A count that comes out of a determinant

Kirchhoff proved in 1847 that the number of spanning trees of a graph is a determinant: delete any one row and column from the Laplacian and take the determinant of what is left. The answer does not depend on which row was deleted, and it is a positive integer.

That makes it an unusual computation for this site. The quantity is discrete, the routine that produces it is continuous, and the correct answer is known in advance to be a whole number — so it looks as though any computation accurate to better than a half can be rounded to the truth.

The two routes #

Exactly. For an unweighted graph the Laplacian has integer entries, so the grounded matrix can be eliminated in BigInt rationals and the determinant is exact. Its denominator must come out 1 — the theorem says the answer is an integer — and the library asserts that rather than assuming it, which is a check on the rational arithmetic that costs nothing.

In floating point. The site’s own pivoted LU, on the same grounded matrix, with the determinant read off as the product of the pivots.

For the complete graph there is a third check that is not a computation at all: Cayley’s formula says the count is nⁿ⁻². Every row of the table below is checked against it.

The elimination is backward stable everywhere #

n     spanning trees          relative error   digits   recovered by rounding
 6    1,296                     0                4        yes
 9    4,782,969                 1.9·10⁻¹⁶        7        yes
12    61,917,364,224            2.5·10⁻¹⁶       11        yes
15    1,946,195,068,359,375     2.6·10⁻¹⁶       16        yes
18    1.21·10²⁰                 1.4·10⁻¹⁵       21        no
20    2.62·10²¹                 4.9·10⁻¹⁵       24        no
22    7.05·10²⁶                 9.7·10⁻¹⁶       27        no

The relative error column never leaves the rounding level. It does not grow with n, it does not grow with the answer, and at twenty-two vertices it is 9.7·10⁻¹⁶ — the same as at nine.

That is exactly what the theory predicts and it is worth saying why, because it is the reassuring half of the essay. A Laplacian’s grounded submatrix is symmetric positive definite and well conditioned on these families, pivoted elimination on such a matrix is backward stable, and the error identity then bounds the forward error by about κ times the unit roundoff. The algorithm is not the problem at any size.

And the answer is wrong from n = 16 #

The complete graph on fifteen vertices has 1,946,195,068,359,375 spanning trees, which is 15¹³ and fits in a binary64 exactly. The one on sixteen has 16¹⁴ = 7.2·10¹⁶, which does not.

2⁵³ is 9,007,199,254,740,991. Above it, consecutive integers are not all representable: at 10¹⁷ the doubles are spaced two apart, at 1.2·10²⁰ they are spaced 16,384 apart, and at 2.6·10²³ they are spaced 33,554,432 apart.

So from sixteen vertices the count cannot be stored, let alone computed. The elimination returns the nearest representable number to the right answer, which is what a backward-stable algorithm should return and is not the count. Rounding it to the nearest integer returns itself, because it already is one — a representable one, sixteen thousand away from the truth.

The error is committed by the format and not by the elimination, and that is a distinction no residual can make. The computed determinant satisfies every check a determinant routine can run: the matrix reconstructs from its factors to 10⁻¹⁵, the pivots are all positive, the growth factor is 1.

The determinant is a product of pivots, and that is the whole story #

It is worth following where the digits go, because the mechanism is completely visible.

Pivoted elimination computes the determinant as the product of the n − 1 diagonal entries of U. Each of those is a floating-point number with a relative error of a few roundings, so the product has a relative error of about n roundings — which for n = 22 is 5·10⁻¹⁵ and matches the measured column.

The product itself is where the size comes from. On the complete graph on twenty vertices the pivots are around twenty each, so their product is 20²¹ divided by something, which is 10²⁷ before the grounding is accounted for. Every intermediate partial product is representable — binary64 reaches 10³⁰⁸ — so there is no overflow, no underflow, and no warning.

What is lost is not magnitude but resolution. The exponent tracks the answer perfectly and the mantissa runs out after fifty-three bits, so the computed number has the right order and the right first sixteen digits and then nothing. For a real-valued determinant that is a completely satisfactory answer. For a count it is not an answer at all.

That distinction — a number whose leading digits are right and whose identity is wrong — is specific to answers that are integers. Nothing on this site that computes a real number has it, and it is why the graph field meets it first.

Why this is a different failure from the site’s usual one #

Almost everything in this collection is about an algorithm’s contribution to a wrong answer, separated from the problem’s. The identity is forward ⪅ condition × backward, and every essay reports which of the two factors was responsible.

Here neither is. The backward error is a rounding, the condition number is small, and the answer is wrong by ten thousand. The missing term is the one this site named in the fifth author: a property of the representation rather than of the computation — and unlike the machine field’s version, which is about which order the additions happened in, this one is about whether the answer can be written down at all.

The general form is worth stating because it applies to any computation whose answer is a large integer. A permanent, a matching count, a partition function, a number of paths — all of them are computed by continuous routines and all of them have answers that outgrow binary64 quickly. The routine’s accuracy is beside the point once the answer has more digits than the format.

What “backward stable” is not promising #

It is worth being precise, because the phrase is doing work in the table and could be read as an excuse.

Backward stability says the computed answer is the exact answer to a nearby problem. For a determinant that means: the number returned is the exact determinant of a matrix within 10⁻¹⁵ of the one handed over. That is a strong statement and it is true here at every size.

What it does not say is that the decimal digits of the answer are right, and for a large integer those are different claims. The exact determinant of a nearby matrix is a different integer, and how different depends on how large the answer is: at 10²⁰ a relative perturbation of 10⁻¹⁵ is an absolute perturbation of 10⁵.

So a backward-stable determinant of a well-conditioned matrix can be wrong by a hundred thousand, and nothing is broken. The site has made this argument before about a determinant deciding nothing; the graph case is the sharpest instance, because here the answer is known to be an integer and the temptation to round is at its strongest.

Where the crossover actually is #

The figure draws two curves — the relative error, flat at 10⁻¹⁵, and the spacing of the doubles relative to the answer, which is 2⁻⁵³ once the answer exceeds 2⁵³ and irrelevant below it.

They cross where the answer passes the largest exactly representable integer, and for the complete graph that is at n = 16, since 15¹³ < 2⁵³ < 16¹⁴. For other families it is wherever the count passes 9·10¹⁵:

graph            spanning trees            digits   recovered
grid 4×4         100,352                     6       yes
grid 5×5         557,568,000                 9       yes
hypercube 4      42,467,328                  8       yes
hypercube 5      20,776,019,874,734,407,680  20      no
complete 15      1,946,195,068,359,375       16      yes
complete 16      72,057,594,037,927,936      17      no

A five-dimensional hypercube has thirty-two vertices and eighty edges — a small graph by any measure — and its spanning-tree count has twenty digits.

That is the practical content: the format runs out long before the graph gets interesting. Any tree count on a graph of more than about a dozen vertices needs exact arithmetic, and the question of which floating-point routine to use never arises.

What to do instead #

Three options, and the third is the one that makes the theorem useful at scale.

Compute exactly. BigInt rationals give the count with no error at all, at a cost that is superquadratic in the size on top of the elimination. Affordable to a few dozen vertices, which is what the figures here do, and what makes the error column measurable in the first place.

Compute the logarithm. log(det) = Σ log(pivot) is a sum of about n terms, each accurate to a rounding, so the log of the count is accurate to about n·10⁻¹⁶ relative — which at n = 32 is fourteen correct digits of an answer that could not be represented at all. That is enough for every use of the count except printing it: comparing two graphs’ counts, computing a probability, estimating an entropy.

Or ask a different question. The number of spanning trees is rarely wanted for itself. What is usually wanted is a ratio — the probability an edge appears in a random spanning tree, which is its effective resistance — and a ratio of two determinants is a quantity of modest size computed by two well-conditioned solves.

That last route is worth dwelling on. It is the same move the inverse essays make: a formula names a quantity that is enormous and awkward, the thing actually wanted is a ratio of two of them, and computing the ratio directly avoids the enormous intermediate entirely. Here the intermediate is an integer with twenty digits and the ratio is a number between zero and one.

The theorem does not depend on which row is deleted #

One property of Kirchhoff’s theorem is worth verifying rather than quoting, because it is the kind of claim that is easy to state and easy to get subtly wrong in an implementation.

Deleting any row and the corresponding column gives the same determinant. That is not obvious — the submatrices are different matrices, with different entries, different pivots and different condition numbers — and it is a consequence of every row of the Laplacian summing to zero.

In floating point the invariance holds to the rounding level and not exactly, and the reason is the one the grounding essay measured: the condition number of the grounded matrix depends on which vertex was grounded, by up to a factor of nine hundred on a star. So the determinant computed after grounding a leaf and the one computed after grounding a hub have different forward errors, both at the rounding level and not the same rounding.

For a count small enough to be represented that difference is invisible, since both round to the same integer. Past the crossing it is not: two implementations that ground different vertices return two different large numbers, both backward stable, differing in their last digits, and both wrong. A count that disagrees between two runs is not evidence of a bug.

That is the graph field’s version of a machine-field observation: the same program, twice returns different numbers for reasons nobody chose, and the right response is to report the disagreement rather than to pick a winner.

The check the theorem provides #

One more use of the exact route belongs here, because it is the reason the exactness is not just a demonstration.

Kirchhoff’s determinant must come out an integer. In rationals the library asserts the denominator is 1, and if the elimination had a bug the assertion would fire — not because the answer was compared against another routine, but because it violated a property the answer must have.

That is the same class of check as Foster’s identity two essays back and the Hilbert inverse in the error field: a mathematical fact the answer has to satisfy, checkable without a second implementation. A brute-force enumeration over all subsets of a five-vertex graph’s edges confirms the theorem itself once, at nine spanning trees, and Cayley’s formula confirms it at four more sizes — so the chain from “the theorem is true” to “this code computes it” has no unchecked link in it.

What a count is usually wanted for #

It is fair to ask why anybody computes this number, given how quickly it stops being computable, and the answer sharpens the advice above.

Network reliability. The number of spanning trees is a crude measure of how many ways a network stays connected, and ratios of it are the useful form: the fraction of spanning trees containing a given edge is that edge’s effective resistance, which is a number between zero and one.

Random spanning trees. Sampling uniformly from spanning trees underlies the sparsification of the previous anchor and several combinatorial algorithms. The samplers never form the count; they use random walks, whose stationary properties encode it.

Statistical physics. The count is the partition function of a spanning-tree model, and what is wanted from a partition function is its logarithm — the free energy — divided by the size. That is exactly the log-determinant route above, and it is well defined in a limit where the count itself is astronomically large.

And graph comparison. Two graphs with the same count are not the same graph, and two with different counts are certainly different. That is a use for the exact integer, on graphs small enough to have one — and it is the use the next essay turns on its head, since the cospectral pair there has the same count as well as the same spectrum.

In none of those is a twenty-digit integer printed. The count is an intermediate, and the intermediate is the part that does not fit — which is the standard situation this site meets whenever a formula names a quantity larger than the answer.

One more reading of the dashed curve #

The figure’s dashed curve is the spacing of the doubles at the answer’s magnitude, divided by the answer — which is 2⁻⁵³ once the count exceeds 2⁵³ and much smaller below it, because a small integer sits among representable numbers spaced far more finely than itself.

Read that way, the curve is the relative resolution of the format at that answer, and the crossing is where the format’s resolution stops being finer than the algorithm’s error. Below the crossing the format is the precise part and the elimination is the imprecise one; above it, the reverse.

That is a general way to look at any computation whose answer is an integer, and it takes one line of arithmetic: compare log₂ of the expected answer against 53. If it is below, the integer is recoverable provided the algorithm is accurate. If it is above, no algorithm helps and the question is which exact route to take.

The line is not always drawn, and the reason it is not is that a floating-point routine gives no symptom when it crosses. Integer arithmetic overflows loudly; floating-point arithmetic loses resolution silently, and a determinant of 10²⁰ looks exactly as healthy as one of 10⁶.

At other settings #