Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Hermite normal form — where it appears

The triangular form an integer matrix reaches by integer row operations that can be undone, with positive pivots and the entries above each reduced below it. Every integer matrix has exactly one, so two bases span the same lattice exactly when they share it.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

s10 bitss20 bitss30 bitss40 bitss514 bitsinvariant factors, in bitstwo routes, and a conserved quantitydet A-2.3·10⁴Π invariants2.3·10⁴SNF widest15HNF widest24det of the transform-1an algorithm and a definitionagreeing as integers

What a determinant does not determine

Two integer matrices can have the same determinant, the same rank and the same size, and define genuinely different maps. What separates them is a list of integers each dividing the next — computed here twice, once by unimodular elimination and once from the gcds of every minor, which share no algorithm at all.

exact · Normal forms 10¹10²10³10⁴nwidest entry, bits48163264plain: the formplain: the transformplain: finished transformmodular: before reductionmodular: stored|det A|at n = 80: 13835 bits against 390the determinant bounds everything modulo itself

Every entry under the determinant

The Hermite form's swell was put down to its transform — the record of how the answer was reached — while the form's own entries stayed bounded. Instrumented separately, the form's intermediates swell exactly as much: 3,371 bits against the transform's 3,366 for a random 48 × 48 matrix whose determinant has 219. Carried out modulo the determinant instead, every entry stays within the determinant's width, the answer is identical on every matrix to n = 80, and it is almost always the identity with the whole determinant in its last pivot and last column. What the bound does not buy is speed: counted in bit operations the modular route does more work until just past n = 72, because its steps multiply numbers the determinant's size where plain elimination multiplies wide numbers by small quotients.

exact · Normal forms

Named alongside it

The objects these essays reach for when they reach for this one.

DeterminantExact arithmeticLatticeSmith normal formUnimodularCoefficient growthInvariant factors

All concepts