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.
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.
Fig. 1 The invariant factors of a five by five integer matrix, computed by unimodular elimination and again
from the gcds of every minor of each order. Two routes with no algorithm in common, agreeing as
integers.
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
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.
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.
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_k 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 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.
Fig. 2 Pascal, whose determinant is 1, so every invariant factor is 1: the map is an isomorphism of ℤⁿ, no
prime is unlucky for it, and its rank is the same over every ring.
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 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.
Fig. 3 Six by six, where the definition is running 924 minors and the two routes still agree.
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.
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.
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.
Fig. 4 Three by three, the smallest size where the chain can fail and be repaired.Fig. 5 Four by four, where the definition enumerates fifty minors.Fig. 6 Three-digit entries, where the last invariant factor is fourteen digits and the first four are still
one.Fig. 7 Unit triangular, where the map is an isomorphism and every factor is 1.Fig. 8 The integer Hilbert family, whose invariant factors carry the enormous determinant its conditioning
is famous for.Fig. 9 The ranks the invariant factors predict, over eight rings.Fig. 10 The primes dividing the last invariant factor, which are the unlucky ones and the only ones.Fig. 11 The product of the invariant factors, computed three ways without ever computing them.Fig. 12 The lattice these forms are descriptions of, and a basis that describes it badly.Fig. 13 A spanning-tree count, which is the order of the cokernel of a graph’s Laplacian.Fig. 14 The growth that appears in the Hermite transform without any fractions being involved.Fig. 15 The float determinant, which is the summary this essay is about the inadequacy of.Fig. 16 Wide entries at order four, where the definition runs fifty minors.Fig. 17 An isomorphism of the lattice, with every invariant factor 1.Fig. 18 The integer Hilbert family, whose last invariant factor is enormous.Fig. 19 The ranks the invariant factors predict, at order five.Fig. 20 And at order eight, where two invariant factors are even.Fig. 21 The primes dividing the last invariant factor, swept further out.Fig. 22 Their product, computed three exact ways.Fig. 23 The growth a Hermite transform suffers with no fractions in it.Fig. 24 A basis of the lattice these forms are canonical descriptions of.Fig. 25 Whether a system of this kind has an integral answer is a different question.Fig. 26 Six by six, where the definition runs 924 minors.Fig. 27 Pascal at order four, every invariant factor 1.Fig. 28 The ranks those factors predict at order nine.Fig. 29 Their product, on wide entries.Fig. 30 The primes dividing the last one.Fig. 31 The Hermite transform’s growth, in the field’s unit.Fig. 32 A lattice, and a basis that describes it badly.Fig. 33 Hadamard bounding the determinant these factors multiply to.