---
title: "Counting Walks with Matrix Powers"
summary: A^k counts walks, and the trick of exponentiating a graph's matrix solves "in exactly k steps" problems in O(n³ log k).
difficulty: core
tags: [matrix, exponentiation, counting]
time: n^3 log k
space: n^2
prereq: [matrices/adjacency]
see: [matrices/recurrences, euler/debruijn]
---

:::theorem title="The fundamental identity"
Let $A$ be the adjacency matrix of a graph (weighted: put the weights in the entries). Then
$$(A^k)_{ij} = \#\{\text{walks of length exactly } k \text{ from } i \text{ to } j\}.$$
For a weighted graph the sum $\sum_P \prod_{e \in P} w(e)$ runs over the same walks.
:::

:::proof
Induction on $k$, expanding the matrix product: $(A^{k})_{ij} = \sum_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 \to j$. The base case $k=1$ is the definition of $A$, and $k = 0$ gives $A^0 = I$ — the empty walk, from a vertex to itself only. ∎
:::

:::example title="Exactly k steps, huge k"
$n \le 100$ vertices, $k \le 10^{18}$, count walks $1 \to n$ modulo $M$: binary-exponentiate $A$ in $O(n^3 \log k)$ — $100^3 \cdot 60 = 6 \cdot 10^7$, instant. "At most $k$ steps"? Either append a self-loop at the target, or exponentiate the block matrix $\begin{pmatrix} A & I \\ 0 & I \end{pmatrix}$ whose powers accumulate $\sum_{i \le k} A^i$.
:::

```cpp walk-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;
}
```

:::props title="Five variants of the same multiplication"
- **parity / bipartiteness**: $(A^k)_{ii} = 0$ for all odd $k$ $\iff$ no odd closed walk $\iff$ bipartite (@foundations/bipartite),
- **girth**: the smallest $k$ with $\operatorname{tr}(A^k) > 0$ beyond the trivial contributions; $\operatorname{tr}(A^3) = 6t$ counts triangles, $\operatorname{tr}(A^4)$ counts 4-cycles plus degenerate ones (subtract them: $2m + 4\sum_i \binom{\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 $\le k$ edges" — @shortest/bellman-ford viewed differently),
- **expected hitting times**: replace $A$ by the transition matrix $P = D^{-1}A$ and solve a linear system (@special/random-walk),
- **absorbing chains**: $\sum_{k \ge 0} Q^k = (I - Q)^{-1}$ for the submatrix $Q$ over transient states.
:::

:::warning title="Modular arithmetic and 'exactly'"
Over a modulus, "is zero" no longer means "there are none" — $\operatorname{tr}(A^4) \equiv 0 \pmod 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 @euler/hamilton-dp territory ($O(2^n n^2)$) or it is NP-complete.
:::

:::problems
- [[CSES 1136]] Counting Paths | https://cses.fi/problemset/task/1136 | core | the tree case: difference array, no powers
- [[CSES 2181]] Counting Tilings | https://cses.fi/problemset/task/2181 | hard | transfer matrix, exponentiate over width
:::