The rank depends on the ring

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.

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.

Three ranks, none of them a judgement #

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.

It is worth pausing on how unlike the site’s usual findings that is. Almost everything here is about an implementation failing to deliver what the algebra promised — orthogonality that is not orthogonal, a residual that is small while the error is not, an eigenvalue moved by the eighth root of a perturbation. In every one of those the algebra is unambiguous and the arithmetic falls short. Here the arithmetic is perfect and the algebra is ambiguous: the question has a parameter nobody supplied.

Where the different answers come from #

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.

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.

What the elimination looks like when it happens #

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.

What a modular rank is good for anyway #

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.

Two of the eight fields sit below the rational rank at every size, and it is the same two, by the same amounts.

The rank over ℤ, which is a third thing again #

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.

What a numerical analyst should take from it #

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.

How many “a couple” is #

That phrase is doing work and it deserves a number, because the answer depends entirely on how large the primes are and the essay above has been drawing pictures with small ones.

Over three hundred random 6×6 integer matrices with entries in [−9, 9], against the true rank read from the invariant factors:

at least one of the first twelve small primes unlucky      282 of 300   (94%)
p = 2 alone gives a rank below the true one                205 of 300   (68%)

largest of the first k small primes reaches the true rank:
   k = 1    32%          k = 4    99.0%
   k = 2    66%          k = 5    99.7%
   k = 3    93%          worst case in the sample: 7

On small primes an unlucky one is the rule and not the exception. That is arithmetic rather than bad luck: an invariant factor is even about half the time, and every even one costs p = 2 a rank, so the smallest prime is wrong more often than it is right. Two small primes still leave a third of the matrices short by one, and five are needed to be right ninety-nine times in a hundred.

At word size the question evaporates. Not one of the same three hundred matrices has an unlucky prime among the first four 26-bit ones — an invariant factor is divisible by a 26-bit prime with probability about 1.5·10⁻⁸, and there are six of them to miss.

So the method is sound and the phrase is not: the number of primes needed is a property of their size, and “a couple” is the answer only for large ones. A routine reading small primes because they are convenient to compute with is choosing the regime where the failure it is defending against happens to almost every matrix it will see.

That is worth stating carefully because it cuts against the pictures in this essay. The hero draws 𝔽₂ and 𝔽₃ because they are the primes at which the construction’s ranks differ visibly; a reader could take from it that unluckiness is a curiosity of a constructed matrix. It is not — at those primes it is what happens to a randomly chosen integer matrix two times in three. What is a curiosity is finding it at 65,537.

There is a second reading of the same table that the earlier sections set up and did not close. The essay says a modular rank is a lower bound, and that the maximum over several primes is therefore the right thing to take. The measurement says how good that lower bound is as an estimator, which is a different question and the one an implementation needs: at one small prime the bound is loose 68% of the time, at three 7%, at five 0.3%. Every one of those failures is short by exactly one, because two invariant factors sharing a small prime is much rarer than one doing so — which is why the curve rises so steeply and why a matrix needing seven primes appeared once in twelve hundred.

The practical instruction that comes out of it has the same two-stage shape the essay already describes and a sharper first stage: take the largest rank over four or five primes if they are small, or over two if they are word-sized, and treat disagreement between any two of them as the signal to run the exact elimination. Disagreement is not rare on small primes — it happens to most matrices — so on small primes that signal fires constantly and the second stage stops being occasional. That is the real argument for word-sized primes, and it is about how often the expensive path is taken rather than about how fast the cheap one is.

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.

The construction, and why it had to be built #

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.

The deficiency belongs to the prime and not to the matrix’s size. 𝔽₂ loses exactly two at every one of the six sizes and 𝔽₃ loses exactly one, while the six larger fields lose nothing at any of them. Six sizes, eight rings, forty-eight exact eliminations, and the pattern is the same three columns shifted upward by one each time n grows.

Which is the assertion two paragraphs up, drawn rather than stated. The dek quotes the n = 6 case — “rank six over the rationals, five modulo three and four modulo two” — and one matrix reads as a curiosity, the sort of thing that might be an artefact of a particular six-by-six. The assertion says it is not, and the six frames are what makes that visible to a reader rather than to a test: the ring contributes a fixed amount to the answer, and which amount depends on which prime divides the last invariant factor, which is what the invariant-factor figure earlier on this page is about.