Invariant factors — where it appears
Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.
The rank depends on the ring
A floating-point rank is a decision about a threshold. Remove the arithmetic error entirely and the threshold goes away — and the answer still is not a property of the array of numbers, because one integer matrix has rank six over the rationals, five modulo three and four modulo two, with nothing rounded and nothing decided.
What a determinant does not determine
Two integer matrices can have the same determinant, the same rank and the same size, and define genuinely different maps. What separates them is a list of integers each dividing the next — computed here twice, once by unimodular elimination and once from the gcds of every minor, which share no algorithm at all.
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.
The field decides it, usually
A matrix whose rank depends on the field it is read over was built, the first time, from its invariant factors outward, because random integer matrices never seemed to show the effect. Random 0/1 matrices show it at almost every size that is not tiny. At twenty rows, 99.8% of them are invertible over the rationals, 29% modulo two, 56% modulo three — and 71% of the ones the rationals call invertible are singular modulo two. Modulo two they obey, corank by corank, the law for uniformly random matrices over that field; modulo three and five, which their entries cannot fill, they converge to that field's law anyway.
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.
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.
The swell was one-sided
The Smith form can be computed modulo the determinant, and it was predicted to return the right invariant factors, to stay within twice the determinant's width, and to cost about what the modular Hermite form costs instead of the far larger count of the plain Smith routine. The first three hold. The comparison does not: the plain Smith routine never needed a far larger count. With column operations as well as row operations, its smallest-entry pivot is a unit after a step or two, every entry it holds is a minor of the matrix, and nothing it writes is wider than the determinant — at every size to sixty-four, at a fiftieth of the modular route's work. The swell the Hermite form suffered belonged to doing elimination with one hand.
Named alongside it
The objects these essays reach for when they reach for this one.
Smith normal formExact arithmeticCospectral graphsExact ground truthGraph invariantGraph laplacianMatrix tree theoremModular arithmeticSpanning-treeUnimodularCharacteristic polynomialDeterminant