Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Matrix tree theorem — where it appears

Kirchhoff's result that the number of spanning trees of a graph is the determinant of its Laplacian with any one row and column deleted. The answer is an integer known in advance, which is why a floating-point route to it can be scored exactly.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination4.8·10⁻¹⁶worst, by spectrum10·10⁻¹⁶solve residual1.5·10⁻¹⁵Foster's sum15n − 115difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known

A distance computed by a solve

Effective resistance is the one quantity in this field with no combinatorial route to it — it is defined by a linear system. On a small unweighted graph the answer is a ratio of two integers, so for once the error is known rather than estimated, and every resistance in a graph has to add up to a number fixed in advance.

graph · Effective resistance 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹vertices of the complete graphrelative sizethe algorithm is not the problemsizes counted18worst relative error9.4·10⁻¹⁵first wrong at n =16digits in the answer17spacing of doubles there8largest integer a double holds9·10¹⁵the elimination stays at the rounding levelthe format runs out

A count that comes out of a determinant

The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.

graph · Graph elimination separated by the groupboth groups cyclic: cannot bethe same non-cyclic group6 vertices, 2 pairs117 vertices, 65 pairs3023128 vertices, 1022 pairs435361226a cyclic group is fixed by its order, and the order is the tree countthe group heard less than half the time

A finer invariant that hears less

The Laplacian spectrum fixes a graph's number of spanning trees and not the group those trees form, so the Smith normal form of the grounded Laplacian is a strictly finer integer invariant — and on the six-vertex pair the spectrum cannot separate, it does: ℤ₁₂ against ℤ₂ ⊕ ℤ₆. Over all 1,022 Laplacian-cospectral pairs of connected graphs on eight vertices it separates 435. The adjacency polynomial, a second spectrum rather than a finer one, separates all of them.

graph · Graph invariant top bar: same Laplacian spectrum · bottom bar: same adjacency spectrum0%25%50%75%100%share of cospectral pairs the invariant separatesLaplacian spectrum0%100%adjacency spectrum100%0%signless Laplacian spectrum89%100%spanning-tree count0%98%critical group43%98%degree sequence35%83%triangle count34%0%red: Laplacian-cospectral pairs · blue: adjacency-cospectraleach spectrum hears the other's pairs

Each spectrum hears the other's pairs

Pairs of graphs with the same Laplacian spectrum share a spanning-tree count, so the critical group could only tell them apart by how that count factors — and did on two pairs in five. Turn the census round, to the 733 pairs of eight-vertex graphs with the same adjacency spectrum, and the tree count is free to differ. It does on 717 of them, by a median of six per cent. The critical group separates exactly those 717 and not one more: on all sixteen pairs whose counts agree, including a non-cyclic one, the two graphs have the same group. And the Laplacian spectrum separates all 733, as the adjacency spectrum separated every Laplacian pair.

graph · Graph invariant the critical group, alonequartic pairs separated181of quartic pairs587cubic pairs separated014 vertices, degree 30 of 216 vertices, degree 30 of 2218 vertices, degree 30 of 5020 vertices, degree 30 of 4412 vertices, degree 436 of 12614 vertices, degree 497 of 30016 vertices, degree 448 of 161both groups cyclicseparated by the groupnot separatedbars: distinct pairs, split three waysthree in ten quartic, no cubic

The group hears a switch only at two

On a regular graph the Laplacian is the degree times the identity less the adjacency matrix, so the two spectra are one piece of information and the tree count comes with them; between cospectral regular graphs the critical group is the only exact invariant left. Made by Godsil–McKay switching on four vertices, 705 distinct cospectral pairs of 3- and 4-regular graphs on 12 to 20 vertices give its answer. It separates 181 of 587 quartic pairs and none of 118 cubic ones. And on every one of the 705 the two groups agree everywhere except at the prime two: a switch is a conjugation by a matrix of halves, the group can see it only through its 2-part, and a group whose tree count has fewer than three factors of two cannot see it at all.

graph · Graph invariant

Named alongside it

The objects these essays reach for when they reach for this one.

Graph laplacianCospectral graphsExact ground truthGraph invariantSpanning-treeInvariant factorsSmith normal formCharacteristic polynomialBackward errorConnected componentsDeterminantEffective resistance

All concepts