Every intermediate is a minor

An elimination over the integers has an obvious problem: the step that removes an entry needs a division, and integers are not closed under it. The standard repair is to move to the rationals and pay the price the previous essay measured — either a greatest common divisor on every operation, or a million and a half bits.

There is a third repair, and it looks at first like a trick. Do not divide by the pivot. Multiply through by it, subtract, and then divide the whole thing by the pivot from the previous step:

aᵢⱼ  ←  (aₖₖ·aᵢⱼ  −  aᵢₖ·aₖⱼ) / aₖ₋₁,ₖ₋₁

with the convention that the pivot before the first step is 1. Every quantity in that line is an integer, and the claim is that the quotient is an integer too — at every step, on every matrix, with no fallback and no remainder.

Those two figures are the guarantee as a number. Carried through steps one to four on the same five by five, the count of exact divisions runs 16, 25, 29 and 30 and the widest intermediate runs 6, 9, 12 and 15 bits — three bits a step, exactly, and thirty divisions with not one remainder between them.

Three bits a step is the whole of what fraction-free elimination buys. The unreduced rational route of the previous essay quadruples its numerators at every step, which is a bit length doubling; this one adds a constant. Linear against exponential, on the same matrix, with the same answer at the end — and the reason is the paragraph above rather than any care taken with the arithmetic: an intermediate that is a minor of the original matrix is bounded by Hadamard’s bound on that minor, and a (k+1)-square minor of entries of a given size has a length linear in k.

It is not a trick, and the reason is the whole content of this essay.

What the entry is #

After k steps of the recurrence above, the entry at position (i, j) is not “the matrix, partly eliminated”. It is exactly this determinant:

| a₀,₀  …  a₀,ₖ₋₁   a₀,ⱼ  |
|  ⋮          ⋮        ⋮   |
| aₖ₋₁,₀ … aₖ₋₁,ₖ₋₁  aₖ₋₁,ⱼ |
| aᵢ,₀   …  aᵢ,ₖ₋₁   aᵢ,ⱼ  |

a (k+1) × (k+1) minor of the original matrix, on the first k rows together with row i, and the first k columns together with column j. Not of the partly-eliminated matrix. Of the matrix as it arrived.

That is Sylvester’s identity, and once it is stated the exactness of the division is not a separate fact. The numerator formed by the step is a (k+1) × (k+1) determinant multiplied by the k × k one sitting above it, and the thing being divided out is that k × k determinant. The quotient is a determinant, so it is an integer.

Checked against the minors, not against a second elimination #

The claim is easy to state and easy to believe, which is exactly the situation in which this site insists on a second route. So the check is a cofactor expansion of the original matrix: for each boxed entry, the minor Sylvester’s identity names is computed by the definition, recursively, without any elimination anywhere in it, and compared to the entry as an integer.

That is deliberately the slow route. An elimination checked against a faster elimination shares every assumption that could be wrong; the two agree because they are the same argument written twice. The cofactor expansion is exponential in the size of the minor and it is affordable at these sizes precisely because these sizes are the ones the figure prints.

There is one thing the check cannot cover and it is worth saying rather than hiding. Sylvester’s identity is about the matrix in the order the rows arrived. If a pivot is zero and the elimination interchanges rows, the intermediates are minors of the permuted matrix, and the check as written declines to run rather than reporting a false agreement. Every family drawn here has nonzero pivots throughout, and the routine that computes determinants for the rest of the field does interchange rows and does not make the minor claim.

What it costs, which is the point #

The exactness is pleasant. The reason the algorithm exists is the size bound that follows from it.

An intermediate is a minor, so its magnitude is bounded by Hadamard’s bound on that minor: the product of the two-norms of the k+1 rows involved. For entries of b bits that is at most (k+1)·(b + ½log(k+1)) bits — linear in the step index. The elimination cannot form a number much larger than the determinant it is heading for, because everything it forms is a determinant of a submatrix.

Compare that with the unreduced rational recurrence, where the new numerator is a product of two old numerators and the length doubles per step. One is arithmetic that stays inside the answer’s own scale; the other leaves it in the third step and never comes back.

How near anything comes to that bound #

Hadamard’s bound is an upper bound and this collection’s habit is to ask by how much. Across the six families the field carries, at n = 9, the largest intermediate in bits at each step:

wide (10-bit entries): 10, 20, 30, 40, 51, 61, 71, 81, 91 — 87 per cent of the bound at the last step. hadamard (1-bit): 1, 2, 3, 5, 6, 8, 10, 13 — 65 per cent. random (4-bit): 4, 7, 9, 12, 16, 19, 22, 25, 25 — 50 per cent. hilbert (24-bit): 24, 44, 62, 76, 86, 91, 90, 88, 88 — 38 per cent. pascal (14-bit): 14, 14, 14, 14, 14, 12, 10, 7, 7 — 5 per cent. unitriangular: one bit throughout — 4 per cent.

A factor of twenty between the loosest and the tightest. So the bound is a genuine worst case rather than a pessimistic one: something nearly attains it, and something else misses it by a factor of twenty-three.

And the entry width does not say which. pascal has the widest entries but one and is the second-loosest; unitriangular has the narrowest and is the loosest; wide sits in the middle on entries and is the tightest. What decides is the size of the minors, which is a property of the matrix that no single number about its entries carries.

And on two families the intermediates shrink #

The bound is linear and increasing, and two of the six sequences are not.

pascal peaks at 14 bits — the width of its own entries — holds there for five steps, and then falls to 7. hilbert peaks at 91 at step five and ends at 88.

That is not a rounding and it has a reason worth stating, because it is the same reason the algorithm works. A late intermediate is a large minor, and a large minor is not necessarily larger than a small one. The very last entry the elimination produces is the determinant itself, and on these families the determinant is smaller than the intermediate minors that produced it. The sequence therefore rises while the minors are growing faster than they are being cancelled by the divisions, and falls once they are not.

No bound of the form (k+1)(b + ½log(k+1)) can describe a sequence that falls, and none should — it is a ceiling. But it means the shape of the growth is not the shape of the bound on four of the six families, and a reader sizing an allocation by reading the bound’s slope would be sizing for a straight line where two of these are humps.

The practical form is the one worth carrying. The argument justifies the algorithm and the number does not describe it. What decides whether fraction-free elimination’s arithmetic fits in a machine word is the actual growth, which runs between one twentieth and nine tenths of the bound on the families here, and there is nothing cheaper than running it to find out — the same shape the hierarchy field’s expansion bound has, where a bound computable in advance is loose by a factor that varies with the geometry.

The step, entry by entry #

The recurrence is short enough to follow completely on a four by four, and following it is the fastest way to see why the previous pivot is the right thing to divide by.

At the first step the previous pivot is 1, so the step is just aₖₖ·aᵢⱼ − aᵢₖ·aₖⱼ: every new entry is an ordinary two by two determinant of the original matrix. Nothing has been divided yet and nothing needs to be.

At the second step the entries being combined are already two by two determinants, so their products are four factors deep and the result is a four-factor quantity where a three by three determinant is wanted. What removes the surplus factor is precisely the two by two determinant that was the pivot — which is why the divisor is the previous pivot and not the current one, and why it is a single division rather than a search for a common factor.

The families where nothing happens, and why they are the useful ones #

Two families in this field are constructed so that the algorithm has no room to be clever, and they are how any growth claim gets a floor.

The unit lower triangular family is already eliminated. Every pivot is 1, every division is by 1, and every intermediate is 1 or 0. Any growth measured on it is the routine’s own bookkeeping rather than the matrix’s, and there is none.

The Pascal family is more interesting: its entries reach twenty bits by n = 12 and its determinant is exactly 1 at every size. So it separates two quantities that are easy to conflate. The entries are large, the answer is one, and the intermediates — being minors of a matrix whose minors are themselves binomial determinants — stay tiny. Entry size does not predict intermediate size, and intermediate size does not predict the answer’s size.

Three things that follow, none of them obvious from the recurrence #

Stating the intermediates as minors settles several questions that would otherwise each need their own argument, and they are worth collecting because they are the reason this recurrence is the one integer libraries use rather than one of several plausible ones.

The last entry is the determinant, with no accumulation. A float LU builds its determinant as a running product of pivots, and every one of those multiplications rounds. Here the entry at the bottom right after the last step is the n × n minor — that is, the determinant — and it was never formed as a product of anything. There is no accumulated quantity to be wrong, which is why the determinant essay’s complaint about a product of pivots does not transfer.

The leading principal minors come out along the way, in order. Each pivot aₖₖ after step k−1 is the k × k leading principal minor, so the sequence of pivots is the sequence of those minors. That is a free inertia computation on a symmetric matrix — the number of sign changes in the sequence is the number of negative eigenvalues, by Sylvester’s law — and it costs nothing beyond the elimination that was going to happen anyway. The essay that counts eigenvalues by inertia does it in floating point and has to decide what a zero pivot is; here a pivot is zero or it is not.

A zero pivot is information rather than an accident. In a float elimination a small pivot triggers a row interchange and the smallness is a judgement. Here a pivot is exactly zero precisely when a leading principal minor vanishes, which is a statement about the matrix that no arithmetic made — and the interchange that follows is a decision about which nonzero minor to use next rather than about which number is safest to divide by. The two eliminations swap rows for reasons that have nothing in common, which is easy to miss because the code looks the same.

What this makes possible elsewhere #

Fraction-free elimination is the reason several measurements on this site could be taken at all, and they are worth naming because the technique is invisible in them.

The spanning-tree count is a determinant of a grounded Laplacian, and Kirchhoff’s theorem makes it an integer — so a float determinant that returns 1.19999999998·10²⁰ has to be rounded, and the rounding is exactly what fails once the answer passes 2⁵³. The exact determinant does not, and the route it takes is this one.

The effective resistance between two vertices of an unweighted graph is a ratio of two such determinants, so it is a rational number with a known numerator and denominator rather than a float with a residual. Both are computed here.

And the cospectral pair — two graphs with the identical characteristic polynomial — is checked as an identity between integer polynomials rather than as an agreement between two lists of computed eigenvalues, which would be a comparison at a tolerance and would prove nothing at all about whether the polynomials are the same.

In each case the exactness is not the finding. It is the instrument that lets the finding be stated without a tolerance in it — the same role the closed-form Hilbert inverse plays in the essay that measures a float solve against a known answer, and the reason that essay can say the error rather than an estimate of the error.

The other thing a minor is: a rank certificate #

Because every intermediate is a minor, a fraction-free elimination is doing something no floating point elimination can do, and it is worth naming before the field gets to rank properly.

A matrix has rank at least r exactly when some r × r minor is nonzero, and the elimination hands over one such minor at each level as it goes. So when a fraction-free elimination on a rank-deficient matrix reaches a level where every remaining entry is zero, that is not a decision about a small number: it is a proof that every minor of that size vanishes, arrived at without a threshold. Every other statement about rank on this site is a decision about where to put a line — the essay that argued that is about the line, and the cheap rank-revealing route is about what a greedy pivot rule can and cannot detect through one.

Here there is no line. A zero is a zero. What replaces the threshold as the source of trouble is which ring the entries are read in, which is a genuinely different problem and gets its own essay.

What the divisions actually cost #

There is a temptation to read the exactness as free, and it is not quite.

An exact division of a 2b-bit integer by a b-bit one is not one machine operation. It is a division of long integers, and the schoolbook cost is quadratic in the length. So the step performs two multiplications of b-bit integers, a subtraction, and a division — and the division is the expensive one, at roughly the cost of the multiplications together.

That is still the good deal, and the arithmetic says why. The reduced-rational route performs a greatest common divisor per entry, and a gcd of two b-bit integers is a sequence of about b divisions rather than one. So both routes pay a length-dependent price per entry and the fraction-free route pays it once where the reduced-rational route pays it b times. The measured consequence is not in the bit-length figure at all — both routes end within a bit of each other — it is in the time, and it is the reason libraries that compute integer determinants use this recurrence.

The unreduced route is cheap per operation and its operands are the ones that leave the picture. Three ways of arranging the same n³/3 arithmetic operations, and the operation count cannot tell them apart, which is the same complaint the cost field makes about flop counts arrived at from a completely different direction.

Where it stops #

The algorithm has one genuine limitation and it is not about the divisions.

Fraction-free elimination is the right route when the answer is one integer — a determinant, a resultant, a characteristic polynomial’s coefficients. It is a poor route when the answer is a large matrix of rationals, because the last thing it produces is a triangular matrix whose entries are the largest minors, and recovering a solution vector from those means dividing by them and reducing after all. That is the same shape of complaint as forming an inverse when a solve was wanted: the intermediate object is larger than the question, and paying for it is optional.

For that problem the field has a different answer: work modulo primes where nothing can grow, and reassemble. That is where the next three essays go, and the bound that makes it possible — Hadamard’s — is the same one that bounds the intermediates here.