A determinant that counts trees

A determinant is a signed sum of $n!$ products, which does not sound like a counting device — most of its terms are negative, and counting problems have positive answers. Yet there are matrices built from combinatorial objects whose determinants come out as exact counts of those objects, and the negatives are not an obstacle to be overcome. They are the mechanism.

Kirchhoff’s theorem #

Take a graph. Build its Laplacian: the degree of each vertex on the diagonal, and $-1$ in the entry for each edge. Every row sums to zero, so the matrix is singular and its own determinant is useless. Strike out any one row and the matching column, and take the determinant of what is left.

The answer is the number of spanning trees, and it does not depend on which row was struck.

Both halves are checked in the figures — every one of the $n$ possible minors is computed and asserted equal, and the value is asserted against a brute-force enumeration of every subset of edges of the right size.

For the complete graph on $n$ points the theorem reproduces Cayley’s formula. The Laplacian of $K_n$ is $nI - J$ with $J$ the all-ones matrix; striking a row and column leaves a matrix whose determinant works out to $n^{n-2}$. At $n = 4$ that is $16$, which the figure counts one tree at a time.

The two proofs of that formula are worth comparing, since the collection now has both. Prüfer’s is a bijection: every labelled tree is coded by a sequence of $n-2$ labels, and every such sequence comes from exactly one tree, so the count is $n^{n-2}$ because that is how many sequences there are. Kirchhoff’s is an evaluation: the number is whatever the determinant works out to, and it works out to $n^{n-2}$ by an eigenvalue computation with no trees in it. The bijection explains the formula and the determinant computes it, and neither does the other’s job — which is why a subject keeps both.

Why the non-trees vanish #

The mechanism is worth following, because it is the same mechanism in the second half of this essay and in several arguments elsewhere in this collection.

Orient each edge arbitrarily — the choice will not matter, in the same way that an orientation of a surface is a choice whose consequences cancel — and build the incidence matrix $M$: one row per vertex, one column per edge, with $+1$ at the head and $-1$ at the tail. Then $M M^{\mathsf T}$ is the Laplacian — the diagonal counts edges at a vertex, the off-diagonal counts edges between two — and striking a row of the Laplacian is striking a row of $M$.

The Cauchy–Binet formula expands the determinant of such a product into a sum over all choices of $n-1$ columns of $M$, each contributing the square of a determinant. So the count is a sum over all sets of $n-1$ edges, and each set contributes the square of a small determinant. Now the geometry: a set of $n-1$ edges containing a cycle has linearly dependent columns — go round the cycle and the head and tail contributions cancel — so its determinant is zero, and it contributes nothing. A set with no cycle and $n-1$ edges is a spanning tree, and its determinant works out to $\pm 1$, so it contributes exactly one.

Every subset is visited; the ones that are not trees are killed by dependence; the ones that are trees each contribute one. That is a determinant counting by cancellation, and the cancellation is doing the selection rather than the arithmetic.

Deletion and contraction, and the count as a recursion #

There is a second way to count spanning trees, and putting it beside the determinant says what the determinant is worth.

For any edge $e$ of a graph $G$, every spanning tree either uses $e$ or does not. The ones that do not are the spanning trees of $G$ with $e$ deleted; the ones that do correspond to the spanning trees of $G$ with $e$ contracted — its two ends glued together. So

$$t(G) = t(G - e) + t(G / e),$$

which is a complete recursion with a base case of a single vertex. It is correct, it needs no linear algebra, and it is how the count is proved in a first course.

What it is not is efficient: each step branches in two, so the recursion visits something like $2^{|E|}$ cases, which is the exhaustive search the figures run and which stops being possible at a few dozen edges. The determinant reaches the same number by elimination, in about $n^3$ operations, on a graph of any size. That contrast is the practical case for the theorem — a count with a recursion and a count with a determinant are both proofs, and only one of them can be evaluated on a graph with a thousand vertices.

It also explains why the theorem is stated with a minor rather than with the whole Laplacian. The full matrix is singular, because its rows sum to zero: the all-ones vector is in the kernel, always, whatever the graph. Striking a row and column removes exactly that degeneracy, and which one is removed cannot matter, because the kernel it removes is the same in every direction.

Paths that do not touch #

The second determinant counts something with no graph theory in it, and it is the more visual of the two.

Fix two starting points and two finishing points on a lattice, and consider paths that move only right and up. The number from any one start to any one finish is a binomial coefficient — choose which of the steps go right. Assemble those four numbers into a two-by-two matrix and take its determinant.

The answer is the number of pairs of paths, one from each start to the matching finish, that share no point at all.

The proof is an involution, and it is the cleanest one in this essay. Take a pair of paths that does cross. At the first point where they meet, swap their remaining halves. The result is a pair of paths running to the opposite finishes, and doing it again returns the original — so crossing pairs of the first kind correspond one-to-one with pairs of the second kind. Every pair of the second kind crosses, because the geometry forces it, so the correspondence is a bijection between the two.

The subtracted term of the determinant therefore counts exactly the pairs that must be thrown away, and the difference counts the pairs that never touch. The figure asserts all three numbers: the total, the crossing count, and the product being subtracted.

When the counting stops working #

Both theorems have hypotheses, and both fail loudly without them, which is worth seeing since the statements are so clean.

Kirchhoff’s theorem counts spanning trees of a connected graph. On a disconnected one there are none, and the minor duly comes out zero — the kernel of the Laplacian has dimension equal to the number of components, so any minor of a graph with two components vanishes. That is the theorem reporting an honest zero rather than failing, and it is a good check that the mechanism is what it claims: no spanning trees, no surviving terms.

The path lemma is the fragile one. Its statement above quietly used a fact about the geometry of the four points: every path from the first start to the second finish must cross every path from the second start to the first finish. Move the finishes so that is no longer true, and the determinant stops counting non-intersecting pairs — it computes some signed combination with no combinatorial meaning at all. The general form of the lemma says the determinant counts non-intersecting families weighted by the sign of the permutation they realise, and only when a single permutation is possible does that reduce to a plain count.

So the theorem’s hypothesis is not a technical nicety. It is the condition that makes the involution above a bijection between two sets rather than a partial matching, and a reader who applies the determinant to an arbitrary arrangement of endpoints will get a number that is not counting anything. The figure asserts the hypothesis at its own endpoints — every pair running to the other finishes is checked to cross — rather than assuming it.

What the two have in common #

Both theorems have the shape: a determinant is a signed sum; the negative terms are matched with positive ones by an operation that swaps something; what survives the matching is the objects being counted.

An operation that pairs up terms of opposite sign and is its own inverse is a sign-reversing involution, and it is one of the two or three most productive devices in enumerative combinatorics. Here it appears as the path swap. It appears again in the proof that a determinant with two equal columns vanishes, which is the same swap one level down. And the pentagonal number theorem — where an infinite product with wildly many terms collapses to a sparse alternating series — is the same device applied to partitions.

The general lesson is worth stating plainly, because it inverts the naive reading. A signed sum is better at counting than an unsigned one, provided the signs can be arranged to cancel the unwanted terms. The determinant comes with signs already attached, and the art is in choosing a matrix whose cancellations do the selecting.

Counting with signs, elsewhere in this collection #

The device is general enough to be worth collecting the instances, because seeing them together is what turns a trick into a method.

Inclusion and exclusion is the same idea at its simplest: count everything, subtract the overcounts, add back what was subtracted twice. The alternating sum is a signed sum whose surviving terms are the objects wanted, and the count of arrangements where nobody gets their own hat is the standard worked example.

A determinant with a repeated column is zero — the fact that made the previous rung’s derivation work — is itself a sign-reversing involution: pair each term with the one obtained by swapping the two identical columns’ contributions, and the pair cancels. Every fact in this ladder about the alternating property is that pairing, applied somewhere.

The pentagonal number theorem, where an infinite product of terms expands to a series in which almost everything cancels, is the deepest of the examples here, and its involution is a geometric operation on dot diagrams rather than a swap of paths.

What unites them is a shape of argument rather than a subject: build a signed sum whose terms are easy to describe, find an operation pairing off the terms that should not survive, and read the answer off what is left unpaired. The determinant is the place where that shape is available for free, because the signs are built into the definition and every matrix supplies a new instance.

Where the counts are used #

Kirchhoff’s theorem was proved in 1847 for electrical networks — the same Kirchhoff whose laws about currents at a junction are the rows of the matrix above, and whose analysis of a circuit needs a spanning tree of the network to choose which loops to write equations for — and the trees were a means rather than an end: solving a resistor network by hand means summing over spanning trees, and the determinant is what makes that tractable. The same matrix governs how a random walk moves on the graph, which is why a walk that forgets where it came from and a count of trees turn out to be governed by one object. The graph-theoretic reading came later.

The path lemma is the engine behind a large part of the combinatorics of tableaux and plane partitions: many objects that look nothing like paths turn out to be families of non-intersecting ones, and their counts are then determinants of binomial coefficients. The Catalan numbers are the smallest example — the number of paths that stay below the diagonal is a two-term determinant of binomials, which is the reflection argument written as an algebraic identity.

Both are cases of a broader habit: when a count is hard, look for a matrix whose determinant it is — the same instinct that turns a counting question into a polynomial whose coefficients are the answers. The determinant then supplies both an evaluation method and, through its expansion, a proof.

What the figures cannot show #

The tree figure enumerates. At four vertices and six edges there are sixty-four subsets and the exhaustion is complete; at ten vertices there would be too many subsets to test and the figure would have to trust the theorem it was drawn to check. So the drawing verifies the theorem where verification is cheap, which is the only honest thing a picture can do with a general statement.

The path figure is worse off in an interesting direction. It enumerates 1,225 pairs of paths and draws two of them, so the picture shows one instance of a bijection whose content is that it works for all of them. The involution is easy to describe and impossible to draw in full; what the caption reports is the count, which is the thing the bijection is asserted to preserve.

Neither figure shows the Cauchy–Binet argument at all. It is the reason the theorem is true rather than merely observed, and it is an identity about sums over subsets — no geometry, nothing positioned in space, nothing to look at. This is the standing division in this collection: the exhaustion is drawn, the mechanism is written.

Where the ladder goes next #

Both counts worked because the minus signs cancelled the configurations that should not be counted. That raises the obvious question about the other sum — the one with the signs deleted, which counts all the configurations including the bad ones. It is the permanent, and it is a much worse object than the determinant in every respect that matters, for one reason: with no cancellation there is no elimination.