I would really appreciate some help on this!
$A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n joining nodes i and j." But I tried the following simple example and it doesn't work out.
Am I misunderstanding the definition? E.g. $A^3_{12}=5$ but how is it there are 5 paths of length 3 joining nodes 1 and 2??
A=[0 1 1 1; 1 0 0 1; 1 0 0 1; 1 1 1 0]
$A^3$=[4 5 5 5; 5 2 2 5; 5 2 2 5; 5 5 5 4]
Best Answer
The powers of the adjacency matrix count the number of $i \to j$ walks, not paths. A walk can repeat vertices, while a path cannot.
The walks are:
$1 \to 3 \to 4 \to 2$
$1 \to 3 \to 1 \to 2$
$1 \to 2 \to 1 \to 2$
$1 \to 2 \to 4 \to 2$
$1 \to 4 \to 1 \to 2$