## Every square matrix over a Euclidean domain can be diagonalized by elementary row and column operations

Show that if $A$ is a matrix over a Euclidean domain $R$, then there is a sequence of elementary row and column operations (as described here and here) which, when performed on $A$, result in a matrix $\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}$ such that $D = [d_{i,j}]$ is square and diagonal and if $d_{1,1},\ldots, d_{k,k}$ are the nonzero diagonal entries of $D$ ($k \leq n$), we have $d_{i,i} | d_{j,j}$ whenever $i \leq j$.

Conclude that if $M$ is a finitely generated $R$-module with relations matrix $A$ (see here for a discussion of relations matrices) then $M \cong R^{n-k} \oplus \bigoplus_{i=1}^k R/(d_i)$.

Let $N : R \rightarrow \mathbb{N}$ denote the Euclidean norm on $R$.

Note first that if $A = 0$, there is nothing to show. If $A \neq 0$, we proceed by induction on the number $m$ of rows of $A$.

For the base case $m = 1$, say $A = [a_{1,1}\ a_{1,2}\ \cdots\ a_{1,n}]$. If $n = 1$ there is nothing to show, so we assume $n \geq 2$. We now proceed by induction on $\sum_{i=2}^n N(a_{1,i})$. For the base case, if $\sum_{i=2}^n N(a_{1,i}) = 0$, then $a_{1,i} = 0$ for each $2 \leq i \leq n$, and so $A = [a_{1,1} | 0]$ has the desired form. For the inductive step, suppose that for all $1 \times n$ matrices $B = [b_{1,1}\ b_{1,2}\ \cdots\ b_{1,n}]$ such that $\sum_{i=2}^n N(b_{1,i}) \leq K$, $B$ can be diagonalized by some sequence of elementary row and column operations. Now suppose $\sum_{i=2}^n N(a_{1,i}) = K+1$. Using column operation 1 (swap two columns), rearrange the columns of $A$ so that $a_{1,1}$ has minimal norm. By the Division Algorithm, there exist $q_i$ and $r_i$ such that $a_{1,i} = q_ia_{1,1} + r_i$ and either $r_i = 0$ or $N(r_i) < N(a_{1,1})$ for each $2 \leq i \leq n$. Using column operation 2 (add a multiple of one column to a different one) $n-1$ times, one for each column after the first, we can put $A$ in the form $[a_{1,1}\ r_2\ \cdots\ r_n]$. Now $\sum_{i=2}^n N(r_i) < \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^n N(a_{1,i})$. 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 $A$. This proves our base case, where $A$ has one row.

Suppose now that the result holds for every matrix having at most $m$ rows, and let $A$ be an $(m+1) \times n$ matrix. Say $A = \begin{bmatrix} a_{1,1} & R_1 \\ C_1 & A_1 \end{bmatrix}$, where $R_1 = [r_{1,2}\ cdots\ r_{1,n}]$ and $C_1 = [c_{2,1}\ \cdots\ c_{m+1,1}]^\mathsf{T}$.

We next claim that there is a sequence of elementary row and column operations which transforms $A$ into a matrix of the form $\begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}$. To prove this, we proceed by induction on $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i})$. (Note that it may be the case that $n = 1$. In this case the sum over the $r$ is empty and thus 0. However, the sum over the $c$ is not empty.) If $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = 0$, then we have $c_{i,1} = r_{1,j} = 0$ for each $2 \leq i \leq m+1$ and $2 \leq j \leq n$, and so $A = \begin{bmatrix} a_{1,1} & 0 \\ 0 & A_1 \end{bmatrix}$ has the desired form. For the induction hypothesis, suppose that for some $K \in \mathbb{N}$, every matrix $B$ can be put in the desired form provided $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) \leq K$, and suppose that for our $A$ we have $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1$. 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 $A = 0$ and there is nothing to show.) Now by the Division Algorithm in $R$, there exist $q_i,t_j,u_i,v_j$ such that $r_{1,i} = q_ia_{1,1} + u_i$, $c_{j,1} = t_ja_{1,1} + v_j$, $0 \leq N(u_i) < N(a_{1,1})$, and $0 \leq N(v_j) < N(a_{1,1})$. Using elementary row and column operations of type 2 (add a multiple of one row/column to a different row/column) we can replace $r_{1,i}$ with $u_i$ and likewise replace $c_{j,1}$ by $v_j$. Note now that $\sum_{i=2}^{m+1} N(v_j) + \sum_{i=2}^n N(u_i) < \sum_{i=2}^{m+1} N(a_{1,1}) + \sum_{i=2}^n N(a_{1,1})$ $\leq \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1$. By the induction hypothesis, there is a sequence of elementary row and column operations which puts the new $A$ in the desired form, and so (performing these one after the other) we can put the original matrix $A$ in the desired form.

Now $A$ can be put in the form $\begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}$ by elementary row and column operations. Note that any row or column operation we perform on $A_1$, when performed analogously on $A$, does not change the entry $a_1$ or introduce new nonzero elements to row and column 1. Since (as we assume by the induction hypothesis) the matrix $A_1$ can be diagonalized, then $A$ can also be diagonalized by elementary row and column operations.

We have thus shown by induction that every matrix $A$ 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 $D$ is square and has all nonzero entries on the main diagonal. We proceed by induction on the dimension of $D$. For the base case, where $D$ has dimension $1 \times 1$, there is nothing to show. Suppose now that every square diagonal matrix $D$ of dimension $n$ can have its diagonal entries divisibility-ordered by elementary row and column operations and let $D = \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix}$ be a square diagonal matrix of dimension $n+1$. We claim that $d_1$ can be replaced by the greatest common divisor of all the $d_i$, and that each remaining $d_i$ can be replaced by a linear combination of the $d_i$s, via elementary row and column operations. We will show this for one $d_i$. Note that if $D$ is diagonal, then row and column operations which only operate on two rows and columns (say $a$ and $b$) do not affect the rest of the matrix. For this reason we can focus on a $2 \times 2$ matrix, say $\begin{bmatrix} d_1 & 0 \\ 0 & d_i \end{bmatrix}$. Since $R$ is a Euclidean domain, using the extended Euclidean Algorithm we can find $x$ and $y$ such that $\mathsf{gcd}(d_1,d_i) = xd_1 + yd_i$. Using a column/row operation of type 2, we can obtain $\begin{bmatrix} d_1 & xd_1 + yd_i \\ 0 & d_i \end{bmatrix}$. Swapping rows (or columns), we have $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & d_1 \\ d_i & 0 \end{bmatrix}$. If $d_1 = a_1\mathsf{gcd}(d_1,d_i)$, then again we can obtain $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ d_i & a_1d_i \end{bmatrix}$, and so $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ 0 & a_1d_i \end{bmatrix}$. Repeating this procedure for each diagonal entry (except the first), and since greatest common divisor is associative, we have a diagonal matrix $\begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix}$ where $d_1$ divides each diagonal entry of $D_1$. By induction, $D$ is row/column equivalent to a diagonal matrices whose diagonal entries are ordered by divisibility.

Finally, suppose we have a finitely generated $R$-module $M$, with (say) a generating set of cardinality $n$ and corresponding surjective homomorphism $\varphi : R^n \rightarrow M$. By the preceding result, there exists a basis $B = \{e_1, \ldots, e_n\}$ for $R^n$ and a generating set $E = \{e_1,\ldots,e_m\}$ for $\mathsf{ker}\ \varphi$ such that the corresponding relations matrix is of the form $\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}$, $D$ is square of dimension $k \leq n$ and has no zero diagonal entries, and the diagonal entries of $D$ are ordered by divisibility. In particular, we have $\mathsf{ker}\ \varphi = Rd_1 + \cdots Rd_k = (d_1) \oplus \cdots \oplus (d_k) \oplus 0^{n-k}$. Then by this previous exercise, $M \cong R/\mathsf{ker}\ \varphi \cong R/(d_1) \oplus \cdots \oplus R/(d_k) \oplus R^{n-k}$. Note that if any $d_i$ are units, then the corresponding quotient $R/(d_i)$ is trivial.

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