Smith Normal Form - Algorithm

Algorithm

Our first goal will be to find invertible square matrices S and T such that the product S A T is diagonal. This is the hardest part of the algorithm and once we have achieved diagonality it becomes relatively easy to put the matrix in Smith normal form. Phrased more abstractly, the goal is to show that, thinking of A as a map from (the free R-module of rank n) to (the free R-module of rank m), there are isomorphisms and such that has the simple form of a diagonal matrix. The matrices S and T can be found by starting out with identity matrices of the appropriate size, and modifying S each time a row operation is performed on A in the algorithm by the same row operation, and similarly modifying T for each column operation performed. Since row operations are left-multiplications and column operations are right-multiplications, this preserves the invariant where denote current values and A denotes the original matrix; eventually the matrices in this invariant become diagonal. Only invertible row and column operations are performed, which ensures that S and T remain invertible matrices.

For a in R \ {0}, write δ(a) for the number of prime factors of a (these exist and are unique since any PID is also a unique factorization domain). In particular, R is also a Bézout domain, so it is a gcd domain and the gcd of any two elements satisfies a Bézout's identity.

To put a matrix into Smith normal form, one can repeatedly apply the following, where t loops from 1 to m.