22
$\begingroup$

Let $A_R$ be the finitely generated abelian group, determined by the relation-matrix

$$R := \begin{bmatrix} -6 & 111 & -36 & 6\\ 5 & -672 & 210 & 74\\ 0 & -255 & 81 & 24\\ -7 & 255 &-81 & -10 \end{bmatrix}$$

Reduce this matrix using Smith Normal Form and determine the isomorphism type of $A_R$.

I know that the Smith Normal Form of this matrix is:

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 21 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

However, this was computed using Maple and I need to understand the method of computing this manually which I am struggling to grasp. Can anyone help?

  • 0
    There's an algorithm on Wikipedia. http://en.wikipedia.org/wiki/Smith_normal_form2012-04-17
  • 5
    Your title mentions "groups rings and fields" but that does not seem to add anything useful to it.2012-04-17
  • 1
    I know how to calculate the smith normal form but how do you work out the isomorphisms?2012-04-23
  • 0
    Any chance you could please explain some steps then matt?? I know how to work out the isomorphisms. I have done the computation so many times now but I am just not ending up with the answer I have shown above. Thanks Euden2012-04-23

1 Answers 1

36

The computation requires two processes:

  • row operations of the type used in Gaussian elimination (with some restrictions because we require that the integer equivalence class be preserved) and the corresponding column operations,
  • the Euclidean algorithm for finding the greatest common divisor of two integers.

Specifically, you are allowed to

  1. interchange two rows or two columns,
  2. multiply a row or column by $\pm1$ (which are the invertible elements in $\mathbf{Z}$),
  3. add an integer multiple of row to another row (or an integer multiple of a column to another column).

The first goal is to reach diagonal form. Let's first work on column 1: using operation 3 for rows repeatedly, you can, by following the Euclidean algorithm, form a row whose first element is the GCD of the elements in column 1. You can then obtain a matrix with the GCD in the $(1,1)$ position and zeroes in the rest of column 1.

Now work on row 1: do the same thing, but using column operations; eventually you will have the GCD of row 1 in the $(1,1)$ position, and zeroes elsewhere in row 1. You will most likely have messed up column 1, but that's OK. Go back and redo column 1, then redo row 1, and repeat until all elements in row and column 1 are 0 except for the $(1,1)$ element. This process is guaranteed to terminate because the GCD gets smaller each time.

Now you can move on to row/column 2, and repeat the process. Continue for row/column 3, and so on, until you have reached diagonal form.

You may not be done at this point, because the diagonal elements may not satisfy the divisibility requirement of the Smith normal form. You can, however, enforce this by some additional moves as in the following example: $$ \begin{bmatrix}8 & 0\\0 & 12\end{bmatrix}\longrightarrow\begin{bmatrix}8 & 8\\0 & 12\end{bmatrix}\longrightarrow\begin{bmatrix}8 & 8\\-8 & 4\end{bmatrix}\longrightarrow\begin{bmatrix}24 & 8\\0 & 4\end{bmatrix}\longrightarrow\begin{bmatrix}24 & 0\\0 & 4\end{bmatrix}\longrightarrow\begin{bmatrix}4 & 0\\0 & 24\end{bmatrix}. $$ The idea is again to use the Eulidean algorithm. After adding column 1 to column 2, you may have to do several row operations to obtain the GCD of the two original diagonal elements. In the example above, only one row operation was needed for this.

Addendum: Details for the particular example in the OP's question. If you add row 2 to row 1, and then multiply row 1 by $-1$, you get a pivot of 1. You can then subtract suitable multiples of row 1 from rows 2 and 4, and end up with $$ \begin{bmatrix} 1 & 561 & -174 & -80 \\ 0 & -3477 & 1080 & 474 \\ 0 & -255 & 81 & 24 \\ 0 & -4182 & 1299 & 570 \end{bmatrix}, $$ which, by subtracting multiples of column 1 from columns 2, 3, and 4, leads to $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -3477 & 1080 & 474 \\ 0 & -255 & 81 & 24 \\ 0 & -4182 & 1299 & 570 \end{bmatrix}. $$ We next need to do a series of row operations involving rows 2, 3, and 4 that results in the GCD of 3477, 255, and 4182. If we always choose the pivot of smallest nonzero magnitude, the steps would be

  1. Subtract 14 times row 3 from row 2, and 17 times row 3 from row 4.
  2. Add 2 times row 2 to row 3, and subtract row 2 from row 4.
  3. Subtract row 4 from row 2, and add row 4 to row 3.
  4. Add 3 times row 3 to row 2, and 6 times row 3 to row 4.
  5. Add row 2 to row 3, and subtract row 2 from row 4.
  6. Add 2 times row 3 to row 2.
  7. Swap rows 2 and 3.
  8. Negate row 2.

You should now have $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 234 & -1410 \\ 0 & 0 & -651 & 3906 \\ 0 & 0 & -147 & 882 \end{bmatrix}. $$ You can now subtract suitable multiples of column 2 from columns 3 and 4. Then you just have to deal with the $2\times2$ block in the lower right. You should be able to get it from here.

  • 0
    Hey, thankyou for your comment. I have tried over and over using your method but whatever happens I just don't seem to be able to get the answer I found on maple.. Could you show some steps so I can compare with what I have done and find where I am going wrong please. Thanks, Euden.2012-04-23
  • 0
    Thankyou so much, I just completed it, so relieved. :)2012-04-25
  • 0
    how did you complete it? any help would be really helpful right now:)2012-05-04
  • 0
    How far did you get? At what point are you stuck?2012-05-05
  • 0
    You say that if one wants to compute the smith normal form of a matrix at a certain point he has to put the GCD of the column i on the position (i,i). Today at scool my assistant (not my professor) said that we have to put in the position (i,i) the GCD of the column AND the line i on the position (i,i) which one of the senteces is correct?2014-02-26
  • 0
    @Ale: I'm certain that the procedure I described works. Your assistant's procedure may also work, and may even be equivalent. I'd have to see a detailed description of the algorithm to say for sure.2014-02-26
  • 0
    @Ale: notice that my procedure puts the GCD of column 1 in the (1,1) position, then puts the GCD of row 1 in the (1,1) position, and then repeats the whole procedure, continuing until all elements in row and column 1 are 0 except for the (1,1) element. To work on column 1, you use row operations; to work on row 1, you use column operations. This means that when working on column 1, row 1 will change. Therefore I am not sure how the GCD of row and column 1 is defined. Assuming you mean the GCD of row and column 1 in their initial state,...2014-02-26
  • 0
    ...how do you avoid bringing elements from other rows and columns into play?2014-02-26
  • 0
    @Ale: to illustrate what I mean, consider the matrix $$\begin{bmatrix}6 & 4\\ 8 & 3\end{bmatrix}.$$ The GCD of row and column $1$ is $2.$ I can put $2$ in the $(1,1)$ position by subtracting row $1$ from row $2$, and then swapping rows $1$ and $2.$ I get $$\begin{bmatrix}2 & -1\\ 6 & 4\end{bmatrix}.$$ The GCD of row and column $1$ is now $1,$ not $2.$ According to your assistant's method, what number is supposed to go in the $(1,1)$ position, $2$ or $1?$2014-02-26
  • 0
    According to my assistant the number 1. I also tried to compute the smith normal form of some matrices with both methods. E.g. the smith normal form of the matrix \begin{bmatrix} 1 & 0 & 0 & 0 \\ 8& 12 & -4 & -6 \\ -5& -8 & 4 & 4 \end{bmatrix} with your method will be (according to my calculation):\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 4 & 0 \end{bmatrix} and with the method of my assistant (always according to my calculation): \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 4 & 0 \end{bmatrix}2014-02-27
  • 0
    (sorry double post due to the length) It can be that both methods are right, because the characteristics of the smith normal form $(a_i | a_{i+1}) \forall i$ is in both cases satisfied. what would you say?2014-02-27
  • 0
    @Ale: the Smith Normal Form is unique, so both cannot be right. I'm not seeing how you get the $4$ in the $(2,2)$ position using my method. Can you explain? Also: the fact that your assistant's method says to put $1$ in the $(1,1)$ position in my previous example suggests to me that the two methods are the same.2014-02-27
  • 0
    Shure with your method this is our matrix: \begin{bmatrix} 1 & 0 & 0& 0\\ 8 & 12&-4 &-6 \\ -5 & -8 & 4 & 4\end{bmatrix} We are lucky because on the first line we have already zeros. We search for the GCD of the column 1 and we see that this is $1$. We now subtract 8 times the first line to the second and we add 5 times the first line to the second one (I also repeat those operations on the left identity matrix) and I get \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 12 & -4 & -6 \\ 0 & -8 & 4 & 4 \end{bmatrix}2014-02-27
  • 0
    Now we see that the GCD of the column 1 is 4 and we get it in the position $(2,2)$ by subtracting the third line to the second one. We get \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 4 & 0& -2 \\ 0 & -8 & 4 & 4 \end{bmatrix} We now want the element $(2,4)$ to be $0$. We get this by adding the second column to two times the fourth one \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 4 & 0 & 0\\ 0 & -8 & 4 & 0 \end{bmatrix} Now we want the element $(3,2)$ to be 0 and we get it by adding two times the second line to the third one. Result: \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 4 & 0 & 0\\ 0 & 0 & 4 & 0 \end{bmatrix}2014-02-27
  • 0
    With the method of my assistant the only thing that changes is the GCD that goes in element $(2,2)$, which is $2$ because the GCD of (12,-8,-4,-6) is two. We get two in $(2,2)$ from this matrix \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 12 & -4 & -6 \\ 0 & -8 & 4 & 4 \end{bmatrix} by adding to the second column the third column and the fourth column and we get: \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 2 & -4 & -6 \\ 0 & 0 & 4 & 4 \end{bmatrix}2014-02-27
  • 0
    Now we want the elements $(2,3)$ and $(2,4)$ to be 0 and we get them by adding two times the second column to the third one and three times the second column to the fourth one \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 2 & 0 & 0 \\ 0 & 0 & 4 & 4 \end{bmatrix} $\to$ \begin{bmatrix} 1 &0 & 0& 0\\ 0 & 2 & 0 & 0 \\ 0 & 0 & 4 & 0 \end{bmatrix}2014-02-27
  • 0
    @Ale: the error is in the step where you make the $(2,4)$ element $0$ by adding column $2$ to $2$ times column $4.$ This is not a legal move: you are permitted to add an integer multiple of one column to another, but you are not allowed to add one column to an integer multiple of another. Otherwise stated, you may multiply a column by $\pm1,$ but not by any other number. Your operation amounts to multiplying column $4$ by $2$ and then adding column $2$ to it.2014-02-27
  • 0
    Make sure you are following my prescription precisely. "Now work on row 1: do the same thing, but using column operations; eventually you will have the GCD of row 1 in the $(1,1)$ position, and zeroes elsewhere in row 1." In your context this needs to be applied to row 2 rather than row 1.2014-02-27
  • 0
    The point of my post is that, in sufficiently complicated situations, it won't be possible to clear a row/column pair by doing a single set of row operations followed by a single set of column operations. You may have to switch back and forth between row and column operations many times before both the row and the column are cleared. The number that will end up in the diagonal position after this operation cannot be described simply as the the GCD of a particular column or row/column pair. That number is the end result of the process, and may depend on other rows/columns.2014-02-27
  • 0
    Ok, than I should have changed column four with column 2 in such a way that I would have get $-2$ in the element $(2,2)$ and after that everything works. Thank you very much!2014-02-27