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.

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.

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.

At other settings #