The echelon form that respects ℤ, not just ℚ
Over a field, echelon form is canonical because any non-zero entry can be scaled to 1. Over ℤ only ±1 is invertible, so the analogue must retain the arithmetic content of the pivots. The Hermite normal form is upper triangular with positive diagonal entries and each off-diagonal entry reduced modulo its diagonal — a unique canonical form for the module generated by the rows. It is how ideals of a number field are actually stored.
Learning objectives
- State the defining conditions of the HNF and its uniqueness.
- Compute an HNF and understand the role of unimodular transformations.
- Explain why naive HNF computation suffers entry explosion.
- Use the HNF to test module equality, membership and containment.
- Recognise the HNF as the storage format for ideals.
Section 01Definition and uniqueness
A matrix is in Hermite normal form when it is upper triangular, its diagonal entries are strictly positive, and every entry above a diagonal entry is reduced into the range [0, d) where d is that diagonal entry. For any integer matrix A there is a unimodular U — integer, determinant ±1 — with UA in HNF, and the HNF itself is unique.
Two integer matrices generate the same module if and only if they have the same HNF. This turns module equality — an infinite condition — into a finite comparison, and it is the reason the HNF, rather than an arbitrary basis, is the storage format.
The product of the diagonal entries is simultaneously the determinant and the index of the module in ℤn — for an ideal, this is its norm, read directly off the diagonal at no extra cost.
Section 02Computing the HNF
- Process columns from the last to the first; maintain a row index i.
- Within the working column, use extended GCD on pairs of entries to reduce all but one to zero. Each elimination is a unimodular 2×2 transformation, so the module is unchanged.
- Ensure the surviving pivot is positive; negate the row if needed.
- Reduce every entry above the pivot modulo the pivot, into [0, d).
- Move to the next column and repeat; discard rows that become entirely zero.
The naive algorithm can produce intermediate entries of astronomically greater size than either input or output — growth far worse than in Gaussian elimination, because the GCD steps combine rows without any normalising division. Practical implementations must control it.
| Strategy | Idea | Trade-off |
|---|---|---|
| Modulo determinant | Work modulo a known multiple of the determinant, since the HNF is determined modulo it | Needs the determinant or a multiple in advance |
| LLL preconditioning | Reduce the basis with LLL first, so rows are already short | Extra cost up front; usually repaid many times over |
| Pivot selection | Prefer small pivots and sparse rows | Cheap heuristic, no guarantee |
| Modular / p-adic | Compute modulo primes and reconstruct | Requires care with the module structure, not just the linear span |
Section 03Using the HNF
Module equality
Two sets of generators span the same module exactly when their HNFs match entry for entry.
Membership testing
A vector lies in the module if back-substitution against the HNF yields integer coefficients — not merely rational ones.
Index and norm
The product of the diagonal gives the index in ℤn; for an ideal this is its absolute norm.
Ideal representation
An ideal of a number field is stored as the HNF of its coordinate matrix with respect to an integral basis — canonical, compact, and directly comparable.
Intersection and sum
The sum of two modules is the HNF of the stacked matrices; the intersection is obtained from a kernel computation.
Canonical output
Any algorithm returning a module should return its HNF, so that downstream comparisons are meaningful.
The HNF is a canonical form for the module: it answers questions about generation, index and membership. The Smith normal form is a canonical form for the quotient: it answers questions about group structure. Use the HNF to store an ideal, and the SNF to determine a class group.
ReferenceFrequently asked questions
Is the HNF row-style or column-style?
Both conventions are in use and they are transposes of one another. Mixing them is a frequent source of confusion when moving data between systems, so check which convention a library uses before interpreting its output.
Do I always need the transformation matrix U?
No, and it is expensive to maintain — its entries can be much larger than those of the HNF itself. Request it only when the change of basis is genuinely needed, for example when lifting a relation back to the original generators.
Why does the HNF matter so much for ideals?
Because an ideal is a ℤ-module of full rank in the ring of integers, and the HNF gives it a unique compact representation with the norm available for free on the diagonal. Ideal equality, membership and norm all become trivial operations.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.