Counting Network Walks with Matrix Powers

Walks and Adjacency Matrices

A network records which transitions are possible. Its adjacency matrix records those transitions numerically, and matrix powers combine them across several steps. The key interpretation is precise: an entry of the \(k\)th power counts walks of exactly \(k\) edges between two vertices. This works for directed and undirected networks, provided that the matrix entries represent edge counts and that parallel edges are treated as distinct choices.

Consider a finite network with vertices labelled \(1,\dots,n\). In a directed network, an edge from \(i\) to \(j\) is oriented from \(i\) toward \(j\). For an undirected network, each edge can be traversed in either direction. A loop is an edge from a vertex to itself. If parallel edges are present, they are distinct edges with the same endpoints.

For a network in which we count walks, define the adjacency matrix \(\mathbf{A}=[a_{ij}]\in\mathbb{R}^{n\times n}\) by letting \(a_{ij}\) be the number of directed edges from \(i\) to \(j\). In an undirected network, count edges joining \(i\) and \(j\); the resulting matrix is symmetric. In particular, \(a_{ii}\) counts loops at \(i\). With no parallel edges, each entry is either \(0\) or \(1\). The row index is the starting vertex and the column index is the destination.

Here the entries must be edge counts, not arbitrary edge weights. If an adjacency matrix instead stores general numerical weights, its powers combine products of weights along walks; the entries are then weighted totals, not necessarily numbers of walks. For a counting matrix with parallel edges, each available edge is one separate choice, as the definition above requires.

Why a Matrix Product Adds One Step

The multiplication rule explains the walk-count interpretation. The \((i,j)\) entry of a product \(\mathbf{B}\mathbf{C}\) is \(\sum_{r=1}^n b_{ir}c_{rj}\). For adjacency matrices, the intermediate index \(r\) specifies the vertex reached after the first step. There are \(a_{ir}\) choices of edge for that first step and, when the entries of \(\mathbf{A}^{k}\) count length-\(k\) walks, \((\mathbf{A}^{k})_{rj}\) choices for the remaining steps. Multiplying counts the combinations through \(r\), and summing includes every possible intermediate vertex.

Proof. We use induction on \(k\). For \(k=0\), \(\mathbf{A}^{0}=\mathbf{I}_n\), whose \((i,j)\) entry is \(1\) if \(i=j\) and \(0\) otherwise. These are exactly the numbers of length-\(0\) walks by the definition. For \(k=1\), \((\mathbf{A})_{ij}=a_{ij}\), which is the number of available edges from \(i\) to \(j\), so it counts length-\(1\) walks, including separate choices among parallel edges.

Now suppose for some \(k\geq 1\) that \((\mathbf{A}^{k})_{rj}\) counts length-\(k\) walks from \(r\) to \(j\), for every pair of vertices \(r,j\). By matrix multiplication,

For each \(r\), a walk counted by the product \(a_{ir}(\mathbf{A}^{k})_{rj}\) is formed by choosing one of the \(a_{ir}\) edges from \(i\) to \(r\), then choosing one of the length-\(k\) walks from \(r\) to \(j\). This gives a walk of length \(k+1\) from \(i\) to \(j\). Conversely, every length-\((k+1)\) walk from \(i\) to \(j\) has a uniquely specified first edge and a uniquely specified remaining length-\(k\) walk. Its first edge ends at exactly one vertex \(r\), so it is counted in exactly one term of the sum. Thus the sum counts every such walk exactly once, proving the claim for \(k+1\). The induction proves the theorem for all \(k\geq 0\). \(\square\)

Worked Counts in Directed Networks

Undirected Networks and Total Counts

For an undirected network, each edge can be traversed in either direction. Its adjacency matrix is symmetric: \(a_{ij}=a_{ji}\). Matrix powers still count walks by the same theorem; symmetry adds a useful relation between walks in opposite directions.

Proof. Reversing the order of the vertices and traversed edges in any length-\(k\) walk from \(i\) to \(j\) gives a length-\(k\) walk from \(j\) to \(i\). Because every edge in an undirected network can be traversed in either direction, the reversed sequence is allowed. Reversing again recovers the original walk, so this correspondence is a bijection. It preserves distinct choices of parallel edges, since the same chosen edges are used in reverse order. The two sets of walks therefore have the same number of elements. By the walk-counting theorem, those numbers are \((\mathbf{A}^{k})_{ij}\) and \((\mathbf{A}^{k})_{ji}\), respectively. For \(k=0\), the equality also follows from the identity matrix. \(\square\)

Proof. For each destination \(j\), the walk-counting theorem says that \((\mathbf{A}^k)_{ij}\) counts walks from \(i\) to \(j\). Walks from \(i\) have exactly one destination, so adding these counts over \(j=1,\dots,n\) counts each walk starting at \(i\) exactly once. Adding that row sum over all starting vertices counts every walk in the network exactly once, since each walk has exactly one starting vertex. \(\square\)

Exact Length, Not “At Most”

The power \(\mathbf{A}^k\) counts walks of exactly \(k\) steps. It does not include shorter walks automatically. For example, the identity matrix \(\mathbf{A}^0\) counts only the length-\(0\) walks; it does not count the length-\(1\) walks recorded by \(\mathbf{A}\). If a question asks for walks of lengths from \(0\) through \(k\), the relevant matrix is the sum \(\mathbf{I}_n+\mathbf{A}+\cdots+\mathbf{A}^k\): each power contributes the counts for its own exact length.

A common error is to read the adjacency entry \(a_{ij}=2\) for two parallel edges as one walk because there is only one vertex sequence \((i,j)\). That calculation uses a definition that forgets which edge was traversed. Under the edge-choice definition, there are two length-\(1\) walks, one for each edge, and the matrix entry correctly equals \(2\). A separate error is to interpret \((\mathbf{A}^2)_{ij}\) as the number of walks of length at most \(2\). It counts only length \(2\); shorter lengths must be added as separate powers.

These interpretations are useful whenever a question asks how many ways a network can be traversed in a fixed number of steps. The matrix power combines all possible intermediate vertices without requiring the walks to be listed individually. For small networks, direct multiplication makes the count visible; for larger powers, the same rule applies, with each entry retaining its exact meaning.