Finding the Smith canonical form of an integer matrix

A is an m × n nonzero matrix of integers.
We find unimodular m × m matrix P, unimodular n × n matrix Q and SNF(A), such that PAQ=SNF(A).

SNF(A) = diag(d₁,...,d_r,0,...,0), where r = rank(A). Moreover the d_i are positive and d_i divides d_i+1 for i = 1,...,r-1.

The standard algorithm in Rings, Modules and Linear Algebra by B. Hartley and T. O. Hawkes, Chapman and Hall, 1970, suffers from coefficient explosion.

Our method avoids this problem by applying the HMM algorithm to A, say B=HNF(A), then get C=HNF(B^t), replacing A by C^t and repeating the process until there are only zero entries below the diagonal of C. Eventually A is converted to a matrix PAQ, whose only nonzero entries are positive integers c₁₁,...,c_rr. This is not quite the Smith normal form of A. For example diag(4,6,8,5) has to be converted to diag(1,2,4,120).

If c₁₁ ≠ 1, we add columns 2,...,r to column 1 and perform the above procedure on the altered matrix. The new 1-1 entry is in fact the gcd(c₁₁,...,c_rr) and is invariant factor d₁. Proceeding to c₂₂, if c₂₂ ≠ 1, we repeat the procedure, until we reach the last invariant factor d_r.

(Ideally all this should be carried out on a diminishing-sized r × r diagonal matrix diag(c₁₁,...,c_rr), with row and column operations also being carried out on the m × m P and n × n Q found above.)

References

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

The matrix can be entered 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 25th September 2011
Return to main page