With reference to this question, it was mentioned in the comments that these problems could be solved using the Smith Normal Form. However, I am unable to extract an exact method from the Wikipedia article alone, and further searching yields few general examples. I am asking for an example where the algorithm is used to classify a factor group.


OK, here is an example. Find the structure of the group $${\mathbb Z}^3/\langle (6,6,4),\,(6,12,8) \rangle.$$ Write down the matrix:

$$\left( \begin{array}{rrr} 6&6&4\\6&12&8 \end{array}\right)$$

There are many different ways to reduce this to SNF. Here is one way (hoping I haven't miscalculated):

Subtract Column 3 from Column 2
Interchange Columns 1 and 2
Subtract 2 times Row 1 from Row 2
Subtract 3 times Column 1 from Column 2    
Subtract 2 times Column 1 from Column 3
Negate Row 2

giving SNF:

$$\left( \begin{array}{rrr} 2&0&0\\0&6&0 \end{array}\right)$$

It is important to remember that the number of cyclic factors should be equal to the number of generators of the original group (although, in general, some of these factors could have order $1$ and hence be trivial). So if there are fewer subgroup generators than group generators, we have to adjoin copies of ${\mathbb Z}$. So, in this example, the group is isomorphic to

$${\mathbb Z}_2 \oplus {\mathbb Z}_6 \oplus {\mathbb Z}$$

  • $\begingroup$ Thank you, although with this task, I can't do much but to take your word for it. Working with, for example, $(\mathbb{Z} \times \mathbb{Z})/\langle (2, 2) \rangle$ we have the matrix $(2\:\:\:2)$ and we reduce that to $(2\:\:\:0)$ to get $\mathbb{Z}_2 \times \mathbb{Z}$? $\endgroup$ – Andrew Thompson Mar 22 '14 at 11:58
  • $\begingroup$ Yes, that's right $(2\ 2) \to (2\ 0)$ giving ${\mathbb Z}_2 \times {\mathbb Z}$. I know I haven't explained the thoery, but sea turtles has done this in a more general context. In fact row operations on the matrix represent changes to the generating set of the subgroup, whereas column operations are changes to the generating set of ${\mathbb Z}^n$. Neither of these changes affects the isomorphism type of the quotient group, which is why the process works. $\endgroup$ – Derek Holt Mar 22 '14 at 13:21

Below I explain how Smith Normal Form relates to the fundamental theorem and how it can be used to classify a given finitely generated module over a PID in terms of a presentation. It has been awhile since I've actually computed a SNF, so I can't show you an example of that without basically relearning how its done (I'll leave that for someone else); rather, I just utilize the existence of SNF and could (for instance) have a computer find one in order to classify a module.

If you don't know what the words "module" and "PID" mean, then I am speaking in slightly too much generality for a given reader $-$ there is a simple fix for this: simply read "module" as "abelian group" and assume the PID (a type of ring) $R$ is the usual set of integers $R=\Bbb Z$.

Let $R$ be a PID and suppose we have a finitely-generated $R$-module $M$ given by

$$M=\left\langle m_1,\cdots,m_n\left| \begin{array}{c} a_{11}m_1+\cdots+a_{1n}m_n \\ \vdots \\ a_{k1}m_1+\cdots+a_{kn}m_n \end{array}\right.\right\rangle \quad (^\dagger k\le n)$$

There is the "universal" $R$-module homomorphism $R^n\to M:(r_1,\cdots,r_n)\mapsto r_1m_1+\cdots+r_nm_n$, and since this is onto, by the first isomorphism theorem for modules we have the isomorphism

$$M\cong R^n/\langle (a_{11},\cdots,a_{1n}),\cdots,(a_{k1},\cdots,a_{kn})\rangle. $$

The denominator above is precisely the image of the matrix transformation $R^n\to R^n$ given by

$$A=\begin{pmatrix}a_{11} & \cdots & a_{k1} & \cdots \\ \vdots & \ddots & \vdots & \vdots \\ a_{1n} & \cdots & a_{kn} & \cdots \end{pmatrix}$$

The right-hand columns are zeroed out in order to make the matrix square. The SNF of $A$ looks like

$$A=SBT, \qquad B=\begin{pmatrix}b_1 & 0 & 0 & 0 & \cdots \\ 0 & \ddots & 0 & 0 & \cdots \\ 0 & \cdots & b_\ell & 0 & \cdots \\ 0 & \cdots & 0 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}, \qquad S,T\in{\rm GL}_n(R).$$

The diagonal entries of $B$ are $b_1,\cdots,b_\ell$ (where $\ell\le n$) and all else zeroed out. Therefore,

$$M\cong\frac{R^n}{AR^n} = \frac{SR^n}{SBTR^n}\cong\frac{R^n}{BTR^n}=\frac{R^n}{BR^n}\cong\frac{R}{b_1R}\times\cdots\times\frac{R}{b_\ell R}\times \underbrace{\frac{R}{0}\times\cdots\times\frac{R}{0}}_{n-\ell}.$$

Thus is established the fundamental theorem of finitely-generated modules over principal ideal domains: all such modules are a finite direct sum of quotients of the scalar ring. Indeed, given the presentation of a module, one computes the SNF of the matrix of coefficients of the relations on the generators, and then reads off from the SNF's diagonals the denominators of these aforementioned quotients.

${}^\dagger$ Any submodule of $R^n$ will be finitely generated by $\le n$ elements, so $k\le n$ w.l.o.g.

  • $\begingroup$ We will work with PID's in a couple of weeks, and I believe this answer will be fruitful for me in the future. $\endgroup$ – Andrew Thompson Mar 21 '14 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.