Classification of finitely generated modules over a PID

We show that any submodule of $R^{\oplus n}$ is free, by induction on $n$. If $n = 0$, we have $R^{\oplus n} \cong 0$ and so there is nothing to prove.

Assume that the claim is true for $n-1$. For an arbitrary submodule $N \subseteq R^{\oplus n}$, we want to prove that $N$ is free. If we consider

$$ N^\prime = N \cap (\lbrace 0\rbrace \oplus R^{\oplus (n-1)}) \subseteq \lbrace 0\rbrace \oplus R^{\oplus (n-1)}, $$

this is a submodule of $R^{\oplus (n-1)}$. Then $N^\prime$ is a free module, because $N^\prime$ is a submodule of $R^{\oplus (n-1)}$.

Generators are selected successively inside a submodule of a free module, illustrating how a basis for the submodule is constructed.

Consider the composite $R$-linear map

$$ \varphi : N \hookrightarrow R^{\oplus n} \xrightarrow{\pi_1} R $$

where $\pi_1 : R^{\oplus n} \to R$ is given by projection $(x_1, \ldots, x_n) \mapsto x_1$. Then the image of $N \to R$ is going to be submodule of $R$, which is going to be an ideal. Because $R$ is a principal ideal domain, $\im \varphi = (a_0)$ for some $a_0 \in R$. Note that we have a short exact sequence

$$ 0 \to N^\prime \hookrightarrow N \xrightarrow{\varphi} \im(\varphi) = (a_0) \to 0. $$

If $a_0 = 0$, then $\im \varphi = (0)$ and so $N$ is actually contained in $\lbrace 0\rbrace \oplus R^{\oplus (n-1)}$. Then $N = N^\prime$ is a free module.

Suppose now that $a_0 \neq 0$. Then $a_0 \in \im \varphi$ shows that there exists an $x_0 \in N$ such that $\pi_1(x_0) = a_0$. Using this, we may define the map

$$ N^\prime \oplus R \to N; \quad (x, a) \mapsto x + a x_0. $$

This is clearly an $R$-linear map. We claim that it is bijective. To show that it is injective, suppose that $x + a x_0 = 0$. Applying $\pi_1$ to both sides gives $0 = \pi_1(x) + a \pi_1(x_0) = a a_0$ because $\pi_1(x) = 0$ for $x \in N^\prime$ and $\pi_1(x_0) = a_0$. Then $a_0 \neq 0$ and $a a_0 = 0$ implies $a = 0$ because $R$ is a PID. It follows that $0 = x + ax_0 = x$.

To show that it is surjective, we consider an arbitrary $y \in N$ and check that it can be written as $y = x + a x_0$ for $x \in N^\prime$ and $a \in R$. Because $\pi_1(y) \in \im \varphi = (a_0)$, we can write $\pi_1(y) = a a_0$ for some $a \in R$. Then $\pi_1(y - a x_0) = \pi_1(y) - a \pi_1(x_0) = 0$ and $y - a x_0 \in N$ because $y \in N$ and $x_0 \in N$. Therefore $x = y - a x_0 \in N^\prime$ so that $y = x + a x_0$ for $x \in N^\prime$ and $a \in R$. This shows that $\varphi : N^\prime \oplus R \to N$ is an isomorphism of $R$-modules. Because $N^\prime$ is free, $N \cong N^\prime \oplus R$ is also free.

Consider the ideal

$$ I = \lbrace a_1 x_1 + \cdots + a_n x_n : a_1, \ldots, a_n \in R \rbrace \subseteq R. $$

Because $R$ is a principal ideal, there exists a $d \in R$ such that $I = (d)$. Then (a) follows from $x_1, \ldots, x_n \in I = (d)$, and (b) follows from $d \in (d) = I$. It is also clear that (b) implies (c).

If we define

$$ \mathfrak{a} = \bigcup_{i=1}^\infty \mathfrak{a}_i, $$

this is an ideal of $R$. Because $R$ is a principal ideal domain, we have $\mathfrak{a} = (x)$ for some $x$. This means that $x \in \mathfrak{a} = \bigcup_{i=1}^\infty \mathfrak{a}_i$, so $x \in \mathfrak{a}_n$ for some $n$. It follows that $(x) \subseteq \mathfrak{a}_n \subseteq \mathfrak{a} = (x)$, so $\mathfrak{a}_n = \mathfrak{a}_{n+1} = \cdots$.

We do this by induction on $n$. If $n = 1$, there is nothing to do. For $n = 2$, if $x_1=x_2=0$, then $d=0$ and we may take $P=I$. Otherwise, let $x_1 = d y_1$ and $x_2 = d y_2$, so that $\gcd(y_1, y_2) = 1$. Then what we are finding is a $2 \times 2$ invertible matrix $P$ such that

$$ d P \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = d \begin{bmatrix} 1 \\ 0 \end{bmatrix}. $$

Because $\gcd(y_1, y_2) = 1$, there exist $z_1, z_2 \in R$ such that $y_1 z_1 + y_2 z_2 = 1$. Then we have

$$ d \begin{bmatrix} z_1 & z_2 \\ -y_2 & y_1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \end{bmatrix} = d \begin{bmatrix} 1 \\ 0 \end{bmatrix}. $$

We check that the matrix is invertible because

$$ \begin{bmatrix} z_1 & z_2 \\ -y_2 & y_1 \end{bmatrix} \begin{bmatrix} y_1 & -z_2 \\ y_2 & z_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}. $$

Now assume we can find $P$ for $n-1$. Then there exists a matrix $P_0$ such that

$$ P_0 \begin{bmatrix} x_{n-1} \\ x_n \end{bmatrix} = \begin{bmatrix} \gcd(x_{n-1},x_n) \\ 0 \end{bmatrix}. $$

This means that if we put $1$s on the diagonal, we can build an $n \times n$ matrix $P_1$ such that

$$ P_1 \begin{bmatrix} x_1 \\ \vdots \\ x_{n-1} \\ x_n \end{bmatrix} = \begin{bmatrix} x_1 \\ \vdots \\ \gcd(x_{n-1}, x_n) \\ 0 \end{bmatrix}. $$

Now we can apply the inductive hypothesis and find another $n \times n$ matrix $P_2$ so that

$$ (P_2 P_1) \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = P_2 \begin{bmatrix} x_1 \\ \vdots \\ \gcd(x_{n-1}, x_n) \\ 0 \end{bmatrix} = \begin{bmatrix} \gcd(x_1, \ldots, x_{n-2}, \gcd(x_{n-1}, x_n)) \\ 0 \\ \vdots \\ 0 \end{bmatrix}. $$

This is what we want, by the next exercise.

Let me describe the algorithm for doing this.

Step 1. First, we use Lemma 4.3.9 on the first column of $A$. Then we can multiply an invertible matrix on the left of $A$ to make it into

$$ \begin{bmatrix} d_1 & \ast & \cdots & \ast \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

If we use Lemma 4.3.9 on the first row, we can multiply an invertible matrix on the right and make it into

$$ \begin{bmatrix} d_2 & 0 & \cdots & 0 \\ \ast & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ \ast & \ast & \cdots & \ast \end{bmatrix}. $$

Here, $d_2 = \gcd(d_1, \ast, \ldots, \ast)$ and so $d_2 \mid d_1$. Now we do this again and make it into

$$ \begin{bmatrix} d_3 & \ast & \cdots & \ast \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

As we repeat this process, we get a sequence of ideals

$$ (d_1) \subseteq (d_2) \subseteq (d_3) \subseteq \cdots $$

and thus by Lemma 4.3.8, the sequence stabilizes. In other words, $(d_{a+1}) = (d_a)$ for some $a$. Because $d_{a+1}$ is the greatest common divisor of everything in the first column and row, this means that when $d_a$ is the first row first column entry, every entry in the first row or column is divisible by $d_a$. Without loss of generality, we may assume that the matrix looks like

$$ \begin{bmatrix} d_a & d_a x_2 & \cdots & d_a x_k \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

By doing the elementary column operation that adds $(-x_i)$ times the first column to the $i$th column, we can make the matrix into

$$ \begin{bmatrix} d_a & 0 & \cdots & 0 \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

Step 2. Rewrite $e_1 = d_a$. Our matrix currently looks like

$$ \begin{bmatrix} e_1 & 0 & \cdots & 0 \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

If all the $\ast$ are divisible by $e_1$, we are happy. If not, assume that the $i$th row $j$th column entry is not divisible by $e_1$. Add the $j$th column to the first column, so that not all entries in the first column are divisible by $e_1$. That is, the matrix is

$$ \begin{bmatrix} e_1 & 0 & \cdots & 0 \\ \bullet_2 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ \bullet_n & \ast & \cdots & \ast \end{bmatrix} $$

where $\bullet_2, \ldots, \bullet_n$ are not all divisible by $e_1$. Now do Step 1 at this point. At the first application of Lemma 4.3.9, the first row first column entry becomes $\gcd(e_1, \bullet_2, \ldots, \bullet_n)$.

Let us denote the result of Step 1 by

$$ \begin{bmatrix} e_2 & 0 & \cdots & 0 \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix}. $$

Because $e_2 \mid \gcd(e_1, \bullet_2, \ldots, \bullet_n)$, we have $(e_1) \subsetneq (e_2)$. If we repeat this process, we get a strictly ascending chain of ideals

$$ (e_1) \subsetneq (e_2) \subsetneq \cdots. $$

This contradicts Lemma 4.3.8, and this means that the process cannot continue infinitely. That is, we arrive at a point where that matrix is

$$ \begin{bmatrix} e_b & 0 & \cdots & 0 \\ 0 & \ast & \cdots & \ast \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \ast & \cdots & \ast \end{bmatrix} $$

where all $\ast$ are divisible by $e_b$.

Step 3. Once we have this, we do this on the $(n-1) \times (k-1)$ matrix of $\ast$. Then what we inductively get is a matrix that looks like

$$ \begin{bmatrix} f_1 & 0 & \cdots \\ 0 & f_2 & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix} $$

with $f_1 \mid f_2 \mid \cdots$.

If $R / \mathfrak{a}$ is a field, we can set $\mathfrak{b} = \mathfrak{a}$ and we are done. If not, there exists a nonzero element $[x_1] \in R / \mathfrak{a}$ such that $[x_1]$ does not divide $[1]$. This means that we have

$$ \mathfrak{a} \subsetneq \mathfrak{a}_1 = \mathfrak{a} + (x_1) \subsetneq R. $$

(We have $\mathfrak{a} \subsetneq \mathfrak{a}_1$ because $[x_1] \neq [0]$ in $R / \mathfrak{a}$, and we have $\mathfrak{a}_1 \subsetneq R$ because $[x_1]$ does not divide $[1]$.) If $R / \mathfrak{a}_1$ is a field, we are done, otherwise we can find a larger ideal

$$ \mathfrak{a} \subsetneq \mathfrak{a}_1 \subsetneq \mathfrak{a}_2 \subsetneq R. $$

This process cannot continue forever by Lemma 4.3.8. This means that $R / \mathfrak{a}_i$ is a field for some $i$.

It is clear that there exists a set of generators of size $n$, namely $([1], [0], \ldots, [0])$ through $([0], [0], \ldots, [1])$.

We now have to show that there is no set of generators of size $n-1$. Suppose there exists such a set of generators. Then by definition there is a surjective homomorphism

$$ R^{\oplus (n-1)} \twoheadrightarrow (R / \mathfrak{a}_1) \oplus \cdots \oplus (R / \mathfrak{a}_n). $$

Using Lemma 4.3.13, we find an ideal

$$ \mathfrak{a}_1 \subseteq \mathfrak{a}_2 \subseteq \cdots \subseteq \mathfrak{a}_n \subseteq \mathfrak{b} \subsetneq R. $$

Now there is a surjective linear map $R / \mathfrak{a}_i \twoheadrightarrow R / \mathfrak{b}$. We can direct sum these maps together and define

$$ \varphi : R^{\oplus (n-1)} \twoheadrightarrow (R / \mathfrak{a}_1) \oplus \cdots \oplus (R / \mathfrak{a}_n) \twoheadrightarrow (R / \mathfrak{b})^{\oplus n}. $$

So there is this surjective $R$-linear map $\varphi : R^{\oplus (n-1)} \twoheadrightarrow (R / \mathfrak{b})^{\oplus n}$. Let us write $\mathfrak{b} = (e)$. Then for any $x \in R^{\oplus (n-1)}$ we have

$$ \varphi(e x) = e \varphi(x) = 0 $$

because multiplication by $e$ turns everything in $(R / \mathfrak{b})^{\oplus n}$ to zero. This means that $\ker(\varphi)$ contains the module $\mathfrak{b}^{\oplus (n-1)} \subseteq R^{\oplus (n-1)}$. Using the module version of Exercise 2.5.H, we can factor $\varphi$ as

$$ \varphi : R^{\oplus (n-1)} \to R^{\oplus (n-1)} / \mathfrak{b}^{\oplus (n-1)} = (R / \mathfrak{b})^{\oplus (n-1)} \xrightarrow{\psi} (R / \mathfrak{b})^{\oplus n}. $$

Here, the $R$-linear map $\psi : (R / \mathfrak{b})^{\oplus (n-1)} \twoheadrightarrow (R / \mathfrak{b})^{\oplus n}$ is surjective because $\varphi$ is surjective.

But recall that we have set $k = R / \mathfrak{b}$ to be a field. This means that $(R / \mathfrak{b})^{\oplus (n-1)}$ and $(R / \mathfrak{b})^{\oplus n}$ are vector spaces over $k$. The map $\psi : k^{\oplus (n-1)} \twoheadrightarrow k^{\oplus n}$ is $R$-linear, and for any $[a] \in k$ we have

$$ [a] \psi(x) = a \psi(x) = \psi(ax) = \psi([a] x). $$

So $\psi : k^{n-1} \to k^n$ is a surjective $k$-linear morphism. This contradicts Corollary 2.7.13 because $\dim_k k^{n-1} = n-1$ is smaller than $\dim_k k^n = n$.