Today I Learned

March 2nd

Today I learned a proof of the classification of finitely generated abelian groups from the Smith normal form, from here . The overarching idea is to view finitely generated abelian groups as "just'' $\ZZ$-modules and then focus on $\ZZ$'s structure. That is, we note that $G$ is finitely generated and abelian if and only if there is a surjective homomorphism\[\ZZ^n\to G\]for some nonnegative integer $n.$ Formally, $G$ is finitely generated by $\{\alpha_1,\ldots,\alpha_n\}$ means that every element of $G$ can be written as a product of powers of the $\alpha_\bullet,$ but being abelian means that all elements can be rearranged to look like\[\alpha_1^{\nu_1}\cdots\alpha_n^{\nu_n}\in G.\]Taking $(\nu_1,\ldots,\nu_n)\in\ZZ^n$ to the above element is our surjective homomorphism. Anyways, the point is that we can understand $G$ by fixing $K\subseteq\ZZ^n$ the kernel of $\ZZ^n\to G$ so that\[\frac{\ZZ^n}K\cong G.\]In particular, it suffices to understand subgroups of $\ZZ^n.$

Before continuing, we need a size bound on $K.$

This pretty much follows from induction. If $n=0,$ then $K\subseteq\ZZ^0=\{e\}$ must be the identity, so there is nothing to prove. Else suppose $n \gt 1.$ The trick is to project onto the $n$th coordinate: note that\[\pi_n:(k_1,\ldots,k_n)\mapsto k_n\]is a homomorphism of groups into $\ZZ.$ All subgroups of $\ZZ$ take form $d\ZZ,$ so we fix $d_n$ a generator of this group; pick $(d_1,\ldots,d_n)\in K$ to be a corresponding element of $K.$ Now, for any $(k_1,\ldots,k_n)\in K,$ we know $k_n\in d_n\ZZ,$ so we can find $\ell\in\ZZ$ so that\[(k_1,\ldots,k_n)-\ell(d_1,\ldots,d_n)=(k_1-\ell d_1,\ldots,k_{n-1}-\ell d_{n-1},0).\]This operation of zeroing out the last coordinate commutes with inversion ($\ell\mapsto-\ell$) and addition (add the $\ell$s), so these elements are a subgroup of $K\cap\left(\ZZ^{n-1}\times\{0\}\right).$ That is, these elements are a subgroup of $\ZZ^{n-1},$ so there is a surjective homomorphism\[\ZZ^{n-1}\to K\cap\left(\ZZ^{n-1}\times\{0\}\right).\]Adding back in $(d_1,\ldots,d_n)$ will make the domain $\ZZ^{n-1}\oplus\ZZ\cong\ZZ^n$ and the image onto $K$ because all elements of $K$ had a representative in $K\cap\left(\ZZ^{n-1}\times\{0\}\right)\oplus\ZZ(d_1,\ldots,d_n).$ So we are done here. $\blacksquare$

With a size bound in hand, we can classify all subgroups $K.$

Note that we are permitting $d_\bullet=0,$ but this would force all components after $d_\bullet$ to also be $0.$ Using our size bound, the main idea here is to fix our generators $k_\ell:=(k_{1\ell},\ldots,k_{n\ell})$ for $1\le\ell\le n$ and then "row-reduce'' the matrix\[M:=\begin{bmatrix} k_{11} & k_{12} & \cdots & k_{1n} \\ k_{21} & k_{22} & \cdots & k_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ k_{n1} & k_{n2} & \cdots & k_{nn}\end{bmatrix}.\]The point is that the image of $M$ under all $\ZZ^n$ is exactly $K,$ so now we're more or less solving a linear algebra problem. In particular, it will be sufficient to show that the image of $M$ is isomorphic to the image of some matrix that looks like\[D=\begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_n\end{bmatrix},\]where $d_1\mid d_2\mid\cdots\mid d_n,$ and $\ZZ^n/D\ZZ^n\cong\ZZ^n/M\ZZ^n.$ It remains to show how we do this, but we note that it feels quite similar to row-reduction in linear algebra.

We begin with column operations because they aren't supposed to change the image. We note that we need to be somewhat careful because division is not allowed, so our column operations are the following.

• We can swap two columns. Effectively this swaps vectors $k_a$ and $k_b$ in the basis of $K.$ Formally, the image doesn't change because for vector $v=(v_1,\ldots,v_n),$ we have \[Mv=\sum_{\ell=1}^nv_\ell k_\ell=\sum_{\substack{\ell=1\\\ell\ne a,b}}^nv_\ell k_\ell+k_bv_b+v_ak_a.\] That is, we take $(v_1,\ldots,v_b,\ldots,v_a,\ldots,v_n)$ to recover $Mv.$ Swapping back gives the reverse inclusion.

• We can negate a column. Suppose we took $k_a\mapsto-k_a.$ Formally, the image doesn't change because for vector $v=(v_1,\ldots,v_n),$ we have \[Mv=\sum_{\ell=1}^nv_\ell k_\ell=\sum_{\substack{\ell=1\\\ell\ne a}}^nv_\ell k_\ell+(-v_a)(-k_a).\] That is, we take $(v_1,\ldots,-v_a,\ldots,v_n)$ to recover $Mv.$ Negating back gives the reverse inclusion.

• We can add one column to another one. Effectively this changes the basis of $K$ from having a vector $k_a$ to $k_a+k_b.$ The image does not change because for vector $v=(v_1,\ldots,v_n),$ we have \[Mv=\sum_{\ell=1}^nv_\ell k_\ell=\sum_{\substack{\ell=1\\\ell\ne a,b}}^nv_\ell k_\ell+v_a(k_a+k_b)+(v_b-v_a)k_b.\] That is, we take $(v_1,\ldots,v_a,\ldots,v_b-v_a,\ldots,v_n)$ to recover $Mv.$ Negating $k_a,$ adding it back to $k_a+k_b,$ and negating $-k_a$ back to $k_a$ gives the reverse inclusion.

These turn out to be insufficient to get the result we want, so we consider row operations as well. These will change the subgroup $K,$ but we will get out an isomorphic one. Some extra care is required, however, to ensure modding out from $\ZZ^n$ still gives isomorphic quotients.

• We can swap two rows. In effect, we take each basis vector $k_\ell=(k_{1\ell},\ldots,k_{a\ell},\ldots,k_{b\ell},\ldots,k_{n\ell})$ to a basis vector $k_\ell'=(k_{1\ell},\ldots,k_{b\ell},\ldots,k_{a\ell},\ldots,k_{n\ell})$ of some group $K'.$ In fact, name this operation $\sigma,$ and it is our isomorphism.

  We don't show this formally, but it is a homomorphism because one can add and then swap or swap and then add; it is surjective by definition of $K'$; it is injective because the only vector swapping to $(0,\ldots,0)$ would have to start with all $0$s to begin with.

  We also have $\ZZ^n/K\cong\ZZ^n/K'$ because the isomorphism extends to $\ZZ^n$: take $\ZZ^n$ to $\ZZ^n$ via $\sigma$ and then mod out by $K$; the kernel is $K'.$

• We can negate a row. In effect, we take each basis vector $k_\ell=(k_{1\ell},\ldots,k_{a\ell},\ldots,k_{n\ell})$ to a basis vector $k_\ell'=(k_{1\ell},\ldots,-k_{a\ell},\ldots,k_{n\ell})$ of some group $K'.$ In fact, name this operation $\sigma,$ and it is our isomorphism.

  Again, we don't show this formally, but it is a homomorphism because negation distributes over addition; it is surjective by definition of $K'$; it is injective because to get to $(0,\ldots,0),$ we can negate back to see the original vector had to be all $0$s.

  We still have $\ZZ^n/K\cong\ZZ^n/K'$ for the same reason: take $\ZZ^n$ to $\ZZ^n$ via $\sigma$ and then mod out by $K$; the kernel is $K'.$

• We can add one row to another row. In effect, we take each basis vector $k_\ell=(k_{1\ell},\ldots,k_{a\ell},\ldots,k_{n\ell})$ to a basis vector $k_\ell'=(k_{1\ell},\ldots,k_{a\ell}+k_{b\ell},\ldots,k_{n\ell})$ of some group $K'.$ In fact, name this operation $\sigma,$ and it is our isomorphism.

  We still don't show this formally, but it is a homomorphism because we can add the $k_{b\bullet}$ elements before or after; it is surjective by definition of $K'$; it is injective because to get to $(0,\ldots,0),$ we must have had $k_b=0,$ so we must have had $k_a=0,$ and everything else would have to be $0$ automatically.

  And of course, $\ZZ^n/K\cong\ZZ^n/K'$ because we can take $\ZZ^n$ to $\ZZ^n$ via $\sigma$ and then mod out by $K$; the kernel is $K'.$

More or less, we can picture these operations as applying some module transformation on $K,$ which does change $K,$ but not in any meaningful way.

Anyways, it remains to show how we use these column and row operations to "row-reduce.'' We take the following definition.

So we have the following (sub)lemma, which will complete the proof of the lemma as discussed above.

We induct on $n.$ If $n=1$ (or $n=0$), there is nothing to show. For the inductive step, it suffices to show that column operations can turn $M$ into a matrix\[\begin{bmatrix} d & 0 \\ 0 & M'\end{bmatrix},\]where each element of $M'$ is divisible by $d,$ From here, we apply the inductive hypothesis on $M',$ for column and row operations can't change the fact that every entry is divisible by $d,$ so every element of the Smith normal form of $M'$ will be divisible by $d.$

We divide the reduction into two parts.

• We begin by noting that we can certainly transform any matrix $M$ into the form \[\begin{bmatrix} d & 0 \\ 0 & M' \end{bmatrix},\] without requiring each element of $M'$ to be divisible by $d.$ This is done by repeated division algorithm: because we are allowed to negate and repeated add columns, we can apply the division algorithm to entries of the first row and column.

  If all elements are $0$ already, we're done. Else swap columns or rows to make the top-left element $d$ nonzero. Now, using division by $d,$ each element of the first column and row will be smaller (in absolute value) than $d.$ If they're all $0,$ then we're done; else swap to replace the current $d$ with some smaller (in absolute value) nonzero value and repeat the divisions. Note that the top-left position is always nonzero.

  We always have the top-left position at least each element in the first row and column, and this process requires the top-left element to strictly decrease (in absolute value) while always being nonzero. Because $\ZZ$ is well-ordered, this must terminate, and it the top-left position will terminate to a nonzero value.

• Now suppose that we are in the form \[\begin{bmatrix} d & 0 \\ 0 & M' \end{bmatrix},\] but some element in $M'$ is not divisible by $d.$ Well, if an element in the $k$th row isn't divisible by $d,$ then add the $k$th row to the first, and apply the first step. If still someone isn't divisible by the new $d,$ we can repeat the process. Note that the fact some element is not divisible by $d$ means that this element is nonzero, so the new value of $d$ will surely be nonzero.

  We note further that adding the $k$th row to the first does not change $d.$ But if $d$ starts nonzero (as it must be after the first iteration of this process), then the resulting divisions in the above process imply that the value of $d$ will decrease (in absolute value) while still being nonzero. So $d$ is decreasing (in absolute value) and nonzero, so well-order of $\ZZ$ requires this to terminate.

Applying the first process and then repeatedly applying the second process will eventually terminate to the desired form with each element of $M'$ divisible by $d.$ This completes the proof of the lemma. $\blacksquare$

It remains to turn this into a classification of finitely generated abelian groups. This follows from the discussion at the beginning along with our classification of subgroups of $\ZZ^n.$

Because $G$ is finitely generated (of dimension $\le n$) and abelian, we have a surjective homomorphism\[\ZZ^n\to G.\]Let $K$ be the kernel of this homomorphism so that $G\cong\ZZ^n/K$. Because of our work with the Smith normal form, we know that $K$ is isomorphic to a a group of the form $\prod_{k=1}^nd_k\ZZ$ such that $d_1\mid d_2\mid\cdots\mid d_n,$ and even\[G\cong\frac{\ZZ^n}K\cong\frac{\ZZ^n}{d_1\ZZ\times\cdots\times d_n\ZZ}.\]It is a fact that $(A\times B)/(C\times D)\cong A/C\times B/D$ (take $A\times B$ to $A/C\times B/D$ by modding; the kernel is $C\times D$). Applying this inductively gives\[G\cong\prod_{k=1}^n\ZZ/d_k\ZZ.\]Do note that $d_\bullet=0$ is permitted, in which case $\ZZ/0\ZZ\cong\ZZ.$ This is what we wanted, so we are done. $\blacksquare$

I am told this generalizes nicely to general modules over PIDs. I can see where some of the generalization is possible, but the existence of the Smith normal form made heavy use of the division algorithm, which is nontrivially stronger than PID structure. I suspect there are ways to go around the division algorithm, however, by (for example) considering the ideal generated by all elements in a row or column and then extracting its generator.