Lattices and LLL Reduction
Integer Kernel and Image via LLL
Computing a reduced basis of the integer kernel and image of a matrix, and why this is not the same as clearing denominators from a rational kernel.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0551
The kernel of an integer matrix over the integers is a lattice. Computing a basis for it — rather than merely a spanning set — requires either a normal form or lattice reduction, and reduction generally gives a far better basis.
Why the rational kernel is not enough
The correct object is the saturation: the set of all integer vectors in the rational kernel. This is what an integer kernel algorithm must return.
The LLL construction
Build an auxiliary lattice by stacking the matrix, scaled by a large factor, above an identity block. Reducing this lattice forces vectors in the kernel to become short, because their scaled part vanishes.
Integer kernel via LLL
- Choose the scaleTake c large enough that any vector with non-zero A-part is longer than every kernel vector.
- ReduceApply LLL to the stacked lattice.
- ExtractVectors whose upper part is zero give the kernel; read the kernel vector from the lower block.
- VerifyMultiply back through the original matrix to confirm.
The image
The image over the integers is the module generated by the columns. Its canonical basis is the Hermite normal form; a short basis is obtained by LLL reduction of the columns directly.
| Object | Canonical basis | Short basis |
|---|---|---|
| Image | Hermite normal form | LLL on the columns |
| Kernel | Hermite normal form of a kernel spanning set | LLL on the stacked construction |
Alternative via dependent LLL
The variant described in LLL for dependent generating sets produces kernel relations directly as a by-product, avoiding the scaling construction entirely. It is often the simpler route when an implementation of that variant is available.
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.