Integer Matrix Normal Forms
The Hermite Normal Form Algorithm
The Hermite normal form, the classical column-reduction algorithm, and the modular variant that bounds entry growth.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0537
The Hermite normal form is the integer analogue of row echelon form. It is canonical, which makes it the basis of every equality test on modules and ideals in this collection.
Definition
A matrix is in Hermite normal form when it is upper triangular, each pivot is positive, and every entry above a pivot is reduced modulo that pivot into a fixed range.
- Triangular
- Zero below the diagonal, after discarding zero columns.
- Positive pivots
- Each diagonal entry is strictly positive.
- Reduced off-diagonal
- Entries above a pivot lie in the interval from zero to the pivot. This is what makes the form unique.
The classical algorithm
Classical Hermite normal form
- Select a columnWork from one end, one row at a time.
- Reduce the rowUse the extended Euclidean algorithm on pairs of entries to replace them with their GCD and a zero.
- Normalise the pivotEnsure the pivot is positive.
- Reduce aboveReduce entries above the pivot modulo it.
- AdvanceMove to the next row and repeat on the remaining columns.
The modular algorithm
When a multiple of the determinant of the lattice is known in advance, the entire computation can be carried out modulo that value. Entries then never exceed the modulus.
Modular Hermite normal form
- Obtain a determinant multipleAny non-zero determinant of a full-rank square submatrix will serve.
- ReduceWork modulo that value throughout.
- RecoverLift the result and normalise; the true Hermite form is recovered because the lattice contains the modulus times the ambient lattice.
Two-element representation
For ideals of a number field a more compact representation is often preferable — see two-element representation. The Hermite form remains the canonical form used for comparison and for computing norms and indices.
Cost
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.2. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.