What a determinant does not determine

The determinant decides nothing is an argument this site has already made in floating point: the number is a poor test for singularity, a poor measure of conditioning, and its scale is arbitrary. Over the integers it stops being arbitrary — it is an integer, it counts something, and it is exact — and it is still not enough to say what the matrix does.

An integer matrix is a map from ℤⁿ to ℤⁿ. Two such maps can have the same determinant and be different in a way that no rank, norm or spectrum records.

What the list is #

Every integer matrix can be brought by unimodular row and column operations — integer operations with integer inverses, so nothing about the lattice changes — to a diagonal form

diag(s₁, s₂, …, sᵣ, 0, …, 0)      with s₁ | s₂ | … | sᵣ

each entry dividing the next. That is the Smith normal form, the sᵢ are the invariant factors, and they are unique: no choice made during the elimination can change them.

The determinant is their product. The rank is how many are nonzero. The rank modulo p is how many are not divisible by p — which is the previous essay’s whole subject, and which the list makes into a triviality. And the quotient ℤⁿ divided by the image of the map is ℤ/s₁ ⊕ ℤ/s₂ ⊕ … , so the list is a complete description of what the map does to the lattice, of which every other invariant is a summary.

A random integer matrix has a dull one: on the five by five above the factors are 1, 1, 1, 1 and 22616, four trivial entries and one carrying the whole determinant. That is typical and it is a theorem-shaped fact rather than an accident — the cokernel of a random integer matrix is cyclic with high probability — but typical is exactly what makes the exceptions worth being able to detect.

How typical is measurable on this site’s own generator rather than citable. Three hundred matrices at each of six settings:

The cyclic share sits between 0.77 and 0.91 with no trend in the size — which is what a limit independent of n looks like at three hundred samples — and the eight-by-eight row lands on 0.847 against the Cohen–Lenstra figure of 0.846936. The dullness is a measurement now, and the exceptions are about one matrix in six.

The other two columns belong to a claim made three sections below, and they are put here because they come from the same sample. They are what the divisibility sweep is worth.

Why the determinant cannot carry it #

There is a reason no single number can, and it is worth stating because it explains why the invariant is a list rather than a better scalar.

The determinant is the product of the invariant factors, so it is one equation in r unknowns. On a five by five with factors 1, 1, 1, 1, 22616 it is satisfied by that list and by 2, 2, 2, 11, 257 and by every other factorisation of 22616 into an increasing divisor chain. The determinant is the volume of the image lattice’s fundamental cell; the invariant factors are the shape of it, and a volume never determined a shape.

The rank is the other summary and it is worse: it counts how many factors are nonzero and says nothing about any of them. Between them, rank and determinant fix the number of entries and their product, which on a large matrix is a very small part of the information.

This is the same relation the site keeps meeting between a norm and the object it summarises. Two condition numbers of one matrix are two summaries disagreeing about the same thing; a spectrum does not determine a graph; a singular value does not determine a rank. What is unusual here is that the complete invariant exists, is computable, and is not much longer than the summary — which is rarely the case and is the reason this essay can be about what a determinant leaves out rather than about how hard the question is.

Two routes, sharing nothing #

The site’s habit is that every quantity is computed twice by routes that share no arithmetic, and here the two are unusually far apart.

The algorithm finds the smallest nonzero entry of the remaining block, moves it to the corner, and clears its row and column by integer division with remainder — repeating until the row and column are clear, which terminates because the corner entry strictly decreases whenever it does not. Then it recurses on the trailing block. It is a few dozen lines and it is fast.

The definition says s₁s₂…sₖ is the greatest common divisor of all k × k minors. So computing the list from the definition means enumerating every k × k minor for every k, taking gcds, and dividing consecutive results. On a six by six that is 400 minors of orders one through six, each by cofactor expansion. It is exponential and it is the reason the figure stops at n = 6.

They agree, entry for entry, at every size drawn, which is a stronger statement than it sounds. The gcd of every k × k minor is a single integer distilled from hundreds of determinants, and it has to come out equal to a product of diagonal entries produced by a completely different process. There is no tolerance in the comparison and no way for a near miss to pass. Neither could have confirmed itself: the algorithm’s correctness is a sequence of claims about unimodular operations, and the definition’s is a claim about gcds of determinants, and there is no step in common where a shared mistake could hide.

The divisibility chain is not free #

The refusal this essay carries is about a step that is easy to leave out because the code looks finished without it.

The elimination above reaches a diagonal. A diagonal reached by unimodular operations is not automatically a Smith normal form, because the divisibility chain can fail: an elimination can perfectly well produce diag(2, 3), and 2 does not divide 3. The determinant is right, the rank is right, and the invariant factors are 1 and 6 rather than 2 and 3.

The repair is a sweep: wherever sᵢ does not divide sᵢ₊₁, replace the pair by their gcd and their lcm, and repeat until nothing moves. That preserves the product and imposes the chain, and it is a genuine part of the algorithm rather than tidying.

Leaving it out gives a routine that returns the right determinant and the right rank and the wrong answer to every question the invariant factors are actually for — including which primes are unlucky, which is the question that sent this field here. The check against the minors catches it, which is what a second route is for.

That paragraph has a rate in it and the table above supplies it. The sweep changes the answer on 9% to 15% of random matrices — about one in nine — and on every one of the 1,800 sampled the unswept diagonal still has the right determinant and the right rank. Both columns are 1.000, with no exceptions anywhere in the sample.

Which is the exact shape of a defect worth writing a second route for. The failure rate is high enough that the bug cannot survive a comparison against the minors — one matrix in nine means a handful of test cases finds it immediately — and it is invisible to every check somebody would think to write first. A test suite asserting that the determinant of the diagonal equals the determinant of the matrix passes on all 1,800. So does one asserting the rank. The routine is wrong on eleven per cent of its inputs and right on every quantity anybody would compare it against.

There is a general form of that worth extracting, because this collection keeps arriving at it from different fields. A summary of an object cannot detect a bug in the object’s construction unless the bug changes the summary, and a bug that preserves a product cannot be found by checking the product. The divisibility sweep is exactly a rearrangement that preserves the product — it replaces a pair by their gcd and their lcm — so it is guaranteed invisible to the determinant, by construction rather than by luck. The rank survives it for the same reason: gcd and lcm of two nonzero integers are both nonzero.

So the two quantities a reader would naturally check are the two the defect is provably invisible to, and that is not a coincidence about this sweep. Any repair that acts by redistributing a quantity among the factors while preserving their product has the same immunity, and the only test that sees it is one computing the factors another way. Which is what makes the exponential route through the minors worth its cost: not that it is more accurate — there is no accuracy here, the arithmetic is exact — but that it is the only available check that is not a function of what the fast route already got right.

The two matrices the title is about #

The abstract claim deserves the concrete pair, and it is small enough to write down.

A = [ 2  0 ]        B = [ 1  0 ]
    [ 0  3 ]            [ 0  6 ]

Both have determinant 6. Both have rank two over ℚ. Both are diagonal, symmetric, and have the same Frobenius norm to within a few per cent. Every summary this site normally reaches for treats them as the same kind of object.

They are different maps. A sends ℤ² onto the sublattice of pairs with the first coordinate even and the second a multiple of three; B sends it onto the pairs whose second coordinate is a multiple of six. The quotients are ℤ/2 ⊕ ℤ/3 and ℤ/1 ⊕ ℤ/6 — which are isomorphic, as it happens, since 2 and 3 are coprime, and the Smith form says so by returning 1, 6 for both.

So the honest small example is the one where the invariant factors agree and the diagonals do not, and it makes the point better than a pair where they differ: the diagonal an elimination reaches is not an invariant and the Smith form is. Change A to diag(2, 4) and the factors become 2, 4 rather than 1, 8, the quotient is ℤ/2 ⊕ ℤ/4 rather than ℤ/8, and now two matrices with determinant 8 and rank 2 are genuinely different maps that no determinant, rank, norm or spectrum separates.

That is the whole content of the form, and it is why the divisibility chain is the part that carries the information rather than an aesthetic preference for a tidy diagonal.

The other normal form, and what it costs #

The Hermite normal form is the one-sided version: row operations only, reaching an upper triangular form with positive pivots and every entry above a pivot reduced modulo it. It describes the same lattice — the row space over ℤ — and it is what one computes to answer do these vectors generate that lattice.

Its cost is the field’s usual story in a new place, and it is worse than the Smith form’s.

The entries of the Hermite form itself are bounded, because each is reduced modulo a pivot. The transform is not: the unimodular matrix U with U·A = H accumulates every quotient the elimination used, and those grow. Measured on a five by five random matrix the Hermite form’s widest intermediate is 24 bits against the Smith form’s 15, and the gap widens with n.

That is the swell from the field’s first essay appearing in a routine with no fractions in it anywhere. It is not the fractions that grow — it is the coefficients of a combination, and any algorithm that reports how it reached its answer pays for the report.

The transform is unimodular, which is checkable and is checked: its determinant is exactly ±1 at every size, computed by the same fraction-free elimination the rest of the field uses. That is the conserved quantity here, and it is the one thing an implementation cannot get subtly wrong without being caught.

What it is for #

Three uses, and none of them is a numerical one, which is worth saying plainly.

Deciding whether an integer system is solvable in integers. Ax = b has an integer solution exactly when the invariant factors divide the corresponding components of the transformed right-hand side. A rational solution always exists when A is nonsingular, and the essay on the answer’s length is about how long it is; whether it happens to be integral is a completely different question and this is the one that answers it.

Deciding which primes are unlucky, which the field has now met twice — for a determinant and for a rank — and which is exactly the primes dividing an invariant factor.

Describing a quotient group. The cokernel of an integer matrix is ℤ/s₁ ⊕ ℤ/s₂ ⊕ …, which for a graph’s Laplacian is the sandpile group and whose order is the number of spanning trees. That is the same integer the graph field computes from a determinant, and the invariant factors say not just how many trees there are but what the group of them is.

What a numerical reader should notice about the cost curve #

This field has been consistent about one thing: the price of exactness is the length of the numbers, and different routes pay it differently. The normal forms add a case that does not fit the pattern and is worth flagging.

The Smith form’s output is short. Five ones and a fourteen-digit integer is barely more information than the determinant, and on a random matrix it is nearly the same information. So this is not a case like the exact solution’s length, where the answer itself is large and no route can avoid it.

What is expensive is the route, and the two available routes are expensive for unrelated reasons. The elimination grows its intermediates because it accumulates quotients; the definition is exponential because it enumerates minors. There is no known route that is cheap in both senses, which is unusual on this site — almost every other quantity here has one good algorithm and several bad ones, and the essays are about which is which.

That makes the normal forms the field’s outlier: a short answer with no cheap route to it. The practical consequence is that they are computed when they are needed and not as a diagnostic, which is why the unlucky-prime question is answered probabilistically in practice even though it has an exact answer sitting right here.

What is not here #

Two things are outside what this essay measures and are worth stating rather than implying.

The cost of the Smith form on matrices of any size is genuinely bad, and the routine used here is the naive one: it terminates, its entries are bounded by the check against the minors, and it makes no attempt to control the growth that a modular or a Hermite-first approach would. Sizes above about ten are not affordable with it, which is why every figure here stops at six.

And the divisibility repair as implemented is a sweep to a fixed point rather than a single pass. That is correct and it is not the standard construction, which interleaves the chain with the elimination. Both reach the same unique answer, since the invariant factors do not depend on the route — which is the property being relied on, and it is also the property the check against the minors is testing.

Where the graph field meets this one #

The clearest application on this site is one that has already been computed for a different reason, and putting the two together is worth a section.

A connected graph’s Laplacian has rank n − 1, so its Smith normal form has one zero and n − 1 nonzero invariant factors. The product of those factors is the number of spanning trees — which is Kirchhoff’s theorem, and which the graph field computes as a determinant of the grounded Laplacian. The invariant factors say more: the cokernel is ℤ/s₁ ⊕ … ⊕ ℤ/sₙ₋₁, and that group is the one whose elements are chip configurations on the graph modulo the moves that fire a vertex.

So two graphs with the same number of spanning trees can have different groups, exactly as two matrices with the same determinant can be different maps. And the pair the graph field found with identical characteristic polynomials — a triangle joined to a square, and K₂,₃ with a pendant edge, twelve spanning trees each — is a candidate for exactly that: same spectrum, same tree count, and a question about the group that the spectrum cannot answer.

That is the second time this field has supplied a finer invariant than a spectral one, and both times the finer invariant is integral. It is the standing reason the field is placed after graph rather than beside cost: the objects it separates are ones the graph field could see were different and had no instrument for.