Integer Matrix Normal Forms
LLL-Based Hermite Normal Form Computation
Using lattice reduction to control entry growth during Hermite normal form computation, and when this beats the modular approach.
Engineering / MathematicsInteger Matrix Normal Forms2 min readKV-MATH-0542
When no determinant multiple is available, the modular Hermite algorithm cannot be used. Lattice reduction provides the alternative: keep the working basis short so the elimination never produces large entries in the first place.
The idea
The entries grow because the working basis vectors become long and nearly parallel. Reducing the basis with LLL restores near-orthogonality and short length, after which elimination proceeds with small Bezout coefficients.
LLL-based Hermite normal form
- Reduce the inputApply LLL to the generating set.
- EliminatePerform Hermite reduction steps on the reduced basis.
- Re-reduceInterleave further LLL passes when entries start to grow.
- NormaliseFinish with the standard Hermite normalisation of pivots and off-diagonal entries.
Handling dependent generators
Generating sets are often larger than the rank, so the input is a dependent family. Standard LLL assumes independence; the variant for dependent input detects and removes the zero vectors that appear — see LLL for dependent generating sets.
Choosing between LLL and modular
| Condition | Preferred method |
|---|---|
| Determinant multiple known | Modular — simpler and faster |
| Full-rank ideal in a number field | Modular, using the norm as the multiple |
| Rank unknown or matrix rank deficient | LLL-based |
| Very skewed input basis | LLL-based |
| Kernel or image over the integers wanted | LLL-based — see integer kernel via LLL |
Practical note
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.7.1. 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.