### 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., *Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix*,
Ravindran Kannan and Achim Bachem, Siam J. Computing, **8** (1979) 499-507. 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. (See slides and corrections to paper.) Also see the examples and
*Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications*, Murray R. Bremner, CRC Press 2011.

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.

Enter the matrix of integers, either

(i) as a string of mn integers separated by spaces,

or

(ii) cut and pasted from a text file, with entries separated by spaces and each row ended by a newline:

*Last modified 29th April 2016*

Return to main page