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., 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