I knew from Mark Newman's book – Networks: An Introduction (Page 137, Eq: 6.31) that, if $A$ is the adjacency matrix of a graph, then $ij$'th entry of $A^k$ will give me the number of $k$-length paths connecting the vertices $i$ and $j$. This works very well for directed graphs. But does it work for undirected graphs too?
For instance, for the undireceted network below:
if i want to calculate how many $3$-length paths are there from vertex-$2$ to vertex-$1$, then I should find $[A^3]_{12}$. Proceeding in this way, I get,
\begin{eqnarray}
A^3 =
\left(
\begin{matrix}
4 && 6 && 1 && 5 && 5 \\
6 && 2 && 3 && 6 && 2 \\
1 && 3 && 0 && 1 && 2 \\
5 && 6 && 1 && 4 && 5 \\
5 && 2 && 2 && 5 && 2
\end{matrix}
\right)
\end{eqnarray}
And, I find,
the entry of the 1st row and 2nd column = 6 = entry of the 2nd row and 1st column.
Does it mean that there are 6 paths of length 3 from vertex-2 to vertex-1? Cearly it is not true because I have only $1$ path of length $3$ from 2 to 1, namely the sequence: $(2,4,5,1)$.
What am I missing?
UPDATE:
I am attaching a snapshot of Newman's book. He only talks about "paths", but never about a "walk". Is it a mistake?
Best Answer
The powers of the adjacency matrix don't give you the number of paths but the number of walks between any two vertices. In other words, you need to consider walks such that some vertices/edges are repeated (which do exist).