Every entry under the determinant

What a determinant does not determine computed the two normal forms of an integer matrix — the Smith form’s diagonal of invariant factors, and the Hermite form, upper triangular with every entry reduced modulo the pivot below it — and was candid about its routines: they “make no attempt to control the growth that a modular or a Hermite-first approach would”, so every figure stopped at six by six. It also said where the Hermite form’s growth comes from: “The entries of the Hermite form itself are bounded, because each is reduced modulo a pivot. The transform is not … It is not the fractions that grow — it is the coefficients of a combination, and any algorithm that reports how it reached its answer pays for the report.”

Both remarks can be tested once the routine is instrumented and the modular approach is built. The first one’s promise holds completely, and costs more than it saves at every size the earlier essay could have afforded. The second puts the growth in the wrong place.

Two routes to one form #

The plain route is the earlier essay’s: integer row operations only, each column reduced to a single nonzero by repeated Euclidean steps, then the entries above each pivot reduced modulo it. It is instrumented here to record two widths separately at every step — the widest entry of the matrix being reduced, and the widest entry of the transform $U$ with $UA = H$ that it carries along.

The modular route rests on one fact about lattices. If $A$ is square and nonsingular with $D = |\det A|$, then every vector $D e_j$ is an integer combination of $A$’s rows — the adjugate gives the coefficients — so the lattice $A$’s rows generate is also generated by those rows together with $D I$. Adding any multiple of $D e_j$ to a row stays in the lattice, which means every entry can be reduced modulo $D$ at every step. At column $c$ the route adds $D e_c$ to the remaining rows, combines their column-$c$ entries into one pivot by extended-gcd steps, each a unimodular two-by-two transformation, reduces everything else modulo $D$, and finally reduces above the pivots as the plain route does.

The determinant comes first, computed exactly by fraction-free elimination, whose intermediates every intermediate is a minor showed are bounded by Hadamard’s inequality. The matrices are random, with entries from $-9$ to $9$ to $n = 80$, and from $-999$ to $999$ to $n = 32$.

Four by four, by hand #

The smallest case shows everything. Take the four-by-four matrix with rows $(8, 6, 4, -8)$, $(-8, -8, -5, 2)$, $(-7, 9, 2, 1)$ and $(-6, 7, 8, -1)$ — one of the random matrices, with nothing special about it. Its determinant is 5,174, a thirteen-bit number. Its Hermite form is the identity in its first three columns, with a last column of 1,784, 4,565, 1,224 and 5,174: three residues and the determinant. Every row of the answer says that one coordinate, taken with a multiple of the last, lies in the lattice — and the lattice is every integer vector whose coordinates satisfy a single congruence modulo 5,174.

Plain elimination reaches that answer through numbers of six bits after the first column, ten after the second and twenty after the third — a million, beside an answer whose largest entry is five thousand — before the last column’s reductions bring everything back under the pivots. The modular route works with residues modulo 5,174 throughout, so no stored number is wider than thirteen bits and no product before a reduction wider than twenty-six. The two routes end at the same four rows.

Identical answers, one of them never wide #

The figure at the top of the page is the whole measurement of size.

The two routes return the same Hermite form, entry for entry, on every matrix, and its pivots multiply to $|\det A|$. Modulo the determinant every stored entry fits in the determinant’s own width — 13 bits at $n = 4$, 60 at 16, 219 at 48, 390 at 80 — and every product formed before a reduction fits in twice that. The plain route’s widest intermediate is 21 bits at $n = 4$, 307 at 16, 3,371 at 48 and 13,835 at 80. On the wider entries the gap is the same shape: 167 against 899 bits at $n = 16$, 347 against 3,727 at 32.

Followed column by column the two routes look nothing alike. The plain route’s widest entry climbs steadily through the elimination, from 7 bits after the first column to 696 after the twenty-third, and falls back to 98 at the last, when the final reductions bring every entry under its pivot. The modular route is at the determinant’s width, 98 bits, from the first column and never leaves it. The plain route’s swell is not a peak at one awkward step. It is the whole elimination, growing the remaining rows column after column until the end discards it.

The swell is the elimination’s, not the report’s #

The dashed red line in that figure, the transform’s width, is invisible because it lies on the solid one. At $n = 24$ the form’s widest intermediate is 696 bits and the transform’s 693; at 48, 3,371 and 3,366; at 80, 13,835 and 13,832. At every size and on both families the form is within five per cent of the transform and usually a few bits wider.

So the earlier essay’s account of where the growth lives does not survive being measured. It is true that the finished form’s entries are bounded — every entry above a pivot is reduced modulo it — and true that the transform grows. But the form’s intermediates grow just as much, because the same Euclidean steps that build up the transform’s coefficients are applied to the rows being reduced. An algorithm that computed the Hermite form and threw the transform away would save memory for one matrix and save nothing in the width of the numbers it handles. The growth belongs to the elimination, and the report — the transform — merely records it.

The two widths grow differently in kind. The determinant’s width grows like $n \log n$ — Hadamard’s bound, roughly the log of the entries plus half the log of $n$, times $n$. The plain route’s widest intermediate grows roughly like $n^2$, so their ratio grows in proportion to $n$: 1.6 at $n = 4$, 5.1 at 16, 10 at 32, 15 at 48 and 35 at 80. That is the same contrast the answer is longer than the question found between Bareiss’s elimination and naive rational arithmetic — linear growth against something faster — arriving here inside a routine that uses no fractions at all.

The finished report is narrow too #

There is a second half to the earlier essay’s sentence — “any algorithm that reports how it reached its answer pays for the report” — and it can be tested the same way. The report is the transform $U$, and the figure at the top of the page draws its finished width as well as its intermediates. The finished transform is as narrow as the form: 23 bits at $n = 8$, 95 at 24, 209 at 48, each within the determinant’s width, while the transform’s intermediates on the way were 69, 693 and 3,366 bits. On every matrix measured the finished form and the finished transform both fit inside the determinant’s width.

That is not a coincidence of these matrices. For a nonsingular $A$ the transform is unique, $U = HA^{-1}$, and $A^{-1}$ is the adjugate over the determinant, so $U = H\,\operatorname{adj}(A)/\det A$ — a product of two matrices whose entries are bounded by the determinant’s width, divided exactly by the determinant. The report has a size fixed by the problem, as the answer does; what is unbounded is only the path plain elimination takes to both.

Which also means the report can be had without the path. Once the modular route has produced $H$, the transform is the solution of $UA = H$, an integer system whose answer is known in advance to be integral; fraction-free elimination solves it with every intermediate a minor, and the inverse that is never formed is the reminder that it should be solved rather than computed as $H$ times an inverse. Nothing in that recovery is wider than the determinant’s width plus the form’s, so a caller who needs the transform does not have to choose between it and the bound.

What the answer actually is #

The width of the intermediates is out of all proportion to the answer, and the answer is worth looking at.

The Hermite form of a random integer matrix is almost the identity. At $n = 12$ the first nine pivots are 1, the next two are 2 and 17, and the last is a 39-bit number; every column but the last holds entries of at most five bits, and the last column holds entries up to 39 bits, each below the last pivot. Of the determinant’s 44 bits, 39 sit in one corner entry.

Over twenty random matrices at $n = 24$ it is the same: between one and four pivots differ from one — exactly one on eleven of the twenty — and the last pivot carries at least 95 per cent of the determinant’s 94 to 100 bits. When the last pivot is the only one, the lattice a random integer matrix generates is the set of all integer vectors satisfying a single linear congruence modulo the determinant, and one number and one column of residues describe it. Plain elimination produces numbers of thirteen thousand bits on the way to an answer that is a column of four-hundred-bit residues and an identity. The modular route never writes down anything wider than the answer’s own widest entry.

That shape is what the Smith form records as invariant factors of one and a single large last factor: the quotient of all integer vectors by the lattice is cyclic. The rank depends on the ring found an integer matrix of rank six over the rationals whose rank drops to five modulo three and four modulo two — a matrix whose quotient is not cyclic — and a matrix like that cannot have a Hermite form with a single non-unit pivot, since a single non-unit pivot would make the quotient cyclic.

A bound is not a saving #

The measurement that changes the conclusion is the cost.

The cost is counted in schoolbook bit operations — a multiplication costs the product of its operands’ widths, a division the product of dividend’s and divisor’s, an addition the wider operand — so that it does not depend on the machine. Counted that way, and with the modular route charged for computing its determinant, it does more work than plain elimination at every size to 64 on both families: 3.8 times as much at $n = 4$, 2.6 times at 24, 1.2 times at 64. The two are within three per cent at $n = 72$, and at 80 the modular route is a sixth cheaper.

The reason is in what each route multiplies. Plain elimination’s Euclidean steps mostly multiply a wide row by a small quotient — a few bits times thousands — which is cheap per step even when the row is huge. The modular route’s extended-gcd steps multiply rows of determinant-sized entries by determinant-sized coefficients and then reduce the products modulo the determinant, which is a wide number times a wide number on every step. The plain route’s numbers grow like $n^2$ in bits and the modular route’s like $n \log n$, so the plain route’s cost must eventually overtake, and it does — but not until the matrices are larger than anything the earlier essay could have computed with its routine.

So the earlier essay’s remark that a modular approach would control the growth is right, and the implication that it would be what made larger sizes affordable is not, at least not below seventy. What the bound buys at these sizes is memory and predictability: the modular route’s numbers are never wider than twice the determinant, known in advance from Hadamard’s bound, while the plain route’s widest number cannot be predicted without running it.

Where the determinant comes from #

The modular route needs $|\det A|$ before it starts, and that is not free either. It is the one number that has to be exact before anything else is, and it could be produced modulo enough primes and reconstructed, the way a fraction recovered from one remainder recovers a rational from a single modular image. Here it comes from fraction-free elimination, $n^3$ operations on numbers bounded by the determinant’s width, and in the same count it is 2 to 5 per cent of the modular route’s total — a small part of why the crossover is as late as it is. How many primes the answer needs priced the other route to a determinant — compute it modulo enough word-sized primes and reconstruct it — and found the number of primes set by the same Hadamard bound. Either way the determinant is cheap beside what follows it: the expensive part of the modular route is the elimination modulo the determinant itself, every step of which multiplies two numbers of the determinant’s width.

There is also a subtlety the measurement passes over because these matrices never trigger it: the modular route needs a nonsingular matrix, since a zero determinant gives no modulus, and for a singular or rectangular matrix the standard variants work modulo a nonzero maximal minor instead. The refusal attached to this essay feeds the route a singular matrix and requires it to say so rather than return a form computed modulo zero.

What eighty random matrices do not show #

Every matrix here is random with small entries, square and nonsingular. Random matrices are the case where the Hermite form is almost the identity, and a matrix built to have many non-unit pivots — a lattice with structure, the kind a basis that describes its lattice badly reduces — would give the modular route more to do at every column, and the plain route a different growth. The cost model counts schoolbook operations; a multiplication algorithm faster than schoolbook on wide numbers would cut the plain route’s large multiplications less than proportionally, since most of them are wide-by-small, and would favour the modular route earlier. And the plain route’s growth on these matrices is roughly quadratic in bits, which is benign: plain Hermite elimination can be driven to far worse growth by adversarial matrices, and none of them is measured here.

Still open: the Smith form modulo the determinant, structured lattices, and the crossover’s size #

The Smith form. The same lattice fact lets the Smith form be computed modulo the determinant, with column operations as well as row operations. The prediction with a sign is that it returns the earlier essay’s invariant factors exactly, never writes a number wider than twice the determinant, and — because random matrices have Smith forms of all ones but one entry — finishes in about the same bit operations as the modular Hermite form, rather than the far larger count the plain Smith routine needs, which the earlier essay could not take past six.

A lattice with structure. Take a matrix whose Hermite form has many non-unit pivots — the product of a random unimodular matrix and a diagonal of small primes. The prediction is that the modular route’s advantage in width is unchanged, and that its cost crossover moves to smaller $n$, because the plain route’s Euclidean steps there involve more and larger quotients.

Where the crossover sits. The two routes cross at $n = 72$ for entries to ±9. The prediction is that for entries to ±999 they cross earlier, near $n = 48$, because the determinant’s width grows by a fixed amount per row and the plain route’s quadratic growth starts from wider entries — and that the crossover in general falls where the plain route’s widest entry is about forty times the determinant’s.