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_{ij_i} is the first nonzero entry in row i of A, then j₁ < j₂ < ⋯ < j_r;

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

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

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 1st November 2022
Return to main page