Integer Matrix Normal Forms
Applications of the Hermite Normal Form
Solving integer linear systems, computing indices and intersections, and testing module membership using the Hermite normal form.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0539
The Hermite normal form is a general-purpose tool. Once a module is in canonical form, a range of questions that are awkward in general become straightforward.
Membership testing
To decide whether a vector lies in a module, reduce it against the Hermite basis from the pivot positions downward. The vector belongs exactly when the reduction terminates at zero.
Module membership
- AlignStart at the highest pivot position.
- DivideDivide the corresponding vector entry by the pivot; if the division is not exact, the vector is not a member.
- SubtractSubtract that multiple of the basis column.
- AdvanceMove to the next pivot and repeat.
Integer linear systems
A system with integer coefficients may be solvable over the rationals but not over the integers. The Hermite form makes the distinction explicit: the divisibility conditions appear directly as exactness requirements during back-substitution.
Index computation
For two modules of the same rank, one contained in the other, the index is the absolute determinant of the matrix expressing the smaller basis in terms of the larger. In Hermite form this is simply the product of the diagonal entries.
Sum and intersection
| Operation | Method |
|---|---|
| Sum | Concatenate generating sets, take Hermite normal form |
| Intersection | Compute a kernel of the stacked matrices, then normalise |
| Equality | Compare Hermite normal forms entrywise |
| Containment | Test each basis vector of one for membership in the other |
Ideal arithmetic
Every ideal operation in a number field reduces to these primitives. Ideal sum is module sum; ideal product is the module generated by pairwise products, normalised; ideal norm is the index of the ideal in the maximal order, hence a product of pivots. See ideal multiplication and ideal norms.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.4.3. 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.