Finitely Generated Abelian Groups

Finitely generated abelian groups arise all over algebraic number theory. For example, they will appear in this book as class groups, unit groups, and the underlying additive groups of rings of integers, and as Mordell-Weil groups of elliptic curves.

In this section, we prove the structure theorem for finitely generated abelian groups, since it will be crucial for much of what we will do later.

Let $ \mathbf{Z}=\{0,\pm 1, \pm 2, \ldots\}$ denote the ring of (rational) integers, and for each positive integer $ n$ let $ \mathbf{Z}/n\mathbf{Z}$ denote the ring of integers modulo $ n$, which is a cyclic abelian group of order $ n$ under addition.

Definition 2.1.1 (Finitely Generated)   A group $ G$ is finitely generated if there exists $ g_1,\ldots, g_n \in G$ such that every element of $ G$ can be expressed as a finite product of positive or negative powers of the $ g_i$.

For example, the group $ \mathbf {Z}$ is finitely generated, since it is generated by $ 1$.

Theorem 2.1.2 (Structure Theorem for Abelian Groups)   Let $ G$ be a finitely generated abelian group. Then there is an isomorphism

$\displaystyle G \cong (\mathbf{Z}/n_1\mathbf{Z}) \oplus (\mathbf{Z}/n_2\mathbf{Z}) \oplus \cdots \oplus
(\mathbf{Z}/n_s\mathbf{Z}) \oplus \mathbf{Z}^{r},
$

where $ n_1>1$ and $ n_1\mid{}n_2\mid{}\cdots \mid{}n_s$. Furthermore, the $ n_i$ and $ r$ are uniquely determined by $ G$.

We will prove the theorem as follows. We first remark that any subgroup of a finitely generated free abelian group is finitely generated. Then we see that finitely generated abelian groups can be presented as quotients of finite rank free abelian groups, and such a presentation can be reinterpreted in terms of matrices over the integers. Next we describe how to use row and column operations over the integers to show that every matrix over the integers is equivalent to one in a canonical diagonal form, called the Smith normal form. We obtain a proof of the theorem by reinterpreting in terms of groups. Finally, we observe by a simple argument that the representation in the theorem is necessarily unique.

Proposition 2.1.3   If $ H$ is a subgroup of a finitely generated abelian group then $ H$ is finitely generated.

The key reason that this is true is that $ G$ is a finitely generated module over the principal ideal domain $ \mathbf {Z}$. We will give a complete proof of a beautiful generalization of Proposition 2.1.3 in the context of Noetherian rings in Section 2.2, but will not prove this proposition here.

Corollary 2.1.4   Suppose $ G$ is a finitely generated abelian group. Then there are finitely generated free abelian groups $ F_1$ and $ F_2$ and a homomorphism $ \psi:F_2 \to F_1$ such that $ G \cong F_1/\psi(F_2)$.

Proof. Let $ x_1,\ldots, x_m$ be generators for $ G$. Let $ F_1=\mathbf{Z}^m$ and let $ \varphi :F_1\to G$ be the map that sends the $ i$th generator $ (0,0,\ldots,1,\ldots,0)$ of $ \mathbf{Z}^m$ to $ x_i$. Then $ \varphi $ is a surjective homomorphism, and by Proposition 2.1.3 the kernel $ \ker(\varphi )$ of $ \varphi $ is a finitely generated abelian group. Let $ F_2 = \mathbf{Z}^n$ and fix a surjective homomorphism $ \psi:F_2
\to \ker(\varphi )$. Then $ F_1 / \psi(F_2)$ is isomorphic to $ G$. $ \qedsymbol$

Suppose $ G$ is a nonzero finitely generated abelian group. By the corollary, there are free abelian groups $ F_1$ and $ F_2$ and a homomorphism $ \psi:F_2 \to F_1$ such that $ G\approx F_1/\psi(F_2)$. Choosing a basis for $ F_1$ and $ F_2$, we obtain isomorphisms $ F_1\approx \mathbf{Z}^n$ and $ F_2\approx \mathbf{Z}^m$ for integers $ n$ and $ m$. We can thus view $ \psi:F_2 \to F_1$ as being given by left multiplication by the $ n\times m$ matrix $ A$ whose columns are the images of the generators of $ F_2$ in $ \mathbf{Z}^n$. The cokernel of this homomorphism is the quotient of $ \mathbf{Z}^n$ by the image of $ A$ (the $ \mathbf {Z}$-span of the columns of $ A$), and this cokernel is isomorphic to $ G$.

By augmenting $ A$ with zero columns or adding (standard basis) rows to $ A$, we may assume that $ m = n$. For example, we would replace

$\displaystyle \left(\begin{matrix}4 \\
2 \end{matrix}\right)$    by $\displaystyle \left(\begin{matrix}4 & 0\\
2 & 0 \end{matrix}\right)
$

and would replace

$\displaystyle \left(\begin{matrix}4 & 2 \end{matrix}\right)$    by $\displaystyle \left(\begin{matrix}4 & 2\\
1 & 0 \end{matrix}\right).
$

The following proposition implies that we may choose a bases for $ F_1$ and $ F_2$ such that the matrix of $ A$ is diagonal, so that the structure of the cokernel of $ A$ will be easy to understand.

Proposition 2.1.5 (Smith normal form)   Suppose $ A$ is an $ n\times n$ integer matrix. Then there exist invertible integer matrices $ P$ and $ Q$ such that $ A'=PAQ$ is a diagonal matrix with entries $ n_1, n_2,\ldots, n_s,0,\ldots,0$, where $ s\geq 0$, $ n_1>1$ and $ n_1\mid n_2 \mid{} \ldots \mid{} n_s$. Here $ P$ and $ Q$ are invertible as integer matrices, so $ \det(P)$ and $ \det(Q)$ are $ \pm 1$. The matrix $ A'$ is called the Smith normal form of $ A$.

We will see in the proof of Theorem 2.1.2 that $ A'$ is uniquely determined by $ A$. An example of a matrix in Smith normal form is

$\displaystyle A=\left(
\begin{matrix}2&0&0 0&6&0 0&0&0
\end{matrix}\right).
$

Proof. The matrix $ P$ will be a product of matrices that define elementary row operations and $ Q$ will be a product corresponding to elementary column operations. The elementary row and column operations over $ \mathbf {Z}$ are as follows:
  1. [Add multiple] Add an integer multiple of one row to another (or a multiple of one column to another).
  2. [Swap] Interchange two rows or two columns.
  3. [Rescale] Multiply a row by $ -1$.
Each of these operations is given by left or right multiplying by an invertible matrix $ E$ with integer entries, where $ E$ is the result of applying the given operation to the identity matrix, and $ E$ is invertible because each operation can be reversed using another row or column operation over the integers.

To see that the proposition must be true, assume $ A\neq 0$ and perform the following steps (compare [Art91, pg. 459]):

  1. By permuting rows and columns, move a nonzero entry of $ A$ with smallest absolute value to the upper left corner of $ A$. Now attempt to make all other entries in the first row and column 0 by adding multiples of row or column 1 to other rows (see step 2 below). If an operation produces a nonzero entry in the matrix with absolute value smaller than $ \vert a_{11}\vert$, start the process over by permuting rows and columns to move that entry to the upper left corner of $ A$. Since the integers $ \vert a_{11}\vert$ are a decreasing sequence of positive integers, we will not have to move an entry to the upper left corner infinitely often.

  2. Suppose $ a_{i1}$ is a nonzero entry in the first column, with $ i>1$. Using the division algorithm, write $ a_{i1} = a_{11}q + r$, with $ 0\leq r < a_{11}$. Now add $ -q$ times the first row to the $ i$th row. If $ r>0$, then go to step 1 (so that an entry with absolute value at most $ r$ is the upper left corner). Since we will only perform step 1 finitely many times, we may assume $ r=0$. Repeating this procedure we set all entries in the first column (except $ a_{11}$) to 0. A similar process using column operations sets each entry in the first row (except $ a_{11}$) to 0.

  3. We may now assume that $ a_{11}$ is the only nonzero entry in the first row and column. If some entry $ a_{ij}$ of $ A$ is not divisible by $ a_{11}$, add the column of $ A$ containing $ a_{ij}$ to the first column, thus producing an entry in the first column that is nonzero. When we perform step 2, the remainder $ r$ will be greater than 0. Permuting rows and columns results in a smaller $ \vert a_{11}\vert$. Since $ \vert a_{11}\vert$ can only shrink finitely many times, eventually we will get to a point where every $ a_{ij}$ is divisible by $ a_{11}$. If $ a_{11}$ is negative, multiple the first row by $ -1$.
After performing the above operations, the first row and column of $ A$ are zero except for $ a_{11}$ which is positive and divides all other entries of $ A$. We repeat the above steps for the matrix $ B$ obtained from $ A$ by deleting the first row and column. The upper left entry of the resulting matrix will be divisible by $ a_{11}$, since every entry of $ B$ is. Repeating the argument inductively proves the proposition. $ \qedsymbol$

Example 2.1.6   The matrix $ \left(
\begin{matrix}-1&2 -3&4
\end{matrix}\right)$ has Smith normal form to $ \left(
\begin{matrix}1&0 0&2
\end{matrix}\right)$, and the matrix $ \left(
\begin{matrix}1&4&9 16&25&36 49&64&81
\end{matrix}\right)$ has Smith normal form $ \left(
\begin{matrix}1&0&0 0&3&0 0&0&72
\end{matrix}\right).$ As a double check, note that the determinants of a matrix and its Smith normal form match, up to sign. This is because

$\displaystyle \det(PAQ) = \det(P)\det(A)\det(Q) = \pm \det(A).$

We compute each of the above Smith forms using SAGE, along with the corresponding transformation matrices. Warning: Currently in Sage the entries down the diagonal are reversed from the discussion above. First the $ 2\times 2$ matrix.

sage: A = matrix(ZZ, 2, [-1,2, -3,4])
sage: S, U, V = A.smith_form(); S
[2 0]
[0 1]
sage: U*A*V
[2 0]
[0 1]
sage: U
[ 1 -1]
[ 0  1]
sage: V
[4 1]
[3 1]
The SAGE matrix command takes as input the base ring, the number of rows, and the entries. Next we compute with a $ 3\times3$ matrix.
sage: A = matrix(ZZ, 3, [1,4,9,  16,25,36, 49,64,81])
sage: S, U, V = A.smith_form(); S
[72  0  0]
[ 0  3  0]
[ 0  0  1]
sage: U*A*V
[72  0  0]
[ 0  3  0]
[ 0  0  1]
sage: U
[  1 -20 -17]
[  0   1  -1]
[  0   0   1]
sage: V
[  93   74   47]
[-156 -125  -79]
[  67   54   34]

Finally we compute the Smith form of a matrix of rank $ 2$:

sage: m = matrix(ZZ, 3, [2..10]); m
[ 2  3  4]
[ 5  6  7]
[ 8  9 10]
sage: m.smith_form()[0]
[0 0 0]
[0 3 0]
[0 0 1]

Proof. [Theorem 2.1.2] Suppose $ G$ is a finitely generated abelian group, which we may assume is nonzero. As in the paragraph before Proposition 2.1.5, we use Corollary 2.1.4 to write $ G$ as a the cokernel of an $ n\times n$ integer matrix $ A$. By Proposition 2.1.5 there are isomorphisms $ Q:\mathbf{Z}^n\to \mathbf{Z}^n$ and $ P:\mathbf{Z}^n\to \mathbf{Z}^n$ such that $ A'=PAQ$ is a diagonal matrix with entries $ n_1, n_2,\ldots, n_s,0,\ldots,0$, where $ n_1>1$ and $ n_1\mid n_2 \mid{} \ldots \mid{} n_s$. Then $ G$ is isomorphic to the cokernel of the diagonal matrix $ A'$, so

$\displaystyle G \cong (\mathbf{Z}/n_1\mathbf{Z}) \oplus (\mathbf{Z}/n_2\mathbf{Z}) \oplus \cdots \oplus
(\mathbf{Z}/n_s\mathbf{Z}) \oplus \mathbf{Z}^{r},
$ (2.1)

as claimed. The $ n_i$ are determined by $ G$, because $ n_i$ is the smallest positive integer $ n$ such that $ nG$ requires at most $ s+r-i$ generators. We see from the representation (2.1.1) of $ G$ as a product that $ n_i$ has this property and that no smaller positive integer does.

$ \qedsymbol$

William Stein 2012-09-24