### Finding the Hermite normal form of an integer matrix using the Havas-Majewski-Matthews LLL-based algorithm

An m × n integer matrix A = [a_{ij}] is said to be in *Hermite normal form* if
(i) the first r rows of A are nonzero and the remaining rows are zero;

(ii) for 1 ≤ i ≤ r, if a_{iji} is the first nonzero entry in
row i of A, then j_{1} < j_{2} < ⋯ < j_{r};

(iii) a_{iji} > 0 for 1 ≤ i ≤ r;

(iv) if 1 ≤ k < i ≤ r, then 0 ≤ a_{kji} < a_{iji}.

Let G be an m × n integer matrix. Then there are various algorithms for finding a unimodular matrix P

such that PG=A is in Hermite normal form and which attempt to reduce coefficient explosion during their execution,

e.g., Kannan-Bachem (1979). This is the one to use for large matrices if G has full row rank, as then P is unique.
The algorithm used in our BCMATH program is the LLL-based method in the paper *Extended gcd and Hermite normal form algorithms via lattice basis reduction*,

George Havas, Bohdan S. Majewski, Keith R. Matthews, Experimental Mathematics, Vol 7 (1998) 125-136 with parameter α = 1. (See slides and corrections to paper.) Also see the examples.

One desirable feature of this algorithm, apart from controlling coefficient explosion, is that if r < m, then the entries of P are expected to be small, with the last m - r rows of P forming a ℤ-basis for the integer lattice of row vectors X such that XA = 0.

*Last modified 10th September 2011*

Return to main page