Proof of Finitely Generated Module Theorem Over EDs by Matrices (12.1.19)

Dummit and Foote Abstract Algebra, section 12.1, exercise 19:

By the previous two exercises we may perform elementary row and column operations on a given relations matrix by choosing different generators for $R^n$ and $\text{ker }φ$. If all relation matrices are the zero matrix then $\text{ker }φ=0$ and $M=R^n$. Otherwise let $a_1$ be a nonzero g.c.d. of all the entries in a fixed initial relations matrix for $M$.

(a) Prove that by elementary row and column operations we may assume $a_1$ occurs in a relations matrix $(a_{ij})$ where $a_1 \mid a_{ij}$ for all $i,j$.
(b) Prove there is a relations matrix of the form $(a_{ij})$ where $a_{1,1} = a_1 | a_{ij}$ for all $i,j$ and $a_{1k}=a_{k1}=0$ for all $k > 1$.
(c) Let $a_2$ be a g.c.d. of all the entries except the element $a_1$ in the relations matrix in (b). Prove there is a relations matrix of the form above where additionally $a_{2,2} = a_2$ and $a_{2k} = a_{k2} = 0$ for $k \neq 2$.
(d) Prove there is a relations matrix diagonalized from the top left $a_1,a_2,...,a_k$ for some $k ≤ n$ such that $a_1 \mid a_2 \mid ... \mid a_k$. Derive the theorem for finitely generated modules over Euclidean Domains.

Proof: (a,b) Let $N : R → \mathbb{N}$ be the norm on $R$. For a matrix $M$ with entries in $R$ define $N(M)$ to be the minimum norm taken over the nonzero entries over $M$. For $A$ the initial relations matrix, let $A'$ be a minimal matrix attainable from $A$ by elementary row and column operations with regard to $N(A')$, and let $a_1$ be the nonzero entry of $A'$ possessing such minimum norm. Move $a_1$ to position $(1,1)$ by a row and column interchange. We claim $a_1$ divides all the entries of $A'$, and as such is the g.c.d. of all the entries of $A$ (since any divisor of all the entries of $A$ still acts as a divisor after an operation, and the operation is reversible). First, we show $a_1 \mid a_{1i}$ and $a_1 \mid a_{i1}$. By definition of the norm write $a_{1i} = qa_1 + r$, and subtract $q$ times the first column from the $i^{th}$ column to set $r$ in the $(1,i)$ position; since $N(r) < N(a_1)$ or $r = 0$, we must have the latter by the minimality of $A'$, and thus $a_1 \mid a_{1i}$. The case for the first column is parallel.

Now attain a matrix like the one in (b) by subtracting appropriate multiples of the first row and column. We show $a_1 \mid a_{ij}$ for all $i,j$ and we will be done. Add the $i^{th}$ row to the first to set $a_{ij}$ in the $(1,j)$ position while still retaining $a_1$ in the $(1,1)$ position (as the entry in the $(i,1)$ is zero), and as above prove the remainder of the division is zero. This is matrix $B$.

(c) Simply iterate the process of (a,b) by focusing on the matrix $B_{1,1}$. These operations will not disturb the outer part of the matrix because of the zeros.

(d) Continue iterating to obtain the matrix in (d). By considering the new basis for $R^n$, we have $$R^n/\text{ker }φ = (R~⊕~...~⊕~R) / (Ra_1~⊕~...~⊕~Ra_k~[⊕~0~⊕~...~⊕~0]) ≅$$ $$R^{n-k}~⊕~R/(a_1)~⊕~...~⊕~R/(a_k)~\square$$ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Though the above proof is nonconstructive, a process for obtaining such a matrix with minimal norm can be described as follows: Given $A$, move the nonzero element with minimal norm to the top left. Use Euclid's algorithm to obtain the smallest possible norm among the elements of the first row, which is a g.c.d. of the row. Subtract the other elements of the row to zero and repeat with the first column. Now if $a_{1,1}$ doesn't divide $a_{ij}$ then add row $i$ to row $1$ and use Euclid's algorithm between $a_{1,1}$ and $a_{1,j}$ to obtain an element of smaller norm. Repeat until completion.