Every essay — page 17
The matrix that is a graph
Every matrix in the fields before this one arrives as a matrix. A graph does not: it arrives as vertices and edges, two different matrices can be built from it that answer different questions, and what anybody wants back is a partition, a ranking or a count — a discrete answer, computed by continuous arithmetic. So a rounding here does not make the answer slightly wrong, it makes it a different answer: a connected graph reported as two pieces, a leaderboard whose middle places are decided by one uncrawled link, a determinant that is known in advance to be a whole number and stops being one at sixteen vertices while the elimination that produced it stays backward stable throughout. Two things this field has that nothing else on the site does. The Laplacian's null vector is exact — the rows are cancellations of integers, so L·1 is zero rather than nearly zero. And there is a two-sided bound that is proved rather than estimated, from one matrix–vector product.
A bound with a square root in it
Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂).
A partition decided in the last digit
On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector.
A ranking that is an eigenvector
PageRank is the stationary vector of a walk that follows links with probability α and jumps at random otherwise.
The rate is the second eigenvalue
A walk forgets where it started at a rate the graph's second eigenvalue names exactly.
A chain with no stationary vector
A page with no outgoing links loses forty per cent of the walker's probability in six hundred steps.
An eigenvector that must not change sign
Perron's theorem says the leading eigenvector of a connected nonnegative matrix is strictly positive.
A ranking whose order is not determined
Of the fourteen adjacent comparisons in a top-fifteen, fourteen survive perturbing the arithmetic at the rounding level, eleven survive moving the teleportation parameter across its usual range, and three survive removing one link.
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.
A graph with a tenth of the edges
Keeping 344 of 1,225 edges, sampled by effective resistance and reweighted, preserves every eigenvalue of the Laplacian to within a factor of 1.7.
Eliminating a vertex is a graph operation
Gaussian elimination on a Laplacian deletes a vertex and joins its neighbours into a clique with conductances wᵢwⱼ over Σw.
A preconditioner that is a tree
Every eigenvalue of a tree-preconditioned Laplacian is at least one and at most the total stretch — a combinatorial integer with no arithmetic in it.
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 spectrum is not the graph
Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits.
A Laplacian that is not symmetric
Point the edges and the matrix stops being symmetric.
A conductance the arcs do not measure
Symmetrising a directed Laplacian with respect to its walk recovers everything the arrows took — a real spectrum, a sweep cut, a Cheeger inequality.
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 ℤ₂ ⊕ ℤ₆.
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.
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.
No subtraction, and no waiting
The power iteration keeps a positive vector's small entries correct because it never subtracts, and it pays for that in steps.
The stall was in the block
On two dense clusters joined by a coupling ε, the power iteration needs about 7/ε steps and then stalls at about u/(4ε).
The set has to be even outward
Switching on four vertices makes cospectral regular graphs, and the critical group separated 181 of 346 quartic pairs whose switching set had no edges inside and none of 118 cubic ones.
Three is where it can hear
A Godsil–McKay switch on four vertices conjugates by a matrix of halves, and the critical group hears it at the prime two exactly when the switching set's indicator is a Laplacian null vector modulo two.
Exact arithmetic, and what it costs instead
An integer matrix eliminated over the rationals commits no rounding anywhere, so the forward error is zero, the residual is the zero vector, and the identity the rest of this site is built on has nothing left to say. The cost does not disappear with the error — it moves into the length of the numbers, where three eliminations returning the same integer differ by four orders of magnitude in the widest one they form. What is left to decide is which route pays: divide by the previous pivot and stay in the integers, reduce every fraction and pay a gcd per operation, or work modulo primes where nothing can grow and put the answer back together afterwards.
An answer with no error in it
An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left.
Every intermediate is a minor
Fraction-free elimination divides by the previous pivot at every step and the division is always exact.