# calculating walks in an undirected graph using linear algebra identity

I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says:

Walks: which allow both nodes and edges to be used more than once. For example, in Figure 1, Mary-Bob-Sue-Ramona-Bob-Mary-Joe is a walk, but not a trail or a path. A particular dollar bill flows through the person-person network along walks. Mary might give the bill to Bob in one transaction, and Bob might return it to Mary in another.

A trail is when a node i may be visited multiple times, but a particular edge connecting it with a node j, can be visited no more than 1 time.

An identity from linear algebra is used which I cannot find is used Suppose an undirected network has an adjacency matrix A, where $a_{i,j}=1$ if nodes i and j are connected, and $a_{i,j}=0$ otherwise. Then the basic identity

$(A^{n})_{ij} = \sum^{n}_{k_{1} = 1}\sum^{n}_{k_{2}=1}\ldots\sum^{n}_{k_{n-1}=1}a_{i,k_{1}}a_{k_{1},k_{2}}\ldots a_{k_{n-1},j}$

shows that $(A^{n})_{ij}$ counts the total number of walks of length n from node i to node j.

The indice k is not explicitly defined in the text or given more description. What makes it hard to understand is that the index k is not being summed over the possible nodes the matrix since n is the walk length as it is written, unless there is a mistake.

I want to see if I can be bold and say that the equation should have been better written as (making N be the node set or square matrix dimension):

$(A^{n})_{ij} = \sum^{N}_{k_{1}=1}(\sum^{N}_{k_{2}=1}\ldots(\sum^{N}_{k_{n-1}=1}a_{i,k_{1}}a_{k_{1},k_{2}}\ldots a_{k_{n-1},j}))$

Because I read the equation as a brute force summation over the total set of combinations of length n.

Is this interpretation correct?

and is $(A^{n})_{ij}$ the result of the entry for ij in doing the matrix exponentiation of the adjacency matrix n times because in simple examples I tried with small graphs I did not get the correct answer (tried simple fully connected graph with n=2,3,4)?

Best,

-

Yes, you're right (the $k$'s should run from 1 to $N$, the size of the matrix), and yes, $(A^n)_{ij}$ is the $(i,j)$ entry in $A^n=AA\dots A$ ($n$ factors).