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,