Chapter 7 · Matrices
The Matrix–Tree Theorem
Counting spanning trees with a determinant — plus Gaussian elimination mod p, which is the algorithm you actually type.
Let L = D - A be the Laplacian of a connected graph, and L(r) the matrix obtained by deleting row and column r. Then
the number of spanning trees — independent of which row/column you removed.
Two ingredients.
- Cauchy–Binet. L = B Bmathsf T where B is the (n-1) × m oriented incidence matrix with row r removed. Hence det L(r) = det(B Bmathsf T) = ∑S det(BS)2, summing over all (n{-}1)-edge subsets S of columns.
- A square incidence submatrix is 0, ± 1. BS is nonsingular ⇔ the edges S contain no cycle and connect everything, i.e. ⇔ S is a spanning tree; then det(BS) = ± 1.
Summing det(BS)2 over subsets therefore counts exactly the spanning trees. ∎
- 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 Auv = wuv, the determinant is ∑T ∏e ∈ T we, 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
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(n3) big-integer multiplications and no gcd blow-up. That is what SPOJ HIGHWAYS-style problems with n ≤ 60 need; a modular answer with one prime is only valid if the question says "mod p".
- Kn: L = nI - J + I = (n)I - J restricted, whose eigenvalues are n with multiplicity n-1 (and 0), so τ(Kn) = nn-2 — Cayley's formula, reproved by linear algebra (Counting Trees: Cayley and Prüfer).
- Ka,b: eigenvalue bookkeeping gives ab-1 ba-1.
Spectral shortcuts for Laplacians
- τ(G) = (1)/(n) ∏i=2n λi for any connected G (λi = nonzero Laplacian eigenvalues) — handy when the spectrum is known by symmetry (cycles: τ(Cn) = n, complete multipartite, hypercube: τ(Qn) = 22n - n - 1 ∏..., better looked up than derived at 11pm),
- λ2 = 0 ⇔ disconnected, and λ2 bounds expansion (Cheeger), which is the quantitative version of "is this graph well connected" (Cuts and Flows),
- effective resistance between u,v equals Ωuv = (L+)uu + (L+)vv - 2 (L+)uv: "expected commute time" of a random walk is 2m · Ruv (Random Walks and Cover Times) — one pseudo-inverse, three different subjects.
- Forgetting the sign flip on a row swap (determinant is then wrong by -1, which mod 2 looks "fine" and mod 109{+}7 looks random).
- Deleting the wrong row/column pair — you must delete the same index from both (any one, but one of each).
- 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 Tours: When They Exist) with Lij = -aij for i≠ j and Lii = deg-(i), and then you delete row/column of the root.