Classifying finitely generated abelian groups

First, we need a result rectifying the theorem that a subgroup of a f.g. free abelian group is free.
In a way, it is a generalisation of a well-known property of a subspace U of a vectorspace V: we can change the basis of V to, say, e_1,\dots,e_n so that U will be generated by e_1,\dots,e_{\dim U}. As we cannot, generally speaking, invert our integer coefficients in the case of abelian groups, the e_j‘s will get extra multipliers. More precisely, the following, known as Smith Normal Form Theorem for abelian groups, holds.

Let H\leq B be a subgroup of a f.g. free abelian group B. Then in B there exists a free generating set e_1,\dots,e_n such that H is freely generated by u_1 e_1,\dots,u_m e_m, with m\leq n, positive integers u_1,\dots u_m, and u_i dividing u_{i+1} for i=1,\dots,m-1.

We know that H is free of rk(H)=m\leq n. So H is freely generated by h=(h_1,\dots,h_m), and there is an integer m\times n matrix Q such that Qs=h, where s=(s_1,\dots,s_n) are free generators for B. We apply to Q the Smith Normal Form algorithm (in this reference one can ignore the PID etc bits, just assuming that matrix entries are integers), something akin to Gauss elimination, although without division.

More precisely, given a free abelian group and an (ordered) basis for it, we are allowed to (check this!)

  1. multiply basis elements by -1;
  2. swap two basis elements;
  3. add to a basis element another one, multiplied by an integer

without “breaking” the basis property (the resulting set of elements will remain a basis for the group.)
These are the operations we will perform on h and on s. Respectively, they affect, in the way just described, rows and columns of Q. Thus, after applying Smith Normal Form algorithm to Q, we obtain a diagonal matrix Q'=diag(u_1,\dots,u_m) and bases h' and s' of H and B, respectively, so that (Q'|\overline{0})s'=h'. (We denoted here by \overline{0} the all-0 matrix of size m\times (n-m).) This completes the proof.

Our work will bear fruit here. We will prove the following Classification theorem for finitely generated abelian groups. One more piece of notation: B^k=B\oplus\dots\oplus B, with k direct summands on the right-hand side.

Let A be an abelian group generated by s_1,\dots,s_n. Then A\cong \mathbb{Z}_{n_1}\oplus\dots\oplus\mathbb{Z}_{n_t}\oplus\mathbb{Z}^{n-t}. Moreover, n_i|n_{i+1}, for 1\leq i\leq t-1, and n_1,\dots,n_p, for some p\geq 0, are allowed to be 1.

Consider the homomorphism \phi:\mathbb{Z}^n\to A given by (k_1,\dots,k_n)\mapsto \sum_{j=1}^n k_j s_j. By the 1st Isomorphism Theorem one has A\cong \mathbb{Z}^n/Ker(\phi). Changing, if necessary, the generating set in \mathbb{Z}^n, we can assume by Smith Normal Form Theorem that Ker(\phi) is freely generated by u_1 e_1,\dots,u_m e_m, with m\leq n and e_1,\dots, e_n freely generating \mathbb{Z}^n.

Now consider the homomorphism \psi:\mathbb{Z}^n\to \mathbb{Z}_{u_1}\oplus\dots\oplus\mathbb{Z}_{u_m}\oplus\mathbb{Z}^{n-m} given by \sum_{j=1}^n \ell_j e_j\mapsto (\ell_1\mod u_1,\dots,\ell_{m}\mod u_m,\ell_{m+1},\dots,\ell_n). It can happen that u_1=\dots = u_p=1, then the corresponding first p direct summands must be dropped – they correspond to trivial subgroups. Then Ker(\psi)=Ker(\phi), and so A\cong \mathbb{Z}^n/Ker(\psi)= \mathbb{Z}_{u_{p+1}}\oplus\dots\oplus\mathbb{Z}_{u_m}\oplus\mathbb{Z}^{n-m}. This completes the proof (we will have t=m-p).

As a 1st example, consider an abelian group B=\langle t_1,t_2\rangle, where the generators satisfy just one irredundant relation 2t_1+4t_2=0. The latter just means that the kernel of the homomorphism \phi:\mathbb{Z}^2\to B is Ker(\phi)=\langle  2t_1+4t_2\rangle. Then, according to the procedure outlined in the proof, we are to compute the Smith normal form of the matrix \begin{pmatrix}2& 4\end{pmatrix}. Applying the column operation of adding the -2 times the 1st column to the 2nd column, we obtain the normal form Q'=\begin{pmatrix}2& 0\end{pmatrix}. Thus we see that B\cong \mathbb{Z}_2\oplus\mathbb{Z}.
It is instructive to see what happens to the basis x=(x_1,x_2) of \mathbb{Z}^2 and to the relation r^T x=2x_1+4x_2\in Ker(\phi) as this basis change is carried out. Note that the column operation we used is given by the matrix C=\begin{pmatrix}1&-2\\ 0&1 \end{pmatrix}. (To see this, perform this operation on the matrix \begin{pmatrix} 2&4\\ 1&0\\ 0&1 \end{pmatrix}, and read off C from the 2nd and 3rd rows of the result.) So the new basis is equal to (x'_1,x'_2)=C^{-1}x=(x_1+2x_2,x_2), and r^T x=r^T CC^{-1}x\in Ker(\phi). The new relation will be written as (r^T C)x'=2x'_1, so in the new basis Ker(\phi)=\langle 2x'_1\rangle.

As an exercise, do the corresponding computation with 5 in the place of 4 in the definition of B. Note that you will need more than one column transformation in this case!

While Smith Normal Form for a given group A is unique, often (e.g. for purposes of ring theory) we are more interested in decomposing A into a direct sum of as many cyclic subgroups as possible.
We can do a bit more work to arrive at a direct sum decomposition that is, in fact, unique in the latter sense, up to permuting summands. Here we just note that the number n-t, that counts \mathbb{Z}-summands, does not depend upon a particular decomposition. To see that, we introduce the notion of torsion subgroup Tor(A) of A.

Tor(A)=\{a\in A\mid ma=0\text{ for some } m\in\mathbb{Z}\}.

More exercises

  1. Let A=\langle x,y,z\rangle be an abelian group generated by x,y,z that satisfy the relations 0=2x=2y=2z=3x+3y=5y+5z. Determine A using the Theorem above and the Smith normal form computation.
  2. Let A=\mathbb{Z}_n\oplus\mathbb{Z}_m, and GCD(m,n)=1, i.e. m and n relatively prime. Use the Theorem above and the Smith normal form computation to show that A\cong\mathbb{Z}_{nm}. (As usual, GCD=Greatest Common Divisor.)
  3. More generally, show, using the method from the previos problem, that =\mathbb{Z}_n\oplus\mathbb{Z}_m\cong \mathbb{Z}_g\oplus\mathbb{Z}_{mn/g}, where g=GCD(m,n).
  4. Show that and n\times n integer matrix X satisfying |\det X|=1 can be transformed into the identity matrix by the elementary row operations. What about elementary column operations?
  5. Find the n\times n matrices C such that for an n\times m matrix Q the elementary row operations on Q can be described as computing the products CQ. That is,
    1. C=C(i) that corresponds to the multiplication of the i-th row by -1;
    2. C=C(i,j) that corresponds to swapping of the i-th and the j-th rows;
    3. C=C(i,j,\alpha) that corresponds to adding to the i-th row the j-th row multiplied by \alpha;
  6. Show that the operation of swapping the rows in the Smith normal form computation is redundant, i.e. the same can be accomplished using the other two operations only.
  7. Let Q be an n\times m integer matrix and U its Smith normal form. Investigate what happens if we consider the (n+m)\times (n+m) “block” matrix \begin{pmatrix}Q & I_n \\ I_m & 0 \end{pmatrix} and apply the row operations on the topmost n rows and the column operations on the leftmost m columns to obtain a matrix \begin{pmatrix}U & A \\ B & 0 \end{pmatrix}.
    Find out how to use the matrix product of A, B,Q to obtain U.
  8. Investigate how A and B from the previous problem change the generating sets of the corresponding free abelian groups;
  9. check that Tor(A)\leq A.
    (As the definition of Tor(A) does not depend on a particular decomposition as in the theorem, and A/Tor(A)\cong Z^{n-t}, we see that n-t is invariant, as claimed.)

Tags: , ,

6 Responses to “Classifying finitely generated abelian groups”

  1. paradox Says:

    maybe you can teach us more about how each elementary operation on Q change the basis for B and H?

  2. paradox Says:

    Is the Smith Normal Form unique? From your last paragraph before exercises, it seems that it is not unique.

  3. Dima Says:

    The Smith Normal Form (SNF) is unique (can’t you prove it?), but sometimes hides the important information about the cyclic structure of the group, i.e. SNF for \mathbb{Z}_{15} is \mathbb{Z}_{15} rather than \mathbb{Z}_{3}\oplus\mathbb{Z}_{5}. I’ll fix the text to explain more on what I wanted to say here.

  4. math Says:

    Hi, this is a very nice tutorial. Thank you very much. Can you give an referece for this?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: