### 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_{1},...,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_{11},...,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_{11} ≠ 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_{11},...,c_{rr}) and is invariant factor d_{1}. Proceeding to c_{22},
if c_{22} ≠ 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_{11},...,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