invariant become diagonal. Only invertible row and column operations are performed, which ensures that and remain invertible matrices. For , write for the number of prime factors of (these exist and are unique since any PID is also a unique factorization domain). In particular, 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 loops from 1 to . Step I: Choosing a pivot Choose to be the smallest column index of with a non-zero entry, starting the search at column index if . We wish to have ; if this is the case this step is complete, otherwise there is by assumption some with , and we can exchange rows and , thereby obtaining . Our chosen pivot is now at position . Step II: Improving the pivot If there is an entry at position (k,jt) such that , then, letting , we know by the Bézout property that there exist σ, τ in R such that By left-multiplication with an appropriate invertible matrix L, it can be achieved that row t of the matrix product is the sum of σ times the original row t and τ times the original row k, that row k of the product is another linear combination of those original rows, and that all other rows are unchanged. Explicitly, if σ and τ satisfy the above equation, then for and (which divisions are possible by the definition of β) one has so that the matrix is invertible, with inverse Now L can be obtained by fitting into rows and columns t and k of the identity matrix. By construction the matrix obtained after left-multiplying by L has entry β at position (t,jt) (and due to our choice of α and γ it also has an entry 0 at position (k,jt), which is useful though not essential for the algorithm). This new entry β divides the entry that was there before, and so in particular ; therefore repeating these steps must eventually terminate. One ends up with a matrix having an entry at position (t,jt) that divides all entries in column jt. Step III: Eliminating entries Finally, adding appropriate multiples of row t, it can be achieved that all entries in column jt except for that at