Count Walks of Length K

Count Walks of Length K looks like a graph traversal problem, but the cleanest solution is a one-line idea from linear algebra: the adjacency matrix raised to the k-th power counts the walks for you.

The slow way first

The brute-force idea is to enumerate every walk: a depth-first search that takes exactly k steps, counting how many times it lands on each target. With branching out of every vertex this explodes — roughly O(n^k) paths in the worst case. For anything but tiny k it is hopeless.

The question to ask: can I build longer walks out of shorter ones instead of re-walking from scratch? Yes — and matrix multiplication does exactly that bookkeeping.

The idea: powers of the adjacency matrix

Let A be the adjacency matrix. Then A[i][j] is the number of length-1 walks from i to j (either 0 or 1, since it is just an edge). The magic fact: multiplying gives the next length.

(A²)[i][j] = Σ_m A[i][m] · A[m][j] — for each middle vertex m, an edge i→m times an edge m→j contributes one length-2 walk. By induction, (A^k)[i][j] counts the length-k walks. So the whole problem is: compute A^k.

The key insight: matrix multiplication is the rule "go one more step." Applying it k - 1 times to A walks every path forward k - 1 extra edges at once.

Walk through it

Step through the animation. We draw the graph, write down A, then multiply A x A. Watch row 0 of the product become [0 0 2 0]: entry [0][2] is 2. The animation then lights up both length-2 walks, 0→1→2 and 0→3→2, that this single number is counting.

Pseudocode

A = the adjacency matrix              # A[i][j] = length-1 walk count
result = A                            # k = 1 case
repeat k - 1 times:
    result = result x A               # append one more edge everywhere
return result                         # result[i][j] = length-k walk count

The Python solution

def count_walks(adj, k):
    n = len(adj)
    A = [[adj[i][j] for j in range(n)]
         for i in range(n)]
 
    def matmul(X, Y):
        Z = [[0] * n for _ in range(n)]
        for i in range(n):
            for m in range(n):
                for j in range(n):
                    Z[i][j] += X[i][m] * Y[m][j]
        return Z
 
    result = A
    for _ in range(k - 1):
        result = matmul(result, A)
    return result

• A is a fresh copy of the input matrix — result starts here, which already answers k = 1.
• matmul is plain O(n³) matrix multiply: Z[i][j] sums X[i][m] * Y[m][j] over the middle vertex m.
• That inner sum (lines 9-12) is the whole trick: it glues a walk into m onto a walk out of m.
• The loop runs k - 1 times, each appending one more edge, so result ends as A^k.
• Reading result[i][j] gives the count of length-k walks from i to j.

Complexity

The repeated-multiply version is O(k · n³). When k is huge you can do better with matrix exponentiation (binary exponentiation on matrices), squaring A to climb the exponent in O(log k) multiplies.

When this pattern shows up

Practice