An exact solution of an integer system is a vector of fractions, each of them a ratio of two determinants. So the output carries 2n long integers where the input carried n² short ones, and no algorithm can write it down more cheaply — the length of the answer is a floor under every exact solver rather than a property of one.
The first two essays in this field were about intermediates: numbers the algorithm forms on the way
and could in principle avoid forming. Fraction-free elimination avoids most of them, the modular
route avoids all of them, and the difference between the best and worst arrangements of the same
arithmetic was four orders of magnitude.
This essay is about the number that cannot be avoided, because it is the answer.
Fig. 1 An eleven by eleven integer system: 484 bits of question, 729 bits of answer. Every entry of the
solution is a ratio of two determinants, and the lower curve is the determinant’s own length, which
is what each of those parts costs.
Solve Ax = b with A an integer matrix and b an integer vector. The solution is a vector of rational
numbers, and Cramer’s rule says exactly which ones:
xᵢ = det(Aᵢ) / det(A)
where Aᵢ is A with its i-th column replaced by b. That is usually quoted as a terrible algorithm,
which it is — n+1 determinants where one elimination would do. Read as a statement about the
answer rather than about a method, it is not an algorithm at all and it is exact information
about how large the output must be.
Every entry has a denominator dividing det A. So no denominator is longer than det A, and the whole
vector is 2n integers each of at most that length. On a matrix with b-bit entries det A has about
n(b + ½log n) bits, so the answer occupies roughly 2n²·b bits where the question occupied n²·b.
That is checked here rather than quoted. Each computed entry is multiplied back by det A and the
product compared, as an integer, with det(Aᵢ) computed independently. They agree at every size, which
means the reduced fraction really is that ratio and the denominator bound really does hold. It is the
same shape of check the field uses everywhere — an algorithm against a
definition rather than against a faster version of itself —
and here the definition is a rule from 1750 that nobody computes with.
The natural thing to assert is that no part of the answer is longer than det A. It is false, and the
measurement said so: on an eleven by eleven the widest numerator is 37 bits against a determinant of
33.
The reason is immediate once it is seen. The numerator is det(Aᵢ), a determinant of a different
matrix — one column of A swapped out for b — and if b has larger entries than that column did, that
determinant can be larger. What is exactly true is the denominator statement, because the reduced
denominator divides det A and division cannot lengthen an integer.
Fig. 2 Three-digit entries, where every part of the answer is longer and the ratio between the two curves is
unchanged. The size of the entries shifts both curves and does not tilt either.
That distinction matters for the field’s cost model. A solver can be judged against the length of the
answer, and the answer’s length is a known function of the matrix — but the function is
max over i of the length of det(Aᵢ), not the length of det A, and a bound written for the second is
wrong for a right-hand side with large entries in it.
The distinction between an intermediate and an output is the whole reason this essay is separate from
the two before it.
An intermediate is a choice. Unreduced rational elimination forms 1,422,165-bit numbers on a twelve by
twelve; fraction-free elimination forms 40-bit ones; both return the same answer, so the million and a
half bits were never necessary. That is the shape of every performance argument on this site — the
same result, at a different price, because of how the work was arranged.
An output is not a choice. If the answer is 729 bits then any routine that produces the answer
produces 729 bits, and a routine that produces fewer has produced something else. There is no
arrangement of the arithmetic that gets under it and no cleverness that helps.
So the exact-arithmetic cost model has two floors under it and they behave differently. The intermediate
floor is the answer’s own length, reached by fraction-free elimination and by the modular route, and
the distance from an algorithm to that floor is the algorithm’s fault. The output floor is the answer’s
own length again, and nothing is anybody’s fault.
Fig. 3 The intermediate picture from the field’s first essay, for comparison: the lower group is at the floor
and the upper curve is a choice about the inner loop.
Two consequences follow directly, and both are visible in what the field’s routines actually do.
A modular route must reconstruct rather than eliminate to the end. Working modulo primes keeps
every intermediate under 26 bits, which is the whole advantage — but the answer has 729 bits in it, so
those bits have to come from somewhere. They come from combining many residues, and the combination is
the Chinese remainder theorem for a determinant and rational reconstruction for a solution. The output
floor is why the modular route has a second half at all.
A returned inverse is n times worse than a returned solution. An exact inverse of an integer matrix
is a matrix of n² rationals, each a ratio of an (n−1) × (n−1) cofactor to det A. So it occupies about
2n³·b bits against the solution’s 2n²·b — and the essay that argues against forming an
inverse makes the case in floating point on grounds of
stability and operation count. Here the argument is shorter and harder: the object is n times larger
than the question, and the size is not negotiable.
Fig. 4 The integer Hilbert family — the classical ill-conditioned matrix, cleared of denominators — where
the answer is short because the system was built to have one, and the determinant is long anyway.
The hero’s two curves are worth reading as numbers rather than as slopes, because the ratio between
them is the whole quantity and it moves slowly.
At n = 3 the question is 27 bits and the answer 33, a ratio of 1.22. At n = 7 it is 196 against 292,
a ratio of 1.49. At n = 9 it falls back to 1.40 and at n = 11 it is 484 against 729, a ratio of 1.51.
The answer is about half again as long as the question, the factor climbs slowly, and it is not
monotone — the ninth case is below the seventh, because the length of a determinant is the length of
one particular integer and one particular integer can be small. Both quantities are n² times
something and the somethings differ by a logarithm.
That is a much less dramatic statement than the four orders of magnitude the intermediates gave, and
it is deliberately reported that way. The field’s headline number belongs to a choice about the inner
loop; this one belongs to the problem, and it is small. A reader who took away only exact arithmetic
is expensive because the numbers get long would have the intermediate story and the output story
confused, and would conclude that exact solving is infeasible when what is infeasible is one
particular arrangement of it.
An answer that is short for a matrix that is not #
The families separate two things this essay could otherwise be read as conflating.
The unit triangular family has a determinant of 1 at every size, so every denominator is 1 and
every entry of the solution is an integer. The answer is genuinely short — it is as short as the
right-hand side — and the question is the usual size. There is no floor to speak of, and there is
also no work: the system is already solved.
The Pascal family also has a determinant of 1, and its entries reach twenty bits by n = 12. Here
the denominators are all 1 and the numerators are not: the answer is a vector of integers whose
lengths come from the entries rather than from the determinant. So an answer can be long because the
matrix is large, or because the determinant is, and these two families separate the causes.
Fig. 5 Pascal, where every denominator is 1 because the determinant is, and the answer is still not short.
The general statement is the one Cramer’s rule gives and neither family contradicts: the answer’s
length is decided by the determinants of the column-replaced matrices, and those are bounded by
Hadamard, and the bound is attained on some families and enormously slack on others.
The right-hand side is part of the question, and it is usually forgotten #
There is a practical consequence of the numerator being det(Aᵢ) rather than anything about A alone,
and it is the kind of thing that turns up as a surprise in a running system.
Scale the right-hand side by an integer c. The matrix is untouched, the determinant is untouched, and
the solution is exactly c times what it was — so every numerator has grown by the length of c and
every denominator has not. A system solved with a right-hand side in millimetres and the same system
solved with the same right-hand side in nanometres produce answers of different lengths, by twenty
bits an entry, for the same physical question.
In floating point that is invisible: a scaling of b is a scaling of x, the relative error is
unchanged, and the essay on units and conditioning
makes the case that only a scaling of the matrix can move anything that matters. Exactly, the
units reach the cost. They do not reach the accuracy, because there is none to reach — they reach the
number of bits the answer occupies and therefore the time and the memory.
The repair is the obvious one and it is worth stating because it is not obvious that it is needed:
divide out the content of b before solving, and multiply it back afterwards. It is free, and nothing
in the arithmetic will ever tell anybody it was skipped.
Two determinants, and one of them is usually enough #
The denominator of every entry divides det A, so all n entries share a denominator, and that changes
what the answer should be returned as.
A vector of n independent fractions is 2n integers. The same vector written as a single integer vector
over one common denominator is n+1 integers, and the common denominator can be taken as det A
itself — which is a number the solver computed anyway. So the natural exact return type is not
a list of fractions; it is a pair, an integer vector and one scalar, and it is about half the size.
That representation is also what makes the answer checkable in integers. With x = y/d for an integer
vector y and an integer d, the statement Ax = b becomes
A·y = d·b
which is an identity between integer vectors: no division, no rationals, no tolerance. It is the
strongest form of verification available anywhere on this site — stronger than a residual, because a
residual is a small number that somebody has to decide is small enough, and this is an equality
between two lists of integers.
Fig. 6 The determinant that serves as the common denominator, computed three ways. It is the one number the
whole answer is written over.
The output floor is a different kind of statement and there are only two others like it here. One is
the storage a hierarchical format needs,
where a rank decides how many numbers there are and no arrangement changes the count. The other is
the border-rank sequence, where getting one digit closer
costs a fixed factor in the size of the terms, for ever, because that is what the approximation is.
In each case the quantity being paid for is the answer rather than the route to it, and
the fill an elimination produces is the near miss worth
naming: that one looks like an output floor and is not, because a different ordering changes it.
The correct response to a real one is not a better algorithm. It is to ask whether the answer that long is the answer that was
wanted — which for an exact solve very often it is not, and the field’s last essay is about the case
where it certainly is not.
Fig. 7 The case where paying for an exact answer buys nothing: data measured to ten digits, an exact solve
with a zero residual, and an answer wrong in the first.
The output floor is the reason the modular route is a two-stage algorithm rather than a one-stage one,
and the stages have completely different characters.
The first stage is arithmetic modulo a prime, where nothing grows, everything is a machine word, and
the whole computation is as fast as a float elimination and rather more predictable. Done once it
produces a solution vector modulo p, which is n residues — n·26 bits, a fraction of the answer’s
size, and useless on its own.
The second stage is recovery, and it is where the answer’s length gets paid for. There are two
routes and the field takes both: combine enough residues by the Chinese remainder theorem until the
product of the moduli passes Hadamard’s bound, which reconstructs an integer; or solve modulo a
single prime power, lifting digit by digit, and recover the rational from its residue. The first
needs a bound on the answer, the second needs a bound on both parts of each fraction, and both bounds
come from the same place.
What neither can do is reconstruct an answer that has more bits in it than the moduli supply. That is
the output floor showing up as an arithmetic condition rather than as a philosophical one, and it is
the subject of the three essays that follow.
Fig. 8 The budget the first route works to: enough primes that their product exceeds the bound on the answer,
decided before any residue is computed.Fig. 9 And the condition the second route works to: below a modulus twice the square of the longer part,
the residue does not determine the fraction at all.
Fig. 10 Unit triangular: every denominator is 1, the answer is an integer vector, and the two curves nearly
meet.Fig. 11 Out to thirteen, where the question is 676 bits and the answer a little over a thousand.Fig. 12 The ill-conditioned family at small sizes, where the determinant is already thirty bits.Fig. 13 The determinant that every denominator divides, reached three ways.Fig. 14 And on the ill-conditioned family, where the float route has lost the answer entirely.Fig. 15 The intermediates on the same family, where the fraction-free route still tracks the answer.Fig. 16 Hadamard’s bound, which bounds the numerators of the answer as well as the intermediates.Fig. 17 The last fraction-free step, where the single surviving entry is the determinant every denominator
divides.Fig. 18 Wide entries out to twelve, where the answer passes a thousand bits.Fig. 19 An exact Hilbert solution used as ground truth, which is an answer of exactly this shape.Fig. 20 The float argument against forming an inverse, which this essay makes on size instead.Fig. 21 Another output floor: a format whose storage is decided by a rank rather than by an arrangement.Fig. 22 The amplifier that decides whether an answer this long was worth computing.Fig. 23 Small systems, where the ratio between question and answer is 1.49.Fig. 24 Pascal, where every denominator is 1 and the numerators still grow.Fig. 25 The intermediates, which are a choice, beside an answer that is not.Fig. 26 A determinant of 1, so every denominator of the answer is 1 as well.Fig. 27 The elimination whose last entry is the common denominator.Fig. 28 The bound on the numerators as well, taken over the column-replaced matrices.Fig. 29 The invariant factors whose product is that denominator.Fig. 30 Whether an answer this long was worth computing, on a well-conditioned system.Fig. 31 The modular route the output floor forces to have a second stage.Fig. 32 Rank over three rings, which the same elimination decides.Fig. 33 The ill-conditioned family, whose determinant is long at every size.Fig. 34 The smallest sizes, where the ratio is 1.22.Fig. 35 The intermediates on wide entries.Fig. 36 The determinant every denominator divides, on a wide matrix.Fig. 37 The elimination that produces it.Fig. 38 The bound on both parts of every entry.Fig. 39 The invariant factors of an ill-conditioned integer matrix.Fig. 40 The reduction the reconstruction step is, in two dimensions.