The answer is longer than the question

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.

What an exact solution is #

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 claim that had to be dropped #

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.

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.

Why this is a floor and not a cost #

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.

What it forces on the algorithms #

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 — measured below at 0.85n rather than n, for a reason worth having — 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.

The measurement, size by size #

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.

Four families at one size, and a size at one family #

The four frames above are drawn at four different n — eleven, ten, nine and twelve — because each was chosen to show its own family at its clearest. That makes them four good pictures and not a comparison, so here is the comparison, all four families at n = 11:

The ratio spans a factor of fifty-two, and it crosses one. On the wide and random families the answer is longer than the question, by a factor of two and a half in the first case. On the Hilbert and Pascal families it is shorter — thirteen times shorter and twenty-six times shorter — so the title is a statement about some matrices and its negation is a statement about others, on the same page.

The reason is that a short answer needs no more than a short answer. The Pascal matrix has an integer inverse, so the exact solution of a 2,178-bit question is 85 bits: a handful of small integers. Its question is long because binomial coefficients are large, and its answer is short because the arithmetic cancels almost all of that away. The wide family is the opposite — a 1,210-bit question whose exact rational solution needs 2,460 bits of numerator and denominator to write down.

So the swell is a property of the matrix and not of the method, which is the useful form of the claim. An exact solver’s memory is not predictable from the input size; it is predictable from the input size and the family, and the two families where it is worst are not the two where the question is longest.

And the ratio grows with n on a family where it exceeds one. Across n = 5, 7, 9, 11, 12 and 13 the random family reads 1.40, 1.49, 1.40, 1.51, 1.64 and 1.71 — noisy but trending upward, with the question exactly 4n² bits at every stop (100, 196, 324, 484, 576, 676) and the answer running from 5.6n² to 6.8n². So the swell is not a constant overhead that a caller could budget for once; it is a slowly growing fraction, and the growth is in the part nobody controls.

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 no denominator has. The second half of that needs one more clause, measured below: a denominator never grows and it can shrink. 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.

Both of those claims, counted #

The two statements above are arithmetic about sizes and neither was evaluated. Both hold, and both come out slightly different from the way they were written.

The inverse is 0.85n times the solution, not n. Counting the total bit length of every numerator and denominator of the reduced answer:

The shape is exactly the claim — the ratio grows with n, by a factor of four across the range — and the constant is under one, hovering near 0.85 and drifting upwards. The reason is one line: an inverse’s entries are (n−1) × (n−1) cofactors, while a solution’s numerators are n × n determinants with a column swapped. Each entry of the inverse is therefore about b + ½log n bits shorter than each entry of the solution, which is a fixed shortfall per entry against a growing length — so the constant approaches one from below and never reaches it. The n is an asymptote.

And scaling b can make the answer shorter. On a six by six with det A = −40098 = 2 · 3 · 41 · 163:

The numerators lengthen every time, as the paragraph above says. The denominators never lengthen — also as it says — and they shorten by three bits at c = 2 and six at c = 3, one bit per entry per factor shared with the determinant. At c = 1,000,003, which is prime and divides nothing, they return to exactly 87.

That does not weaken the instruction to divide the content out of b; it makes it slightly harder to price. Leaving a factor c in the right-hand side lengthens the numerators by n·log₂c, which is predictable, and shortens the denominators by however much of c the determinant happens to contain, which is not — it needs the factorisation of det A, an object nobody computes and nobody wants to. So the net effect of a forgotten scaling is a length change of unknown sign in one of the two halves, and the repair is free while the accounting for skipping it is not.

There is a third reading in the first table that is worth taking, because it is the one that decides whether an exact inverse is ever the right object. The ratio is not a constant overhead to be budgeted once — it grows, so the decision moves with the size. At n = 3 an exact inverse costs twice a solve and might reasonably be kept for reuse across several right-hand sides; at n = 10 it costs nine, so it pays for itself only past nine right-hand sides, and at n = 100 it would cost eighty-five. The break-even number of solves is the size of the matrix, which is exactly the shape the floating-point argument reaches by a different route — and here it is a statement about bytes on disk rather than about stability, so it applies even to a code that has no accuracy concern at all.

assertTheOutputFloorScalesWithTheObjectAsked holds both: the inverse ratio between 0.6n and n at every size and growing, and the denominators shortening exactly when the scale shares a factor with the determinant and standing still exactly when it does not.

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.

Where this sits against the rest of the site #

Almost every cost argument on this site is about work: flop counts that stopped predicting the time, an ordering that changes a contraction’s price by two million, a factorisation kept because recomputing it costs more. All of them are arguments about arrangement, and all of them have a better arrangement in them somewhere.

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.

What the modular route has to do about it #

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.