Finitely Generated Modules over Principal Ideal Domains
Main Theorem
Our goal is to prove the classification theorem for finitely generated modules over PID’s, which asserts that every finitely generated module over a PID is the direct sum of a free module and a finite set of cyclic modules. Depending on how you describe the cyclic modules you get different uniqueness statements.
Theorem: Let $R$ be a principal ideal domain and let $M$ be a finitely generated $R$ module. Then there is an integer $k$ and elements $\pi_1,\ldots, \pi_m$ in $R$ such that $\pi_1\vert \pi_2\vert\cdots\vert \pi_m$ such that
\[M=R^{k}\oplus R/\pi_1 R\oplus\cdots \oplus R/\pi_m R.\]Further, the integer $k$ and the ideals $\pi_i R$ are uniquely determined by $M$. The ideals $\pi_i R$ are called the invariant factors of $M$, and the integer $k$ is its rank.
Notice that if $R=\Z$ and $M$ is finite then this is the fundamental theorem of finite abelian groups with the $\pi_i$ being the invariant factors.
Alternative formulation
Theorem: Let $R$ be a PID and let $M$ be a finitely generated $R$ module. Then there is an integer $k$ and elements $\pi_i\in R$ such that $\pi_i$ is a prime power and
\[M=R^{k}\oplus R/\pi_1 R\oplus\cdots \oplus R/\pi_m R.\]Again, the rank $k$ and the prime power factors $\pi_i$ are unique (up to ordering in this case).
The prime powers $\pi_i$ are called the elementary divisors of $M$.
If $R=\Z$ this is the fundamental theorem of finite abelian groups, asserting that every such group is a finite product of cyclic groups of prime power order, and that the prime powers are unique up to ordering.
Strategy
Our strategy is to use ideas from linear algebra and approach the problem algorithmically.
Suppose that $M$ is generated by $n$ elements $e_1,\ldots, e_n$ over the PID $R$. Then there is a surjective map \(\pi: R^{n}\to M\) defined by $\pi((r_1,\ldots, r_n))=\sum_{i=1}^{n} r_i e_i$.
If $f=(r_1,\ldots, r_n)$ is in the kernel of $\pi$, then
\[\sum_{i=1}^{n} r_{i}e_{i}=0.\]Relations
Because of this, elements of the kernel $N$ of $\pi$ are called relations for the generators $e_{i}$, and $N$ is called the module of relations for $M$.
Since the relation module $N$ of this map is a submodule of $R^{n}$, we know from our discussion of finite generation is generated by (at most) $n$ elements $f_1,\ldots, f_n$.
Let’s assume that our relation module has $n$ generators $f_{1},\ldots, f_{n}$, some of which might be zero.
The relation matrix
Expressing $f_j$ in terms of the $e_i$ yields an $n\times n$ matrix $A=(a_{ij})$ defined by:
\[f_j = \sum a_{ji} e_i\]The columns of the matrix $A$ express the generators $f_j$ of the kernel of $\pi$ in terms of the basis $e_i$ for $R^{n}$.
$A$ is called a relation matrix for $M$.
The kernel as column space of the relation matrix
If, as we do in linear algebra, we express elements of $R^{n}$ as column vectors with $R$ entries, we have a map
\[a: R^{n}\to R^{n}\]defined by $a(v)=Av$ (matrix multiplication by $A$ on a column vector $v$ with entries in $R$).
If the entries of $v$ are $(r_1,\ldots, r_n)$ then $a(v)=\sum_{i=1}^{n} r_i f_i$ and therefore the image of the $R$-linear map $a$ is $N$.
Standard form
We’ve reached a point where our module $M$ is isomorphic to $R^{n}/N$ where $N$ is generated by the columns of our matrix $A$.
We will show the following:
- $N$ is free of rank $m$ where $m\le n$.
- $M$ has a basis $y_1,\ldots, y_m$ with the property that there are elements $b_1,\ldots, b_m\in R$ such that $b_1\vert b_2\vert\cdots \vert b_m$ and $b_1 y_1, b_2 y_2,\ldots, b_m y_m$ are a basis for $N$.
In terms of the relation matrix, we are saying that if we choose our basis $e_1,\ldots, e_n$ and $f_1,\ldots, f_n$ properly, then the corresponding matrix $A$ is diagonal with entries $b_1, b_2, \ldots, b_m, 0,0\ldots 0$ and $b_1\vert b_2\vert\cdots\vert b_m$.
We will do this by modifying the set of generators $f_j$ and $e_i$ so that, at each stage, they continue to be sets of generators, but eventually they have the desired relation.
The result from standard form
If we achieve the standard form, then we have the picture \(R^{n}\to M\) where
\[(r_1,\ldots, r_n)\mapsto \sum r_{i}y_{i}\]and the kernel of this map is
\[N=b_1 y_1 \oplus b_2 y_2 \oplus \cdots\oplus b_m y_m.\]Therefore $R^{n}/N=R/b_1 R \oplus\cdots R/b_m R\oplus R^{n-m}$ which is the structure we are trying to establish.
Alternatively, we can think of $M$ as having generators $e_{1},\ldots, e_{n}$ and relations $b_i e_i=0$
Reduction Operations
We begin with our chosen generators $e_1,\ldots, e_n$ for $M$ and the corresponding generators for the relation module $f_1,\ldots, f_n$, which are related by the matrix $A=(a_{ij})\in M_{n}(R)$ where \(f_{j} = \sum_{i=1}^{n} a_{ji} e_{i}.\)
Suppose that $x,y,z,w$ are elements of $R$ such that $xw-yz=1$.
Modifying the generators of $M$
Lemma: Suppose $1\le t,s\le n$ with $i\not=j$. If we let elements $e_{i}^{\ast}=e_{i}$ for $i\not=t,s$, and also \(\begin{aligned} e_{t}^{\ast} &= xe_{t}+ye_{s}\\ e_{s}^{\ast} &= ze_{t}+we_{s}\\ \end{aligned}\) Then $e_{1}^{\ast},\ldots, e_{n}^{\ast}$ are also generators of $M$.
Proof: Write
Since $e_{i}=e_{i}^{\ast}$ for $i\not=t,s$ and \(\begin{aligned} e_{t} &= we_{t}^{\ast}-ye_{s}^{\ast} \\ e_{s} &= -ze_{t}^{\ast}+xe_{s}^{\ast}. \end{aligned}\) wee see that all of the $e_{i}$ are in the submodule of $M$ generated by the $e_{i}^{\ast}$, and vice versa, so the $e_{i}^{\ast}$ are again a set of generators of $M$.
Row operations
Let’s examine the effect of this change on the relation matrix $A$. If \(m=r_1 e_1+\cdots+r_n e_n.\) then \(m=\sum_{i\not=t,s} r_{i} e_{i}^{\ast} + (r_{t}w-r_{s}z)e_{r}^{\ast} + (-yr_{t}+xr_{s})e_{s}^{\ast}.\)
This means that if we construct the relation matrix $A^{\ast}$ by writing \(f_{j}=\sum a_{ji}^{\ast} e_{i}^{\ast}\) we see that $A^{\ast}$ is obtained from $A$ by modifying rows $t$ and $s$. If we use subscripts to describe rows of matrices then \(\begin{aligned} A^{\ast}_{t} &= wA_{t}-zA_{s} \\ A^{\ast}_{s} &= -yA_{t}+xA_{s} \end{aligned}\)
Column Operations
More generally, we see that, given any relation matrix $A$, and $x,y,z,w$ such that $xw-yz=1$, modifying $A$ by changing rows $t$ and $s$ according to these formulas yields a new relation matrix giving rise to an isomorphic module $M$.
A similar line of argument shows that if we make the same type of modification to the generators $f_{j}$ for the relations, then we modify the relation matrix $A$ by column operations of the same type.
Outline of proof of standard form
Initial remarks
Now suppose we are given an $n\times n$ matrix $A$ with entries in a PID $R$. There is a sequence of row and column operations that reduces it to standard form, so that the reduced matrix is diagonal, the first $k$ diagonal elements are nonzero and the remaining $n-k$ are zero, and the nonzero diagonal elements satisfy
\[a_{11}\vert a_{22}\vert\cdots\vert a_{kk}\]Main Steps
- If $A=0$, we’re done, otherwise swap rows and columns so $a_{11}$ is not zero.
Clear out the first row
- If all $a_{1i}$ for $i>1$ are divisible by $a_{11}$, replace each column $A^{j}$ where $a_{1j}$ is not zero by $A^{j}-a_{11}/a_{1j}A^{1}$. Otherwise, for each column $j=2,\ldots, n$ where $a_{1j}$ is not zero, use the fact that $R$ is a PID to find a generator $d$ for the ideal $(a_{11},a_{1j})$ for each column and write $a_{11}x-a_{1j}y=d$. Then make a column operation using this $x$ and $y$ with $w=a_{11}/d$ and $z=a_{1j}/d$ to obtain a matrix with $a_{11}=d$ and $a_{1j}=0$. At the end of this step, the only nonzero entry in the first row is $a_{11}$.
Clear out the first column
- If all $a_{i1}$ for $i>1$ are divisible by $a_{11}$, replace each row $A_{j}$ with $A_{j}-a_{j1}/a_{11}A_{1}$. Now you’ve got a matrix so that the first row and column are all zero, except for $a_{11}.$ Go to step 4. Otherwise, use the fact that $R$ is a PID to find a generator $d=a_{11}x-a_{j1}y$ and make a row operation using this $x$ and $y$ with $w=a_{11}/d$ and $z=a_{j1}/d$ to obtain a matrix with $a_{11}=d$ and $a_{j1}=0$. At the end of this process, you’ve got a matrix so that $a_{11}$ is the only nonzero entry in the first column; but you may have messed up the first row. So go back to step 2.
Check divisibility; descend to submatrix
- At this point the first row and column of $A$ are zero except for $a_{11}$. If $a_{11}$ divides every entry in the lower right $(n-1)\times (n-1)$ submatrix, then apply this algorithm to that submatrix and continue. If $a_{11}$ does NOT divide every entry in lower submatrix, find a row $A_{j}$ containing an element not divisible by $a_{11}$ and replace the first row $A_{1}$ by $A_{1}+A_{j}$. Now go back to step 2 and continue.
Remarks on the algorithm
There are two things to consider in this algorithm.
First, the loop through steps 2 and 3 must eventually terminate because each time you go through it, you replace $a_{11}$ by a divisor of $a_{11}$. This cannot continue indefinitely, so eventually you will reach step 4.
Second, if $a_{11}$ divides everything in the lower submatrix, then by induction, once that matrix is in standard form, the whole matrix will be in standard form. If $a_{11}$ does not divide everything in the lower submatrix, then the return to step 2 will replace $a_{11}$ by a proper divisor of $a_{11}$ and again, that can’t continue indefinitely.
Constructive for Euclidean rings
The only non-constructive part of this “algorithm” is that we invoke the PID property of $R$ so that, given $a,b$ we can find $ax+by=d$ where $d$ is the gcd of $a$ and $b$. If $R$ is Euclidean, this can be done constructively, and so this algorithm can be carried out in practice.
Uniqueness
Uniqueness in DF
Proof of uniqueness is given in DF, Section 12.1 Theorem 9.