5
$\begingroup$

Let $A$ be an adjacency matrix of a directed graph. What's the meaning of the $(i,j)-$entry of the matrix $((A^T)^{7} \cdot (A^{7}))$ ?

My initial interpretation is that $(i,j)$ of this matrix is zero whenever nodes $i$ and $j$ have no 7-length in-coming paths from a common source. Is that right? Any attention is appreciated!

Improve this question
$\endgroup$
1
  • $\begingroup$ Have you tried calculating the thing on a small example? Why are you interested in that quantity? $\endgroup$
    – Raphael
    Commented Oct 7, 2012 at 22:36

1 Answer 1

Reset to default
7
$\begingroup$

This is answered on Math.SE; see also MathWorld .

Briefly,the $(i,j)$-th entry in $A^n$ gives the number of directed walks from vertex $i$ to $j$ that have length $n$. Also, given another adjacency matrix $B$, this entry in the product $(AB)$ gives the number of directed walks from vertex $i$ to $j$ , that walk first along an edge of the first graph and then along an edge of the second.Putting these two together would give you an interpretation to the product of 7th powers in your question.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Since $B=A^T$ here, there might be more/different meaning. $\endgroup$
    – Raphael
    Commented Oct 7, 2012 at 22:38
  • $\begingroup$ My initial interpretation is that $(i,j)$ of this matrix is zero whenever nodes $i$ and $j$ have no 7-length in-coming paths from a common source. Is that right? $\endgroup$
    – John Smith
    Commented Oct 8, 2012 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.