The swell was one-sided

Every entry under the determinant computed the Hermite normal form of an integer matrix two ways. Plain elimination — the smallest entry of a column as pivot, floor quotients down the rest of it — let its intermediates swell to fifteen times the determinant’s width by forty-eight rows, and the swell was in the form itself, not only in the transform that records how the form was reached. Working modulo the determinant $D = |\det A|$, which is legitimate because every multiple of $D$ times a unit vector lies in the lattice the rows generate, kept every stored entry within $D$’s width and every product formed before a reduction within twice that. It was also dearer at every size up to about seventy, once the determinant’s own cost was counted.

What a determinant does not determine, the essay before that, had computed the Smith form — the diagonal of invariant factors, each dividing the next, that two-sided unimodular elimination reaches — and stopped every figure at six rows, saying of its routine that “sizes above about ten are not affordable with it”. So the obvious next step was the Smith form modulo the determinant, and it was predicted with a sign: “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.”

Every clause about the modular route holds. The clause about the plain routine does not, and the reason it does not is more useful than the modular route.

The Smith form modulo the determinant #

The modular route mirrors the modular Hermite form with column operations added. At each position it combines the entries of the pivot’s column into one, and then the entries of its row, by extended-gcd steps — each a unimodular two by two transformation of two rows or two columns — and reduces every entry it writes modulo $D$. When the trailing block is diagonal, each diagonal entry is replaced by its gcd with $D$, and the divisibility chain is restored by replacing neighbouring pairs with their gcd and lcm until nothing moves.

It returns the right answer. On every random matrix measured — entries to ±9 at sizes four to sixty-four, entries to ±999 at sizes four to thirty-two — and on five structured lattices, its invariant factors are the plain route’s exactly, and at sizes four and six they are the earlier essay’s routine’s as well, which is checked against the gcds of all the minors. As predicted, random matrices give a dull answer: all ones and then the determinant, on all but one matrix of the fourteen, which has two factors of two before the large one.

And it is bounded. Every product it forms before a reduction is within twice the determinant’s width plus two bits — 263 bits against a 132-bit determinant at thirty-two rows, 604 against 302 at sixty-four — and every stored entry is within the determinant’s width.

On cost the third clause holds too. Counted the way the Hermite comparison counted — a schoolbook bit-operation count, the determinant’s own fraction-free computation included — the modular Smith route costs between 0.43 and 0.81 of the modular Hermite route on the ±9 family and up to 0.84 on the ±999 family, falling with the size. Column operations give it a second way to reduce each pivot and it finishes each column sooner.

The comparison the prediction assumed #

The prediction placed the modular Smith route against “the far larger count the plain Smith routine needs”. Measured, the plain Smith routine is by far the cheapest of the four. At sixteen rows it costs $4.8 \cdot 10^5$ bit operations, against $2.3 \cdot 10^7$ for the modular Smith route and $3.0 \cdot 10^7$ for the modular Hermite route; at sixty-four, $1.0 \cdot 10^9$ against $4.1 \cdot 10^{10}$. From eight rows on the modular route does twenty-five to sixty-nine times its work on the ±9 family, and eighteen to thirty-five times on the ±999 family.

And it runs. At sixty-four rows the plain Smith routine takes about half a second in an interpreted language, with BigInt arithmetic throughout. The earlier essay’s limit of six was not the elimination’s: it was the check the essay ran beside it, which computes the invariant factors from the definition — the gcd of every minor of every order — and has 924 minors to compute at six rows and about a hundred and forty billion at twenty. That check was the right thing to run once. It was never the cost of the algorithm.

Nothing the plain route writes is wider than the determinant #

The reason it is cheap is that it never swells. On every random matrix measured, the widest entry plain Smith elimination writes is within one bit of the determinant’s width — 60 bits against 60 at sixteen rows, 132 against 132 at thirty-two, 302 against 302 at sixty-four — and on the ±999 family the same. Plain Hermite elimination on the same matrices writes 307 bits at sixteen rows and 3,371 at forty-eight, where the determinant is 60 and 219.

The two routines are the same algorithm with one difference. Both take the smallest nonzero entry as the pivot and reduce the others by floor quotients until the pivot divides everything it must. The Hermite routine may look for its pivot only in the current column and may only combine rows. The Smith routine looks in the whole trailing block and may combine columns too.

The trace says what that difference does. On a random matrix with entries to ±9 the smallest entry in the whole block is almost always a one, so the Smith routine’s first pivot is a unit and its elimination needs no quotient larger than nine. After it the next smallest entry is again usually a one, and it is again the pivot. At twenty-four rows every one of the first twenty-three pivots is one, and the last is the determinant.

With unit pivots, two-sided elimination is exactly fraction-free elimination with nothing to divide by: after $k$ steps every entry of the trailing block is a $(k+1) \times (k+1)$ minor of the matrix with its rows and columns permuted. Minors of order $k+1$ are bounded by Hadamard’s bound for $k+1$ rows, which grows with $k$ and reaches the determinant’s size only at the end. So the width climbs steadily — 7 bits after the first pivot, 28 after the eighth, 54 after the seventeenth, 98 after the twenty-third — and never overshoots, because the largest thing it is ever asked to hold is a minor of the matrix, and the largest minor is about the size of the largest determinant a matrix of that size can have.

The Hermite routine cannot do that. Confined to the current column it must take the gcd of that column’s entries by Euclid’s algorithm on whole rows, and when the column’s entries are coprime but none is one, each step’s quotient multiplies a whole row; the rows it builds are combinations with coefficients that grow like continued-fraction convergents, and the other columns of those rows grow with them. At twenty-four rows it reaches 696 bits before its last column brings it back to 98. The earlier essay found the swell in the form as well as the transform, and called it the elimination’s. It is more specific than that: it is the swell of doing the elimination with one hand.

The dull answer is the cheap route #

Why should the smallest entry of the block be a one at every step, and not only at the first? The routine does not pivot on the smallest entry and move on. It reduces the pivot’s row and column by floor quotients, and if anything is left over — an entry the pivot does not divide — it takes the new smallest entry and goes round again, a Euclid’s algorithm run on the whole block. It stops at a pivot that divides every entry of its row and column, which is the gcd of what it could reach; and the first invariant factor is the gcd of every entry of the matrix.

For a random integer matrix that gcd is one, and so is the gcd of every $k \times k$ minor up to $n-1$: that is what an invariant-factor sequence of ones followed by the determinant means. So the Smith form’s dullness, which the prediction treated as a reason the modular route would be cheap, is the reason the plain route is cheaper. Each pivot is the invariant factor of its position, every one of them is one, and elimination with unit pivots divides by nothing and multiplies by nothing large. The only non-unit is the determinant, and it arrives last, as a single number, when there is nothing left to eliminate.

A prime that divides the answer met the same fact from the modular side: a matrix singular modulo some prime is a matrix whose invariant factors that prime divides, and a random matrix’s invariant factors give it almost nowhere to do so. The answer is longer than the question measured how wide an exact solution’s numbers have to be — ratios of determinants, which no route can avoid writing. The Smith form’s numbers are narrower than that: everything but the last is one.

A residue is as wide as its modulus #

The trace also explains the cost result, and it inverts the intuition that bounded means cheap. Reduced modulo $D$, an entry is a residue — a random-looking number between zero and $D$ — and a random residue is as wide as $D$ itself. So the modular route holds 98-bit entries from its first pivot at twenty-four rows, where plain elimination holds 7-bit ones. Every multiplication it performs is between full-width numbers, followed by a full-width reduction, for every one of the $n^3$ operations of the elimination. Plain elimination does the early part of its work on small numbers and reaches full width only at the end, on a block that by then is small.

How many primes the answer needs made the opposite trade work for linear systems: there, many small primes each keep every operation within a machine word, and the cost is paid in the number of primes, which is set by the size of the answer. A single modulus the size of the determinant gets the bound and none of the cheapness. The modular Hermite route was worth it because plain Hermite elimination swells far past $D$, and the route only had to beat that. The modular Smith route has nothing to beat on random matrices.

Where the modulus earns its keep #

Random matrices are the case where the determinant is as large as it can be for their entries, which is exactly the case where a bound by the determinant constrains nothing. A lattice with structure can have a small determinant under large entries. The structured family here is a diagonal of ones and small primes — two, three, five, seven, eleven, some doubled — between two random unimodular matrices built from thirty-two to a hundred and twenty-eight elementary row operations. Its determinant is ten to forty-one bits wide; its entries twelve to twenty-one.

On those, plain Smith elimination does overshoot. Its pivots are no longer units after the first few — the invariant factors are not all one — and its widest entry exceeds the determinant’s width by six bits at eight rows, twelve at twelve, and twenty-eight at twenty-four. The modular route stores nothing wider than the determinant, as always. In width the modulus earns its keep exactly where the earlier essay’s argument said it would: where the determinant is small compared to what elimination writes.

In work it still does not. The modular route costs 5.6 to 14 times the plain route’s bit operations on the structured lattices. The plain route’s overshoot is a few dozen bits on numbers that are small to begin with, and the modular route still holds every entry at the determinant’s width from the start. A bound on size buys a guarantee — no entry wider than $D$, whatever the matrix — and on every family measured here the guarantee costs more than the swell it prevents.

The structured lattices also give the routes something to agree on that is not a single number. At thirty-two rows the invariant factors are twenty-five ones and then 2, 2, 2, 6, 2310, 2310 and 4620 — the construction’s primes, merged by the divisibility chain into the unique sequence in which each divides the next. Both routes return it exactly. It is a better test of the modular route’s final gcd and chain step than a random matrix, whose Smith form is ones and the determinant.

What a guarantee is worth #

Three things follow, and only the first is about the Smith form.

The first is that two-sided elimination is far better behaved on integer matrices than one-sided elimination, for the reason this essay’s trace makes visible: freedom to choose the pivot from the whole block lets it be a unit, and unit pivots make every intermediate a minor. The Hermite form needs row operations only because it describes the row lattice; it pays for that restriction in swell, and a Hermite-first route to the Smith form inherits the bill.

The second is the one an answer with no error in it began this field with, and that a basis that describes its lattice badly met in lattice reduction: in exact arithmetic the cost is the width of the numbers, and the width is a property of the route, not of the answer. The answer here is the same four ways. The widest number written on the way to it ranges from 98 bits to 696 at twenty-four rows.

The third is about bounds. A modulus guarantees a width; it does not make that width small, and a residue is as wide as the modulus from the first step. Whether a bounded route is cheaper depends on how far the unbounded one would have overshot. For the Hermite form it overshoots fifteenfold and the bound wins past seventy rows. For the Smith form on random matrices it does not overshoot at all.

What forty matrices do not show #

The random matrices are one draw at each size, and the plain routine’s behaviour rests on its first pivots being units, which is overwhelmingly likely for entries drawn uniformly from small ranges and not guaranteed for anything. A matrix whose every entry is even, or whose entries share a large common factor in some rows, would deny it unit pivots and might swell; the structured family approaches that, and swelled by up to twenty-eight bits. The cost count is schoolbook; with fast multiplication of large integers the modular route’s full-width arithmetic would be cheaper per bit, which narrows the gap without closing it at these widths. And the claim that every intermediate is a minor is argued from the unit pivots, not checked entry by entry.

Still open: a matrix that denies the unit pivot, and the crossover on structure #

No unit to pivot on. The plain Smith routine’s good behaviour rests on finding a one in the block. A matrix with entries drawn from the even numbers plus one odd row has no unit pivot until that row is used. The prediction with a sign is that on matrices whose entries are all multiples of three except in one row and one column, plain two-sided elimination’s widest entry exceeds the determinant’s width by at least half again at twenty-four rows and above, while the modular route stays within it — the first family on which the plain route swells by as much as the Hermite routine does.

Where the modulus pays in work. The structured lattices’ plain overshoot grows with the size — six bits at eight rows, twenty-two at thirty-two — while the modular route’s penalty, full-width arithmetic from the start, grows with the determinant. The prediction is that on structured lattices whose determinant stays below sixty-four bits, the modular route becomes the cheaper of the two by ninety-six rows, because the plain route’s swell then costs more than holding every entry at a width of sixty-four bits.