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.
Rank is a decision is one of this site’s oldest arguments and it has a
specific shape. A floating-point matrix does not have a rank; it has singular values, and somewhere in
them is a gap, and the rank is where somebody draws a line. The essay’s whole content is the line: it
is a threshold, it is a choice, and the choice is where the answer comes from.
A reader is entitled to conclude that the trouble is the arithmetic, and that exact arithmetic would
settle it. It does settle that. It does not settle the question.
Fig. 1 One six by six matrix of integers. Its rank is computed exactly, by elimination, with no threshold
anywhere and no small number to be careful about. Three different answers.
The site has said several times that a computed quantity often belongs to the algorithm rather than
to the matrix. This is the sharper version: a quantity that belongs to neither, because the question
was underspecified and the arithmetic supplied the missing argument silently.
The matrix in the figure has rank six over the rationals, five over the field with three elements, and
four over the field with two. Every one of those computations is an exact elimination: the entries are
integers, the pivots are exact, an entry is zero or it is not, and there is nothing anywhere for a
tolerance to compare against.
So the rank of a matrix is not a function of its entries. It is a function of the entries together
with the ring they are read in, and dropping the second argument is what makes the question look
ill-posed. A routine that reports “the rank” has silently chosen one, and a modular routine has
chosen a finite field.
The construction says exactly why, and it is built rather than found.
Take the diagonal matrix diag(1, 1, 1, 1, 2, 6) and conjugate it by two unimodular matrices —
integer matrices with determinant ±1, so their inverses are integral too. The result is an ordinary
looking integer matrix with no visible structure, and its invariant factors are unchanged by the
conjugation: still 1, 1, 1, 1, 2, 6.
Over the rationals every one of those is invertible, so the rank is six. Modulo 3 the last one
vanishes, so the rank is five. Modulo 2 both the fifth and the sixth vanish, so the rank is four. And
modulo 5, 7, 11, 13, 101 or 65537 nothing vanishes, so the rank is six again.
That is the whole mechanism, and it makes the phenomenon completely predictable: the rank over 𝔽ₚ
is six minus the number of invariant factors p divides. Not a probability, not a tendency — a
count. The figure asserts each of the three values before drawing them, so a change to the
construction that broke the correspondence would fail rather than merely make the picture duller.
Fig. 2 The invariant factors of an ordinary random integer matrix: five entries, four of them 1 and one
carrying the entire determinant. The primes dividing that last factor are the only ones at which its
rank drops.
Why this is a different failure from the threshold one #
It is worth separating the two carefully, because they are easy to blur into rank is difficult.
The threshold version is about a continuum. A singular value of 10⁻¹² sits between zero and one,
the matrix is near a rank-deficient one and is not one, and the decision is genuinely a decision:
different thresholds give different answers and all of them are defensible.
The cheap rank-revealing route is about how well a
greedy pivot rule locates that gap, and it has a matrix on which the rule has nothing to choose
between.
The ring version is about a discontinuity, and there is nothing to decide. Over 𝔽₃ the rank is
five, exactly and provably; over ℚ it is six, exactly and provably; and there is no threshold whose
adjustment would reconcile them, because both are right. What is wrong is only the assumption that
they were answering one question.
That makes the ring version closer to
a partition decided in the last digit than to
anything in the rank literature: a correct computation whose subject is not the one that was asked
about. And it is the same substitution as
the unlucky prime one essay back — which is not a
coincidence, since a prime that is unlucky for the determinant is a prime dividing the last invariant
factor, and the determinant is the product of them all.
The mechanism deserves one concrete pass, because “an invariant factor is divisible by p” is a
statement about a normal form and the thing that actually happens is a pivot.
Eliminate the matrix over ℚ and the pivots are nonzero all the way down: six of them, product ±12,
rank six. Eliminate the same matrix modulo 3 and five of the six pivots are nonzero units of 𝔽₃; the
sixth is 0, because the entry that would have been a multiple of 3 is a multiple of 3, and in 𝔽₃ that
is zero. Nothing was small. Nothing was rounded. An integer that happened to be divisible by the
modulus became the additive identity, which is what reduction modulo p is for.
Modulo 2 it happens twice, because two invariant factors are even, and the elimination runs out of
pivots two rows early.
The reason this cannot be defended against by care is that the entry which vanishes is not
identifiable in advance without knowing the invariant factors — and computing those is strictly
harder than the rank was. There is no cheap test. What there is instead is the observation that it
happens at a computable, finite set of primes, so a second prime almost certainly disagrees with a
first that was unlucky.
The natural reaction is that modular rank is unusable, and it is not. It is a lower bound, and a
lower bound on rank is often exactly what is wanted.
The rank over 𝔽ₚ is never larger than the rank over ℚ, because a linear dependence over the rationals
can be cleared of denominators and reduced modulo p, while a dependence modulo p need not lift. So one
modular elimination on machine words certifies that the true rank is at least what it found — and
certifying a large rank is the hard direction, since it needs a nonvanishing minor and a single
modular elimination has produced one.
The direction it cannot certify is deficiency. A matrix with modular rank four might have rank four,
five or six over ℚ, and no number of primes settles it — although agreement across several primes is
strong evidence, and disagreement between two primes is proof that at least one of them is unlucky.
That asymmetry is the same one the determinant had: nonsingularity is cheap to prove and singularity
is not, and it is the shape of certificate
the interval field spends a whole essay on: a verdict of yes
that is cheap and a verdict of no that is not, with nothing can be said as the honest third
outcome. It comes from the same place. A nonzero object stays nonzero at almost every prime, and a zero
object is zero at all of them, so the primes can witness presence and never absence.
Fig. 3 The same construction at order eight, where the ranks over 𝔽₂ and 𝔽₃ are six and seven and every
larger prime returns eight.
There is a further question the field has to name, because it is the one an application usually
wanted and it is not the rank at all.
An integer matrix defines a map from ℤⁿ to ℤᵐ. The image of that map is a subgroup, and describing it
takes more than a dimension: it is generated by vectors, and the quotient by it can have torsion —
elements of finite order — which no rank records. The matrix in the hero has rank six over ℚ, so its
image spans the whole space over the rationals; over the integers its image is an index-12 subgroup,
and the 12 is the product of its invariant factors — which is the determinant, and is why an integer
matrix’s determinant measures a volume in a sense that survives having no real entries at all.
So there are three separate quantities and the word “rank” is used for the first two:
the rank over ℚ, which is how many rows are independent when division is allowed;
the rank over 𝔽ₚ, which is that count when arithmetic is done modulo p;
and the full invariant-factor list, which is what the map over ℤ actually is, and of which both
ranks are shadows.
The third is the subject of the next essay, and once it is in hand the first two stop being separate
facts: the rank over ℚ is the number of nonzero invariant factors, and the rank over 𝔽ₚ is the number
of them p does not divide.
There is a practical reading of all this that does not require caring about finite fields, and it is
the one worth carrying out of the essay.
A rank returned by any routine is a rank with respect to something, and the something is rarely
printed. In floating point it is a threshold, usually a multiple of the largest singular value and
the machine epsilon, and the essays on that argue it should be printed beside the answer. In exact
modular arithmetic it is a prime. In exact rational arithmetic it is the rationals, which is the only
case where the parameter is the one almost everybody meant — and it is also the most expensive case,
which is why library routines are rarely doing it.
So a rank is three things at once: a number, a ring, and in the floating-point case a tolerance. Two
of the three are usually thrown away before the number reaches the caller, and both of the discarded
ones can change the answer.
And the two failure modes do not overlap, so neither defends against the other. Exact arithmetic
removes the threshold and leaves the ring; a well-separated gap removes the ambiguity in the
threshold and says nothing about the ring; and a matrix can be badly conditioned over ℝ and perfectly
well behaved over 𝔽ₚ, or the reverse. There is no single computation that settles rank once, and the
useful question is always which of the three quantities the application actually depends on.
The cost, which is why anybody does this modulo p #
The reason a modular rank is computed at all is the reason the whole modular route exists: no growth.
An exact rank over ℚ by fraction-free elimination forms intermediates of the determinant’s own
length, so on a matrix with three-digit entries at n = 12 it is doing arithmetic on 121-bit integers.
The same elimination modulo a 26-bit prime is doing arithmetic on machine words throughout, and it is
the same n³/3 operations. The ratio is the length, exactly as it was for the determinant.
So the working method is the one the asymmetry suggests: compute the rank modulo a couple of primes,
take the largest answer, and — if the application needs certainty rather than a lower bound — pay for
one exact elimination to confirm it. The modular passes are nearly free and they say what the answer
probably is, which is what makes the expensive confirmation short.
That is the same two-stage shape as almost every expensive computation on this site: a cheap
estimate that is usually right, and an expensive verification that is run once. What is different
here is that the cheap stage’s failure is not an inaccuracy — it is an integer that is too small by
one, arrived at exactly, and the only thing that reveals it is a second cheap stage disagreeing.
Fig. 4 The length the exact route carries and the modular route does not, on the family where the difference
is largest.
The first attempt at this figure did what would occur to anybody: take a random integer matrix, make
two of its rows dependent so the rank over ℚ drops, and hope that a small prime drops it further.
It does not. A matrix built by adding rows has rank deficiency over every ring at once, because the
dependency it carries has integer coefficients and reduces modulo anything. The measurement came back
with the same rank at every prime, and the figure had nothing to show — which is the correct outcome
for that construction and would have been read as evidence for the claim the essay exists to refuse.
What is needed is a dependency that exists modulo p and not over ℚ, and there is exactly one way to
arrange one: an invariant factor divisible by p. So the construction starts from the invariant
factors and works outwards — diag(1, 1, 1, 1, 2, 6), then two unimodular conjugations to hide it —
and the ranks at 2, 3 and every other prime are known before anything is computed.
That is the general rule this field keeps rediscovering. A counterexample found by looking is
evidence that one exists; a counterexample built from the property is evidence about the property, and
it can carry an assertion. Here the assertion is three exact equalities — rank n−2 modulo two, n−1
modulo three, n at every other prime tried — and a build in which the construction stopped having
that structure would fail rather than produce a less interesting picture.
Fig. 5 The invariant factors computed two ways at the smallest size the definition is affordable at: by
unimodular elimination, and by the gcds of every minor of each order.
Fig. 6 The smallest size the construction exists at, where the ranks are four, three and two.Fig. 7 Order nine, where the two small primes still lose one and two and nothing else changes.Fig. 8 Order seven, with the same invariant factors placed in a larger matrix.Fig. 9 Six invariant factors, computed by an algorithm and by the gcds of the minors.Fig. 10 Pascal, whose determinant is 1, so every invariant factor is and no prime is unlucky for it at all.Fig. 11 The determinant version of the same substitution, at the primes dividing the last invariant factor.Fig. 12 The threshold version, which is the failure this one is not.Fig. 13 A rank as a band of plausible values, which an exact rank never is.Fig. 14 What a greedy pivot rule can see of a gap, in the field that measured it.Fig. 15 The growth an exact rank carries and a modular one does not.Fig. 16 The determinant, which is the product of the invariant factors this essay is about.Fig. 17 The answer’s own length, on a system this elimination would be the first step of.Fig. 18 Order five, where the ranks are five, four and three.Fig. 19 The construction at its drawn size, with three distinct answers.Fig. 20 Invariant factors on wide entries, where only the last is not 1.Fig. 21 A unimodular map, whose rank is the same over every ring.Fig. 22 The determinant version of the same substitution.Fig. 23 The determinant, which is the product of the invariant factors.Fig. 24 What an exact rank over the rationals costs in length.Fig. 25 The budget a modular rank does not have and does not need.Fig. 26 The answer a full-rank system of this kind produces.Fig. 27 The lattice whose quotient the invariant factors describe.Fig. 28 The largest size drawn, where the two small primes still cost one and two.Fig. 29 The smallest size the definition by minors runs at.Fig. 30 An ill-conditioned integer matrix’s invariant factors.Fig. 31 The determinant version, at order eight.Fig. 32 The product of the invariant factors, three ways.Fig. 33 The length an exact rank over the rationals carries.Fig. 34 The elimination whose zero pivot is a rank statement.Fig. 35 A full-rank system’s answer, in bits.