Characteristic polynomial — where it appears
Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.
The roots are not the coefficients
A polynomial whose roots are the integers one to twenty, expanded exactly, handed to the routine every library uses. The computed roots are wrong in the third digit, the computation is backward stable for the matrix it factorised, and above degree eighteen the coefficients are not double-precision numbers at all.
The spectrum is not the graph
Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.
One mass removed, and one eigenvalue gone
A coordinate with no inertia reads like a coordinate that has been deleted, and a chain of eight masses with one of them removed would then be a chain of seven, with fourteen eigenvalues. It has fifteen. The massless coordinate is still there, still carrying a damper, and it contributes a first-order equation rather than none.
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.
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.
A basis that has to know where the roots are
Wilkinson's polynomial loses its roots in the third figure at degree twenty when they are computed from its monomial coefficients, and the repair offered was to change the basis: in Chebyshev coefficients, with the colleague matrix, the conditioning 'does not degrade exponentially with degree'. Expanded exactly in that basis and rounded once, the integers' roots come back ten orders better at degree twenty — 4.4·10⁻¹³ against 7.6·10⁻³ — and still degrade exponentially, at a third of a decade a degree, to 2.8·10⁻⁴ at forty. Place the same number of roots at the interval's Chebyshev points instead and they stay at 10⁻¹⁴ at every degree, while the monomial route loses them as fast as the integers. The basis does not repair the problem; it has to match where the roots are.
Named alongside it
The objects these essays reach for when they reach for this one.
Exact ground truthCospectral graphsGraph invariantGraph laplacianSpanning-treeBackward errorChebyshev basisCompanion formCondition numberInvariant factorsMatrix polynomialMatrix tree theorem