Chapter 7 · Matrices

Counting Walks with Matrix Powers

A^k counts walks, and the trick of exponentiating a graph's matrix solves "in exactly k steps" problems in O(n³ log k).

core
time n^3 log k
space n^2
1 snippet
matrix
exponentiation
counting

Read first

TheoremThe fundamental identity

Let A be the adjacency matrix of a graph (weighted: put the weights in the entries). Then

(A^k)_ij = #{walks of length exactly k from i to j}.

For a weighted graph the sum ∑_P ∏_{e ∈ P} w(e) runs over the same walks.

Proof

Induction on k, expanding the matrix product: (A^k)_ij = ∑_m (A^k-1)_im A_mj. A walk of length k from i to j is uniquely a walk of length k-1 from i to some m followed by an edge m → j. The base case k=1 is the definition of A, and k = 0 gives A⁰ = I — the empty walk, from a vertex to itself only. ∎

ExampleExactly k steps, huge k

n ≤ 100 vertices, k ≤ 10¹⁸, count walks 1 → n modulo M: binary-exponentiate A in O(n³ log k) — 100³ · 60 = 6 · 10⁷, instant. "At most k steps"? Either append a self-loop at the target, or exponentiate the block matrix A & I; 0 & I whose powers accumulate ∑_{i ≤ k} Aⁱ.

cppwalk-count.cpp

using Mat = vector<vector<ll>>;
Mat mul(const Mat& a, const Mat& b, ll mod) {
    int n = (int)a.size();
    Mat c(n, vector<ll>(n));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) if (a[i][k])          // skip zeros: 2-5x on sparse A
            for (int j = 0; j < n; j++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}
Mat mpow(Mat a, ll e, ll mod) {
    int n = (int)a.size();
    Mat r(n, vector<ll>(n));
    for (int i = 0; i < n; i++) r[i][i] = 1;
    for (; e; e >>= 1) { if (e & 1) r = mul(r, a, mod); a = mul(a, a, mod); }
    return r;
}

Five variants of the same multiplication

parity / bipartiteness: (A^k)_ii = 0 for all odd k ⇔ no odd closed walk ⇔ bipartite (Bipartite Graphs and 2-Colouring),
girth: the smallest k with tr(A^k) > 0 beyond the trivial contributions; tr(A³) = 6t counts triangles, tr(A⁴) counts 4-cycles plus degenerate ones (subtract them: 2m + 4∑_i C(deg i, 2)),
reachability within k: work over the boolean semiring, or over (min,+) with "+" = ordinary addition (that is exactly min-plus matrix power = "shortest walk with ≤ k edges" — Bellman–Ford and Negative Weights viewed differently),
expected hitting times: replace A by the transition matrix P = D^-1A and solve a linear system (Random Walks and Cover Times),
absorbing chains: ∑_{k ≥ 0} Q^k = (I - Q)^-1 for the submatrix Q over transient states.

Watch outModular arithmetic and 'exactly'

Over a modulus, "is zero" no longer means "there are none" — tr(A⁴) ≡ 0 ±od 2 can hide real cycles. And "walk" is not "path": A^k happily counts walks that revisit vertices. If the problem says simple path of length k, matrix powers are useless — that is Held–Karp: Hamilton in O(2ⁿn²) territory (O(2ⁿ n²)) or it is NP-complete.

Problems for this page

CSES 1136Counting Pathscorethe tree case: difference array, no powers CSES 2181Counting Tilingshardtransfer matrix, exponentiate over width