Show that if is a matrix over a Euclidean domain , then there is a sequence of elementary row and column operations (as described here and here) which, when performed on , result in a matrix such that is square and diagonal and if are the nonzero diagonal entries of (), we have whenever .

Conclude that if is a finitely generated -module with relations matrix (see here for a discussion of relations matrices) then .

Let denote the Euclidean norm on .

Note first that if , there is nothing to show. If , we proceed by induction on the number of rows of .

For the base case , say . If there is nothing to show, so we assume . We now proceed by induction on . For the base case, if , then for each , and so has the desired form. For the inductive step, suppose that for all matrices such that , can be diagonalized by some sequence of elementary row and column operations. Now suppose . Using column operation 1 (swap two columns), rearrange the columns of so that has minimal norm. By the Division Algorithm, there exist and such that and either or for each . Using column operation 2 (add a multiple of one column to a different one) times, one for each column after the first, we can put in the form . Now . By the inductive hypothesis, there is a sequence of elementary row and column operations which diagonalize this new matrix, and so there is a sequence of elementary row and column operations which diagonalizes . This proves our base case, where has one row.

Suppose now that the result holds for every matrix having at most rows, and let be an matrix. Say , where and .

We next claim that there is a sequence of elementary row and column operations which transforms into a matrix of the form . To prove this, we proceed by induction on . (Note that it may be the case that . In this case the sum over the is empty and thus 0. However, the sum over the is not empty.) If , then we have for each and , and so has the desired form. For the induction hypothesis, suppose that for some , every matrix can be put in the desired form provided , and suppose that for our we have . Now among the entries of our matrix, choose a nonzero element of minimal norm and use elementary row and column operations of type 1 (swap) to put this entry in position (1,1). (If no such entry exists, then and there is nothing to show.) Now by the Division Algorithm in , there exist such that , , , and . Using elementary row and column operations of type 2 (add a multiple of one row/column to a different row/column) we can replace with and likewise replace by . Note now that . By the induction hypothesis, there is a sequence of elementary row and column operations which puts the new in the desired form, and so (performing these one after the other) we can put the original matrix in the desired form.

Now can be put in the form by elementary row and column operations. Note that any row or column operation we perform on , when performed analogously on , does not change the entry or introduce new nonzero elements to row and column 1. Since (as we assume by the induction hypothesis) the matrix can be diagonalized, then can also be diagonalized by elementary row and column operations.

We have thus shown by induction that every matrix over a Euclidean domain can be diagonalized. It remains to be seen that these diagonal entries can be ordered by divisibility. We can assume that our matrix is square and has all nonzero entries on the main diagonal. We proceed by induction on the dimension of . For the base case, where has dimension , there is nothing to show. Suppose now that every square diagonal matrix of dimension can have its diagonal entries divisibility-ordered by elementary row and column operations and let be a square diagonal matrix of dimension . We claim that can be replaced by the greatest common divisor of all the , and that each remaining can be replaced by a linear combination of the s, via elementary row and column operations. We will show this for one . Note that if is diagonal, then row and column operations which only operate on two rows and columns (say and ) do not affect the rest of the matrix. For this reason we can focus on a matrix, say . Since is a Euclidean domain, using the extended Euclidean Algorithm we can find and such that . Using a column/row operation of type 2, we can obtain . Swapping rows (or columns), we have . If , then again we can obtain , and so . Repeating this procedure for each diagonal entry (except the first), and since greatest common divisor is associative, we have a diagonal matrix where divides each diagonal entry of . By induction, is row/column equivalent to a diagonal matrices whose diagonal entries are ordered by divisibility.

Finally, suppose we have a finitely generated -module , with (say) a generating set of cardinality and corresponding surjective homomorphism . By the preceding result, there exists a basis for and a generating set for such that the corresponding relations matrix is of the form , is square of dimension and has no zero diagonal entries, and the diagonal entries of are ordered by divisibility. In particular, we have . Then by this previous exercise, . Note that if any are units, then the corresponding quotient is trivial.

By the uniqueness portion of the Fundamental Theorem of Finitely Generated Modules over a PID, the (nonunit) are precisely the invariant factors of .