A modular elimination reports a singular matrix and is telling the truth — over the field with p elements the matrix is singular. Over the rationals it is not. Nothing in the residue distinguishes the two cases, no quantity is small enough to be suspicious, and the wrong answer is a correct computation of a different question.
Modular arithmetic buys the exact-arithmetic field its only route with no growth in it: work modulo a
prime below 2²⁶, and every quantity from the first step to the last is a machine word. The price is
paid in one place, and it is unlike anything else on this site.
Build a six by six integer matrix whose determinant is 30030. Reduce it modulo 3 and eliminate. The
elimination reaches a column of zeros and reports that the determinant is zero.
Fig. 1 The determinant is 30030 = 2·3·5·7·11·13, and its residue at twenty-five small primes. Five dots sit
on the floor. Each of them is a correct computation.
That report is true. Over the field with three elements the matrix genuinely is singular: its
rows are linearly dependent there, its rank is five rather than six, and every statement the
elimination made about it is right. What is wrong is nothing at all inside the computation. What is
wrong is that a caller asked about the rationals and was answered about 𝔽₃.
It is tempting to file this beside the site’s other zero-detection problems and it does not belong
there.
Deciding that a zero has arrived is about a quantity
that is 10⁻¹⁴ when the theory says zero, and about the judgement required to call it one.
Rank is a decision is the same judgement in its most consequential
form: a singular value of 10⁻¹² is not zero, calling it zero is a choice, and the choice is where the
rank comes from. In both cases there is a small number, somebody has to decide about it, and the
essay is about the decision.
Here there is no small number. The residue is the integer 0, exactly, arrived at by a sequence of
integer operations none of which rounded. There is nothing to threshold, nothing to be careful about,
and no amount of extra precision helps — extra precision is what this route already has infinitely
much of. The failure is not in the arithmetic’s accuracy. It is that a different question was
answered, correctly.
That makes it the second instance on this site of a class the graph field opened: a computation whose
output is right and whose subject is wrong. The first was
a partition decided in the last digit, where a
correctly computed eigenvector of a degenerate matrix yields a partition that is one of several and
the choice among them was made by rounding. Here the substitution is cleaner and more total: not one
of several answers, but the answer to a different question, and it does not even have the courtesy to
vary with the seed.
How likely it is, and why that is the wrong question #
A prime p is unlucky for a matrix when p divides det A. For a determinant D, the number of primes
below N that divide it is at most log₂|D|, so among primes near 2²⁶ the proportion that are unlucky
is about log₂|D| divided by the number of primes in the range — a probability of order 10⁻⁶ for a
forty-bit determinant, and smaller as the primes get larger.
The figure uses small primes deliberately, because at 26 bits the failure would be invisible and this
essay would have nothing to draw. Five of the first twenty-five odd primes divide 30030, which is a
rate of twenty per cent; at word-sized primes the same matrix would need millions of draws to hit
one.
Fig. 2 The same sweep taken further. The floor fills slowly and never empties: the six primes dividing the
determinant are the only ones that ever land there, and they are the first six.
The temptation is to treat that probability as a defence, and it is not one, for two reasons.
The determinant is not random and neither are the primes. A matrix arriving from a discretisation
or a combinatorial construction very often has a determinant with structure in it — a factorial, a
power of two, a product of small primes — and the implementations that use fixed prime tables use
the same primes every time. A rare event that is deterministic is not rare in the way the arithmetic
suggests: it happens to the same inputs every run, for ever.
And the consequence is not a small error. A single unlucky prime among k does not perturb the
reconstruction slightly. The Chinese remainder theorem combines residues that are jointly consistent
with exactly one value modulo the product, and one wrong residue gives a completely different value
— an integer with the right number of digits, none of them right, and no residual to notice it by.
What redundancy buys, and it is not what it looks like #
The defence is to compute more residues than the budget requires and compare. It works, and the way
it works is worth being precise about, because it is not error correction.
Reconstruct from the first k primes, where k is what Hadamard’s bound
required, and reconstruct again from k+1. If no prime was
unlucky, both reconstructions give det A and they agree. If one was, the two reconstructions differ,
because they are consistent with different values.
So the extra prime does not tell which residue was wrong, and it does not repair anything. It
converts an undetected wrong answer into a detected one, which in a field whose entire selling
point is that the answer is a certificate is the difference between the route being usable and not.
Recovering from it is a retry: drop the primes, take new ones, and the probability that two
independent draws are both unlucky is the square of a number that was already small.
Fig. 3 The reconstruction when nothing goes wrong: three routes, one integer, and the modular one assembled
from residues none of which is the answer.
There is a cheaper defence available for a determinant specifically and it is worth naming because it
does not generalise. If any single residue is nonzero then det A is nonzero, since a zero determinant
has zero residue at every prime. So a nonsingularity certificate needs one lucky prime rather
than a full budget — and a singularity claim needs the full reconstruction, because a matrix can
be singular modulo every prime anybody tried and not singular. The asymmetry is the useful part: one
of the two answers is cheap to prove and the other is not.
The determinant is the easy case, because it is one number and a wrong residue makes the whole
reconstruction disagree. The rank is worse.
Rank over 𝔽ₚ is computed by the same elimination and it is never larger than the rank over the
rationals — a dependency among rows over ℚ is a dependency over 𝔽ₚ, but not conversely. So a modular
rank is a lower bound on the true rank, and it is a silent lower bound: the elimination does not
report having lost anything, because from its point of view nothing was lost.
Which primes lose rank is not arbitrary either. It is exactly the primes dividing the invariant
factors of the matrix — the diagonal of its Smith normal form — which means the failure is a property
of the matrix’s structure rather than of the arithmetic. Two essays further on, the invariant factors
get computed for their own sake; here they are the answer to which primes are unlucky, and for
what.
Fig. 4 One integer matrix, its rank computed exactly over the rationals and over eight finite fields, with
no threshold anywhere. Three different answers.
There is a second modular strategy that avoids many primes entirely, and it meets the same problem in
a form that is easier to get wrong.
Instead of computing modulo p₁, p₂, … and combining, compute modulo a single prime power p, p², p⁴, …
by lifting: solve modulo p, use the residual to correct, solve modulo p again, and each round doubles
the number of correct p-adic digits. It is the exact-arithmetic analogue of
iterative refinement, and the analogy is close enough to be
useful and close enough to mislead.
Refinement in floating point converges when the residual is computed accurately enough and the matrix
is not too ill conditioned; it is a numerical statement with a numerical failure mode. Lifting
converges when the matrix is invertible modulo p, and if it is not, the very first solve fails and
nothing after it can recover. There is no gradual degradation and there is no conditioning: the
matrix is invertible mod p or the whole route is unavailable.
So the lifting route has to test one prime for luck at the start and can then forget the question,
where the spreading route has to worry about every prime it uses. That is a genuine advantage and it
comes with a matching disadvantage — one prime is one point of failure, and a prime chosen badly by a
fixed table is chosen badly every run.
Which primes are unlucky is a question with an exact answer #
The probability argument above is the one usually given and it is the weaker of the two available.
There is an exact characterisation, and it is worth stating because it turns a risk into a fact about
the matrix.
A prime p is unlucky for the determinant exactly when p divides det A. It is unlucky for the rank
exactly when p divides one of the invariant factors — the diagonal entries of the Smith normal form —
and the number of ranks lost is the number of invariant factors it divides. The matrix in the hero
has invariant factors 1, 1, 1, 1, 1, 30030, so the six primes dividing 30030 each cost it one rank
and nothing else does.
That is not an estimate and it does not involve a distribution. It means the set of unlucky primes is
a finite, computable, matrix-specific list, and that a routine which knew the invariant factors would
know exactly which primes to avoid. Of course computing them is harder than the determinant was —
which is the usual shape of these things, and is why the practical defence stays probabilistic.
What it does buy is the right mental model. An unlucky prime is not noise and it is not bad luck in
any useful sense; it is one of a handful of specific numbers attached to the matrix, and if the
matrix came from a construction with small numbers in it then those numbers are small.
Fig. 5 The invariant factors of a random integer matrix: five ones and one large factor carrying the whole
determinant. The primes dividing that last factor are the unlucky ones, and there are no others.
The practical upshot is a rule about interfaces, and it applies well outside this field.
A modular routine should not return “the determinant”. It should return the determinant together
with the modulus its answer is certain to, because that is what it actually knows — and a caller
that wanted a rational answer can then check whether the modulus was large enough while a caller that
wanted a residue can use it directly. Returning the number alone throws away the only information
that distinguishes a finished computation from an unfinished one.
That is the same complaint the essay about what a method
reports makes about an iterative solver returning its own
estimated residual as though it were the true one, and the same complaint
the certificate essays make about a routine that returns an answer
where it could have returned an answer and a proof. A number without its warranty is a number
somebody will use outside the range it was true in, which is the failure
the essay about a tolerance nobody meets describes from
the other end.
The cost of the defence, measured against what it defends #
The redundancy is one extra elimination out of k, so it costs 1/k of the route — three per cent on a
determinant needing thirty primes, thirty-three on one needing three. That is an unusual cost curve:
the check is cheapest exactly where the computation is largest, and most expensive on the small
problems where a fraction-free elimination would have been affordable anyway.
Which suggests the rule the field actually follows. Below the size where the modular route wins,
fraction-free elimination has no unlucky primes at all and
should be used; above it, the redundancy is nearly free and should always be taken. There is no
regime in which the modular route without a check is the right answer, and the reason is not caution.
It is that the middle regime — where the check is expensive — is exactly the regime where the other
route is available.
The claim this essay exists to break is the natural one: a nonzero determinant has a nonzero residue
at every prime, so a modular elimination reporting zero has found a singular matrix. It sounds like
a statement about arithmetic and it is a statement about nothing.
The construction that refuses it is built rather than searched for. Take diag(1, …, 1, 30030) and
conjugate it by two unimodular matrices — integer matrices with determinant ±1, so the Smith normal
form is untouched and the determinant is exactly 30030. The result is a matrix with no visible
structure, entries in the hundreds, nonsingular over ℚ, and singular modulo each of 2, 3, 5, 7, 11
and 13. The assertion is fed that matrix and has to reject it.
Searching random matrices for one would have made the figure a statement about the search. Building
it makes the six unlucky primes a stated property of the construction, which is what lets the figure
assert that the residue is zero exactly at the primes dividing the determinant rather than merely
observing that some are.
The distinction is the same one the site makes about every constructed counterexample. A matrix found
by looking is evidence that such matrices exist; a matrix built from a property is evidence about
what the property does, and it can carry an assertion that fails if the property stops holding. Here
the assertion is an equivalence rather than an example: the residue is zero at p if and only if p
divides the determinant, checked at every prime in the sweep, so a change to the construction that
broke the correspondence would be caught rather than merely making the picture less striking.
Fig. 6 The same construction at order four, where the determinant is unchanged because it is put there by
the diagonal rather than by the size.Fig. 7 Order eight, thirty primes, and the same five on the floor.Fig. 8 Sixty-four primes swept, of which the unlucky ones are still only the six smallest.Fig. 9 The rank over eight fields at order eight, where the two small primes lose one and two respectively.Fig. 10 And at order four, the smallest size the construction exists at.Fig. 11 The invariant factors, which are exactly what decides which primes are unlucky.Fig. 12 The budget that says how many residues are needed, and does not say whether any of them is
uninformative.Fig. 13 Four primes on a wide matrix, reconstructing an eighty-bit determinant from four twenty-six-bit
residues.Fig. 14 The floating-point version of a rank that is not a property of the matrix, which this one is not
either, for an unrelated reason.Fig. 15 A rank as a band rather than a number, which is the shape the float question takes.Fig. 16 A certificate that is not one, in the field that measures what checking costs.Fig. 17 Tests for singularity in floating point, none of which have this failure and all of which have
another.Fig. 18 The growth the modular route removes, which is what it is paying for this risk with.Fig. 19 Order five, where the construction puts the same six primes on the floor.Fig. 20 The largest sweep, fifty-four primes, and the same five unlucky ones.Fig. 21 The rank version of the same substitution, at order five.Fig. 22 And at order seven, where the two small primes still cost one and two.Fig. 23 Every invariant factor 1, so the set of unlucky primes is empty.Fig. 24 The budget, which counts residues and does not check any of them.Fig. 25 Three primes on a wide matrix, none of them unlucky.Fig. 26 What the modular route is buying with this risk.Fig. 27 The other bound the modular route works to.Fig. 28 The answer a solve has to reconstruct once the residues are in.Fig. 29 Order four, with the same determinant and the same six primes.Fig. 30 Order seven, fifty-four primes swept.Fig. 31 The smallest size the rank construction exists at.Fig. 32 And the largest drawn.Fig. 33 Invariant factors on wide entries.Fig. 34 A reconstruction from three residues, none of them unlucky.Fig. 35 The growth this risk is buying freedom from.Fig. 36 The budget, which counts and does not verify.