---
title: "The Matrix–Tree Theorem"
summary: Counting spanning trees with a determinant — plus Gaussian elimination mod p, which is the algorithm you actually type.
difficulty: olympiad
tags: [determinant, counting, matrix]
time: n^3
space: n^2
prereq: [matrices/adjacency]
see: [trees/counting, flow/cuts, special/coloring]
---

:::theorem title="Kirchhoff (matrix–tree)"
Let $L = D - A$ be the Laplacian of a connected graph, and $L^{(r)}$ the matrix obtained by deleting row and column $r$. Then
$$\tau(G) \;=\; \det L^{(r)},$$
the number of spanning trees — independent of which row/column you removed.
:::

:::proof (the shape of it)
Two ingredients.
1. **Cauchy–Binet.** $L = B B^{\mathsf T}$ where $B$ is the $(n-1) \times m$ oriented incidence matrix with row $r$ removed. Hence $\det L^{(r)} = \det(B B^{\mathsf T}) = \sum_{S} \det(B_S)^2$, summing over all $(n{-}1)$-edge subsets $S$ of columns.
2. **A square incidence submatrix is $0$, $\pm 1$.** $B_S$ is nonsingular $\iff$ the edges $S$ contain no cycle and connect everything, i.e. $\iff$ $S$ is a spanning tree; then $\det(B_S) = \pm 1$.
Summing $\det(B_S)^2$ over subsets therefore counts exactly the spanning trees. ∎
:::

:::note title="What the proof gives for free"
- **Multigraphs**: parallel edges contribute additively, since $L$ just accumulates them — "three bridges between the same islands" is one `L[u][v] -= 3`, no new theory,
- **Weighted count**: with $A_{uv} = w_{uv}$, the determinant is $\sum_T \prod_{e \in T} w_e$, the generating function of trees by weight — this is why "minimum spanning tree" and "determinant of a Laplacian" are cousins, not siblings,
- **Disconnected graphs**: $\det L^{(r)} = 0$, matching the fact that there is no spanning tree.
:::

## The arithmetic, carefully
```cpp determinant-mod-p.cpp
ll det_mod(vector<vector<ll>> a, ll p) {        // p prime
    int n = (int)a.size();
    ll res = 1;
    for (int col = 0; col < n; col++) {
        int piv = -1;
        for (int r = col; r < n; r++) if (a[r][col]) { piv = r; break; }
        if (piv == -1) return 0;
        if (piv != col) { swap(a[piv], a[col]); res = (p - res) % p; }   // row swap flips the sign
        res = res * a[col][col] % p;
        ll inv = powmod(a[col][col], p - 2, p);
        for (int r = col + 1; r < n; r++) if (a[r][col]) {
            ll f = a[r][col] * inv % p;
            for (int j = col; j < n; j++) a[r][j] = (a[r][j] - f * a[col][j]) % p;
            if (a[r][col] < 0) a[r][col] += p;
        }
    }
    return res % p;
}
```
For "exact integer" answers instead of modular ones, use **fraction-free Gaussian elimination (Bareiss)**: it keeps every intermediate an integer, dividing by the previous pivot — $O(n^3)$ big-integer multiplications and no gcd blow-up. That is what SPOJ HIGHWAYS-style problems with $n \le 60$ need; a modular answer with one prime is only valid if the question says "mod p".

:::example title="Two counts you can now do instantly"
- $K_n$: $L = nI - J + I = (n)I - J$ restricted, whose eigenvalues are $n$ with multiplicity $n-1$ (and $0$), so $\tau(K_n) = n^{n-2}$ — Cayley's formula, reproved by linear algebra (@trees/counting).
- $K_{a,b}$: eigenvalue bookkeeping gives $a^{b-1} b^{a-1}$.
:::

:::props title="Spectral shortcuts for Laplacians"
- $\tau(G) = \frac{1}{n} \prod_{i=2}^{n} \lambda_i$ for any connected $G$ ($\lambda_i$ = nonzero Laplacian eigenvalues) — handy when the spectrum is known by symmetry (cycles: $\tau(C_n) = n$, complete multipartite, hypercube: $\tau(Q_n) = 2^{2^n - n - 1} \prod...$, better looked up than derived at 11pm),
- $\lambda_2 = 0 \iff$ disconnected, and $\lambda_2$ bounds expansion (Cheeger), which is the *quantitative* version of "is this graph well connected" (@flow/cuts),
- effective resistance between $u,v$ equals $\Omega_{uv} = (L^{+})_{uu} + (L^{+})_{vv} - 2 (L^{+})_{uv}$: "expected commute time" of a random walk is $2m \cdot R_{uv}$ (@special/random-walk) — one pseudo-inverse, three different subjects.
:::

:::warning title="Three failure modes"
1. Forgetting the sign flip on a row swap (determinant is then wrong by $-1$, which mod 2 looks "fine" and mod $10^9{+}7$ looks random).
2. Deleting the wrong row/column pair — you must delete the *same* index from both (any one, but one of each).
3. Building $L$ for a digraph: the theorem needs the *symmetric* Laplacian. For directed graphs the analogue is the **matrix-tree theorem for arborescences** (BEST theorem, @euler/euler-existence) with $L_{ij} = -a_{ij}$ for $i\ne j$ and $L_{ii} = \deg^{-}(i)$, and then you delete row/column of the *root*.
:::

:::problems
- [[SPOJ HIGHWAYS]] Counting Highways | https://www.spoj.com/problems/HIGHWAYS/ | hard | exact determinant
- [[CSES 1134]] Prüfer Code | https://cses.fi/problemset/task/1134 | core | the combinatorial sibling
:::