An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left. The cost does not vanish with the error. It moves into the length of the numbers, where three correct routes differ by four orders of magnitude.
Every field before this one is about an arithmetic that cannot represent its own answers. A float
has fifty-three significand bits, the exact result of almost any operation on two of them does not
fit, and the whole apparatus of this site — a backward error saying what the algorithm did, a
condition number saying what the problem did to it, and their product being all anybody sees —
exists to account for the difference.
There is a class of problems where none of that applies. If a matrix has integer entries and the
question is its determinant, its rank, or the solution of a system it defines, then every quantity
involved is a rational number, every arithmetic operation on rationals produces a rational, and an
elimination performed in them rounds nothing at any step. The forward error is zero. The
backward error is zero. The residual is the zero vector, not a small vector. The condition number
is a perfectly good number and it multiplies nothing.
Fig. 1 Three exact eliminations of one twelve by twelve integer matrix, plotted against the length of the
widest number each one forms. Every route returns the same determinant, so there is no error to
draw and the vertical axis is bits.
So the interesting question is not whether it works. It is what it costs, and the answer is the
subject of this field: the cost stops being a count of operations and becomes the length of the
numbers those operations are performed on.
The relation the rest of this site reports every measurement against is
forward error ⪅ condition number × backward error
and the essay that introduced it is careful that
both factors are separately measurable. Here the right-hand side is zero because its second factor
is, and a product with a zero in it carries no information about the other one. The matrix above has
a two-norm condition number of 32.7. That is a true statement about the matrix and it predicts
nothing at all about the computed answer, because the computed answer is the answer.
This is not a rhetorical point. It changes what a figure in this field can be. There is no residual
badge to print, because ‖PA − LU‖ is a matrix of exact zeros at every size and on every family, and
a badge reading 0 on nine consecutive figures tells a reader nothing they did not know from the
first. What can be measured is on the vertical axis of the hero: the number of bits in the widest
integer the routine had to hold.
Take a twelve by twelve matrix whose entries are integers between −9 and 9. Its determinant is
2,269,932,161,262 — twelve digits, forty bits, and small enough to write on a line. Three routes
reach it:
Fraction-free elimination, which stays in the integers by dividing each step by the previous
pivot. The widest number it ever forms is 40 bits.
Elimination over the rationals with every fraction reduced to lowest terms, which reaches
39 bits and calls a greatest common divisor on every entry it forms to stay there.
Elimination over the rationals without reducing, which is the routine anybody writes first:
numerator times numerator, denominator times denominator, subtract with a common denominator. It
reaches 1,422,165 bits.
Fig. 2 The same determinant computed four ways. The three exact routes differ by exactly zero, as
integers rather than to a tolerance; the floating-point LU differs in the last digits because the
answer needs forty bits of significand and it has fifty-three of them holding a product of twelve
pivots.
A million and a half bits is four hundred and twenty-eight thousand decimal digits, carried in order
to compute a twelve-digit answer. Nothing about that is a rounding error, a stability question or a
choice of pivot. All three routes are correct. All three return the identical integer. They differ
by a factor of thirty-five thousand in the size of the objects they manipulate, and the flop count —
which is the same n³/3 for all three — sees none of it, exactly as
the flop count fails to predict the time for a
different reason two fields over.
That is the field’s organising fact, and it can be stated in one line: an operation on a
forty-thousand-bit integer is not one operation.
The mechanism is worth writing out because it is short and because it is the reason the other two
routes exist.
At each elimination step, an entry becomes aᵢⱼ − (aᵢₖ/aₖₖ)·aₖⱼ. Written over a common denominator
with no cancellation performed, the new numerator is a product of two previous numerators minus
another such product, and the new denominator is a product of two previous denominators. So if
every entry has b bits before the step, every entry has about 2b after it. Twelve steps of doubling
from four bits is 4·2¹² = 16,384 — and the measured figure is larger still, because the subtraction
of two products of different denominators multiplies them.
Nothing cancels unless something is asked to cancel. The fractions are in lowest terms after the
last step, in the sense that the determinant comes out as an integer over one; they are simply never
put there on the way.
Fig. 3 The same measurement stopped at n = 8, where the unreduced route is at 4,938 bits and the other two
are at 24 and 23. The separation is already three orders of magnitude and the curves have not begun
to be dramatic.
So the obvious repair is to reduce, and it works: the reduced route’s widest intermediate is 39 bits
at n = 12, one bit narrower than the fraction-free route’s. What it costs is that every addition,
every multiplication and every subtraction is followed by a greatest common divisor of two integers
— and a gcd is not a constant-time operation
any more than a multiplication of two long integers is. The reduction is exactly the work the
unreduced route was avoiding.
That fork — pay in gcds or pay in length — is the first of the field’s three answers, and the second
is the one that makes it unnecessary.
and never leaves the integers, because that division is exact at every step of every matrix. It is
not exact by luck and it is not exact because of anything about these entries. It is exact because
the numerator, before the division, is a determinant with the previous pivot as a factor — which is
Sylvester’s identity, and which the next essay in this field checks against the minors themselves
rather than quoting.
The consequence for cost is immediate. Each intermediate entry is a minor of the original
matrix, so its size is bounded by Hadamard’s bound on a minor of that size, which grows like
k·(entry width + log k) — linearly in the step index, not exponentially. That is the flat lower
group of curves in the hero, and it is why the fraction-free route needs no gcds: the division that
keeps the numbers small is a single exact division rather than a search for a common factor.
Fig. 4 A five by five matrix and its state after two fraction-free steps. Every boxed entry is a three by
three minor of the matrix on the left, checked against a cofactor expansion rather than against a
second elimination, and every division that produced it came out whole.
The third route removes growth entirely by removing the room for it: work modulo a prime that fits
in a machine word, where no entry can exceed the modulus, and put the answer back together from
several such computations by the Chinese remainder theorem.
That only works if the number of primes is known in advance, and it is, because Hadamard’s bound
says how large a determinant can be before any of it is computed: |det A| is at most the product of
the row two-norms. On the matrix above the bound is 52 bits and the answer occupies 40, so two
twenty-six-bit primes suffice and the routine uses two.
Fig. 5 Hadamard’s bound in bits against the determinant’s actual length, on four families. The gap between
a solid line and its own dotted one is the waste in the budget — smallest where the entries are
large and used, largest on a family whose determinant is 1 at every size.
The bound is not loose by construction, which matters, because a budget derived from a bound that
is never attained would be a budget that is always wrong. On a Sylvester Hadamard matrix of order
eight the bound is 25 bits and the determinant occupies 25: the bound is reached. On the Pascal
matrix, whose entries reach twenty bits at n = 12 and whose determinant is exactly 1, the bound is
149 bits and the answer is one. Both are correct behaviours of the same inequality, and the second
is the field’s standing warning that entry growth during an elimination is not predicted by the
size of the answer.
Three things this site has said elsewhere survive into the exact setting unchanged.
Two routes to every number. The habit is stronger here rather than weaker: two floating-point
routes to a quantity agree to a relative 10⁻¹⁵ and the essays price the last digit, but two exact
routes agree or they do not. There is no tolerance in the comparison and nothing to negotiate. The
determinant above is checked three ways and the differences are the integer zero.
A rank is still a decision, and now for a different reason.The essay that made
that argument made it about a threshold: a floating-point matrix has
singular values and no rank, and the rank is where somebody puts a line. Remove the arithmetic error
and the threshold goes away — and the answer still is not a property of the array of numbers,
because it depends on the ring the entries are read in. That is later in this field and it is a
genuinely separate failure, closer to
a rank that depends on the thread count than to
a threshold.
An exact answer to the wrong problem is still wrong. The whole apparatus of conditioning
survives, because it was never about arithmetic. It is about the map from data to answer, and if the
data was measured rather than given then the exactness buys nothing at all: the field’s last essay
measures a case where an exact solve and a float solve of the same physically-obtained system differ
by less than either differs from the truth.
Fig. 6 The same three routes on a family with three-digit entries, where the determinant occupies 82 bits
and the floating-point LU no longer has the significand to hold it. Four primes are budgeted rather
than two.
The comparison in that figure is worth reading carefully, because it is the only place in this field
where floating point appears at all.
A determinant of 2,269,932,161,262 needs 40 bits. A double has 53, so the answer fits — and the
float LU still misses it, by a relative 10⁻¹⁵, because the answer is not what is being held. What is
being held is a running product of twelve pivots, each of which is a quotient of quantities that do
not fit, and the last digits of that product are the ones the
cancellation took. Raise the entries to three digits and
the determinant needs 82 bits, at which point no amount of care in the elimination can help, because
the destination has 53.
That is the honest boundary of the field. Floating point is not bad at this; it is answering a
different question, at a fixed precision, for a fixed price. Exact arithmetic answers the asked
question at a price that depends on the answer’s own size — and once that size passes the
significand, the two are not competing.
The first version of the swell figure plotted the reduced-rational route as the villain, on the
strength of the phrase intermediate expression swell, which is what the literature calls this.
The measurement refused it. The reduced route sits at 39 bits at n = 12, one bit below the
fraction-free route, and at 13 bits at n = 6 where fraction-free is at 16 — narrower than the
answer’s own length, because reducing a fraction whose value is small can throw away a great deal.
The swell belongs to the elimination without the gcd, and the two are separate routines that get
called by the same name. Stating it as a property of “rational arithmetic” would have been a claim
that a five-line change to the inner loop falsifies. What the measurement supports is the fork: the
cost is length or it is gcds, and fraction-free elimination is the third road that pays neither.
Fig. 7 On three-digit entries the same picture, shifted up. The lower group starts higher, because the
answer is longer, and the separation between the groups is unchanged, because the doubling per step
does not know how large the entries were.
Four things are true here that are true nowhere else on this site, and they are why the field
exists rather than being a paragraph in the elimination one.
The answer is a certificate. Not a value with an error bar and not a value with a residual — an
integer, which either is or is not the determinant, and whose correctness is a statement about
arithmetic rather than about a tolerance. The interval-arithmetic
essays reach a proved enclosure of a real answer; this reaches the
answer.
The cost model is a different one. Everything else on this site counts operations and then
argues about where the time actually went — cache, bandwidth,
messages. Here the flop count is wrong before any of that, because the operands have lengths, and
the length is decided by the algorithm rather than by the machine.
The failure mode is size, not accuracy. A routine here does not return a bad answer; it returns
the right one after allocating a gigabyte, or it does not return. That is a different thing to
engineer against, and the engineering is Hadamard’s bound and the modular route.
And the ground truth this site has used all along lives here. The Hilbert inverse in closed form,
the spanning-tree count from a determinant, the effective resistance as a ratio of two integers:
each of those is a float measurement checked against an exact
one, and the exact one was computed by the routines this field is about. The instrument has been in
use since the collection’s first essays. This is the field that measures the instrument.
Fig. 8 The Pascal family, whose determinant is 1 at every size while its entries reach twenty bits. The
lower group is flat at one bit and Hadamard’s bound climbs away from it.Fig. 9 Unit lower triangular: the elimination has nothing to do, so every curve is flat and the figure is
the floor any growth is measured against.Fig. 10 A determinant of exactly 1, budgeted at 106 bits because the rows are long.Fig. 11 Small enough that the float route is exact too, which is the only regime in which the four bars
agree.Fig. 12 One step, on a four by four, where every boxed entry is an ordinary two by two determinant.Fig. 13 Three steps on Pascal, where the minors are all 1 and the elimination visibly does no work.Fig. 14 The budget out to n = 13, where the wide family needs six primes and the random one three.Fig. 15 The instrument this field measures: a float Hilbert solve against the rational answer.Fig. 16 The identity with both of its factors, in the field where they are not zero.Fig. 17 A small residual and a large forward error, which is the situation this field cannot be in.Fig. 18 The amplifier that belongs to the problem, and survives the arithmetic being exact.Fig. 19 The elimination field’s own bound that is never attained, against Hadamard’s, which is.Fig. 20 The site’s precision knob, which this field has removed.Fig. 21 The cancellation that takes the last digits of a float determinant, in the field that named it.Fig. 22 Rank as a threshold, which is the version of the question this field replaces.Fig. 23 Fill in a sparse elimination, which is the other way an intermediate becomes larger than its input.Fig. 24 Seven by seven, where the unreduced route is already at 711 bits and the others at 24.Fig. 25 Three-digit entries out to twelve, where the answer needs 121 bits and the budget six primes.Fig. 26 A determinant of exactly 1, reached by every route including the float one.Fig. 27 The integer Hilbert matrix, where conditioning costs the float route and nothing else.Fig. 28 The budget at small sizes, where one prime does for every family.Fig. 29 Six by six after two steps, where every boxed entry is a three by three minor.Fig. 30 The other floor: how long the answer to a system of this kind is.Fig. 31 The invariant factors of a matrix of this family, which its determinant is the product of.Fig. 32 The risk the modular route runs in exchange for having no growth.Fig. 33 A well-conditioned system, where the exactness and the data agree about the answer.Fig. 34 Five by five, where the unreduced route first leaves the group.Fig. 35 Pascal at nine, a determinant of one under a bound of eighty bits.Fig. 36 Three-digit entries at order six, budgeted at three primes.Fig. 37 The case where Hadamard’s bound is attained rather than satisfied.Fig. 38 Wide entries, three steps in, every division still exact.Fig. 39 The budget out to twelve, where the families have separated completely.Fig. 40 The invariant factors of a wide matrix, one of them fourteen digits.Fig. 41 The bound the modular route’s second stage works to.