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(d1,...,dr,0,...,0), where r = rank(A). Moreover the di are positive and di divides di+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(Bt), replacing A by Ct 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 c11,...,crr. 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 c11 ≠ 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(c11,...,crr) and is invariant factor d1. Proceeding to c22, if c22 ≠ 1, we repeat the procedure, until we reach the last invariant factor dr.

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


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.

    Enter m(≤ 50):        Enter n(≤ 50):

    Enter the m × n matrix entries :

Last modified 25th September 2011
Return to main page