(i) the first r rows of A are nonzero and the remaining rows are zero;
(ii) for 1 ≤ i ≤ r, if aiji is the first nonzero entry in row i of A, then j1 < j2 < ⋯ < jr;
(iii) aiji > 0 for 1 ≤ i ≤ r;
(iv) if 1 ≤ k < i ≤ r, then 0 ≤ akji < aiji.
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,
(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