Counting Walks With Powers Of The Adjacency Matrix

Why Matrix Powers Count Walks

An adjacency matrix records which pairs of vertices are joined by an edge. Multiplying matrices combines entries by summing over intermediate indices. That summation has a direct graph-theoretic meaning: it considers each possible intermediate vertex of a walk. Repeated multiplication therefore records walks with more intermediate steps. The precise result is that the entry in row $u$ and column $v$ of the $k$th power counts walks of length $k$ from $u$ to $v$.

Throughout, graphs are finite and simple, and the vertices are listed in a fixed order when forming a matrix. A walk of length $k$ from $u$ to $v$ is a sequence $v_0,v_1,\dots,v_k$ with $v_0=u$, $v_k=v$, and consecutive vertices adjacent. A walk may repeat vertices and edges. Thus, it need not be a path (which has no repeated vertices) or a trail (which has no repeated edges). A walk of length zero consists of its single vertex, so there is exactly one such walk from a vertex to itself and none between distinct vertices.

Definition: For a graph $G=(V,E)$ with a fixed vertex ordering, its adjacency matrix $\mathbf{A}(G)$ has entry $A_{uv}=1$ if $uv\in E$, and $A_{uv}=0$ otherwise. For each integer $k\ge 0$, $\mathbf{A}^k$ is the $k$th matrix power, with $\mathbf{A}^0=\mathbf{I}$, the identity matrix.

Because the graph is simple, each entry of $\mathbf{A}$ is either $0$ or $1$; there are no loops on the diagonal. The convention $\mathbf{A}^0=\mathbf{I}$ matches the length-zero walk definition: the diagonal entries are $1$, and the other entries are $0$.

The Recurrence and the Main Theorem

Write $W_k(u,v)$ for the number of walks of length $k$ from $u$ to $v$. Each walk of positive length has a penultimate vertex, and that vertex gives a recurrence.

Lemma: For every integer $k\ge 0$ and every pair of vertices $u,v$, $$ W_{k+1}(u,v)=\sum_{w\in V} W_k(u,w)A_{wv}. $$

Proof. Consider a walk of length $k+1$ from $u$ to $v$, and let $w$ be its penultimate vertex. Its first $k$ steps form a walk of length $k$ from $u$ to $w$, and its last step is possible exactly when $A_{wv}=1$. For a fixed $w$, the number of such walks is therefore $W_k(u,w)A_{wv}$. Every walk has exactly one penultimate vertex, so the sets counted for different $w$ are disjoint and together include every walk from $u$ to $v$. Summing gives the stated recurrence. $\square$

Theorem: For every finite simple graph $G$, every integer $k\ge 0$, and every $u,v\in V(G)$, the entry $(\mathbf{A}^k)_{uv}$ equals $W_k(u,v)$, the number of walks of length $k$ from $u$ to $v$.

Proof. We use induction on $k$. When $k=0$, $\mathbf{A}^0=\mathbf{I}$, so its $uv$ entry is $1$ if $u=v$ and $0$ otherwise. These are exactly the numbers of length-zero walks from $u$ to $v$.

Now let $k\ge 0$ and assume the result holds for length $k$, for every pair of vertices. By the definition of matrix multiplication,

(\mathbf{A}^{k+1})_{uv} =\sum_{w\in V}(\mathbf{A}^{k})_{uw}A_{wv} =\sum_{w\in V}W_k(u,w)A_{wv} =W_{k+1}(u,v).

The middle equality uses the induction hypothesis, and the last equality is the lemma. This proves the statement for length $k+1$. Induction proves it for all $k\ge 0$. If $V$ is empty, there are no entries or vertex pairs to check, so the assertion holds vacuously. $\square$

This proof explains why matrix multiplication is the right calculation: to count walks of one greater length, sum over all possible penultimate vertices. The theorem counts walks, not just paths. A walk that revisits a vertex or retraces an edge contributes another count if its vertex sequence is different.

Worked Calculations

Worked Example: Two-Step Walks in a Path

Let $G=(V,E)$, where $V=\{1,2,3\}$ and $E=\{12,23\}$. In the ordering $1,2,3$, the adjacency matrix is

\mathbf{A}= \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}.

Multiply $\mathbf{A}$ by itself. For instance, the entry in row $1$, column $1$ is $0\cdot0+1\cdot1+0\cdot0=1$, and the entry in row $1$, column $2$ is $0\cdot1+1\cdot0+0\cdot1=0$. Carrying out the same row-by-column calculation for all entries gives

\mathbf{A}^2= \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&0&1 \end{pmatrix}.

The entry $(\mathbf{A}^2)_{22}=2$ counts two length-two walks from $2$ to $2$: $2,1,2$ and $2,3,2$. The entry $(\mathbf{A}^2)_{13}=1$ counts the walk $1,2,3$. The entry $(\mathbf{A}^2)_{12}=0$ says there is no length-two walk from $1$ to $2$: after two steps from $1$, a walk ends at $1$ or $3$, not $2$.

Check: From $1$, the first step must go to $2$, and the second step can go to either $1$ or $3$. Thus the counts from $1$ to $1,2,3$ are respectively $1,0,1$, matching the first row of $\mathbf{A}^2$. From $2$, there are two choices for the first step, and each leads back to $2$ in one more step, giving $2$ walks back to $2$, as the middle diagonal entry records.

Worked Example: Three-Step Walks in a Triangle

Let $G=(V,E)$, where $V=\{1,2,3\}$ and $E=\{12,13,23\}$. Its adjacency matrix is

\mathbf{A}= \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}.

Multiplying rows by columns gives diagonal entries $0\cdot0+1\cdot1+1\cdot1=2$. For example, the entry in row $1$, column $2$ is $0\cdot1+1\cdot0+1\cdot1=1$. The other off-diagonal entries have the same calculation, so

\mathbf{A}^2= \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2 \end{pmatrix}.

To find the number of length-three walks from $1$ to $2$, multiply row $1$ of $\mathbf{A}^2$ by column $2$ of $\mathbf{A}$:

(\mathbf{A}^3)_{12} =2\cdot1+1\cdot0+1\cdot1=3.

Directly, the three walks are $1,2,1,2$, $1,2,3,2$, and $1,3,1,2$. These are all the possibilities: the first step goes to $2$ or $3$. If it goes to $2$, the second step goes to $1$ or $3$, and either choice allows a final step to $2$. If it goes to $3$, the second step must go to $1$ to allow a final step to $2$.

Check: The matrix calculation gives $3$, and the direct list contains exactly three walks. The entry $(\mathbf{A}^2)_{11}=2$ also agrees with the two length-two walks $1,2,1$ and $1,3,1$; these walks can return to their starting vertex even though the graph has no loops.

Worked Example: Three-Step Walks in a 4-Cycle

Let $G=(V,E)$, where $V=\{1,2,3,4\}$ and $E=\{12,23,34,14\}$. In the ordering $1,2,3,4$,

\mathbf{A}= \begin{pmatrix} 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0 \end{pmatrix}.

For example, row $1$ times column $1$ in $\mathbf{A}^2$ gives $0\cdot0+1\cdot1+0\cdot0+1\cdot1=2$, while row $1$ times column $2$ gives $0\cdot1+1\cdot0+0\cdot1+1\cdot0=0$. Computing the remaining entries in the same way gives

\mathbf{A}^2= \begin{pmatrix} 2&0&2&0\\ 0&2&0&2\\ 2&0&2&0\\ 0&2&0&2 \end{pmatrix}.

For the next power, row $1$ of $\mathbf{A}^2$ is $(2,0,2,0)$. Its product with columns $1,2,3,4$ of $\mathbf{A}$ gives $0\cdot2+1\cdot0+0\cdot2+1\cdot0=0$, $1\cdot2+0\cdot0+1\cdot2+0\cdot0=4$, $0\cdot2+1\cdot0+0\cdot2+1\cdot0=0$, and $1\cdot2+0\cdot0+1\cdot2+0\cdot0=4$, respectively. Row $2$ gives $(0,4,0,4)$; rows $3$ and $4$ repeat rows $1$ and $2$, respectively. Hence

\mathbf{A}^3= \begin{pmatrix} 0&4&0&4\\ 4&0&4&0\\ 0&4&0&4\\ 4&0&4&0 \end{pmatrix}.

In particular, there are four length-three walks from $1$ to $2$. As a separate count, the penultimate vertex must be either $1$ or $3$, the two neighbors of $2$. There are two length-two walks from $1$ to $1$, and the $(1,1)$ entry of $\mathbf{A}^2$ is $2$. There are also two length-two walks from $1$ to $3$, as shown by $(\mathbf{A}^2)_{13}=2$. Appending the edge from either penultimate vertex to $2$ gives $2+2=4$ walks.

Check: The direct last-step count is $2+2=4$, agreeing with $(\mathbf{A}^3)_{12}=4$. The matrix calculation and the recurrence both count the possible walks according to their penultimate vertex.

Interpreting the Entries Carefully

The theorem applies to every pair of vertices, including vertices in different components. If there is no walk of a given length between a pair, the corresponding entry of the power is zero. It also applies to isolated vertices: an isolated vertex has no walks of positive length starting from it, while its length-zero walk is still counted by the diagonal entry of $\mathbf{A}^0$.

For a fixed starting vertex $u$, the entries across row $u$ of $\mathbf{A}^k$ count walks of length $k$ from $u$ to each possible endpoint. This follows directly from the theorem, because the entry in column $v$ counts the walks ending at $v$. The entries need not be just $0$ or $1$: distinct walks may have the same starting and ending vertices, as the path and cycle examples demonstrate.

Common Pitfall

Confusing “no loop” with “no return walk.” In the path with $V=\{1,2,3\}$ and $E=\{12,23\}$, it would be wrong to conclude that $(\mathbf{A}^2)_{11}=0$ because $A_{11}=0$. The first number is computed from the whole row and column: $0\cdot0+1\cdot1+0\cdot0=1$. It counts the walk $1,2,1$. The entry $A_{11}=0$ rules out a one-step loop from $1$ to itself; it does not rule out a longer walk that leaves $1$ and returns.

A second useful check is to match the multiplication index to the walk. In $(\mathbf{A}^{k+1})_{uv}=\sum_w(\mathbf{A}^k)_{uw}A_{wv}$, the index $w$ is the vertex just before $v$, not an arbitrary vertex that can be omitted. Every possible penultimate vertex must be included, and each resulting count is added once.

Check Your Understanding

Use the definitions and recurrence to answer the following questions.

For a graph with adjacency matrix $\mathbf{A}$, what does the entry $(\mathbf{A}^0)_{uv}$ count when $u=v$, and when $u\ne v$?
Let $V=\{1,2,3\}$ and $E=\{12,23\}$. Compute $(\mathbf{A}^2)_{33}$ and name the walks it counts.
Explain why the sum for $(\mathbf{A}^{k+1})_{uv}$ is indexed by the penultimate vertex of a walk.
In the triangle with $V=\{1,2,3\}$ and $E=\{12,13,23\}$, compute the number of length-two walks from $1$ to $1$ by both matrix multiplication and direct enumeration.
Can an entry of $\mathbf{A}^k$ exceed $1$? Explain what such an entry means.