Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is related to the Smith Normal Form of Matrices:

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 ad 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?

share|improve this question
    
Why the low accept rate? –  Brett Frankel Apr 17 '12 at 20:10
    
There's an algorithm on Wikipedia. en.wikipedia.org/wiki/Smith_normal_form –  Brett Frankel Apr 17 '12 at 20:12
4  
Your title mentions "groups rings and fields" but that does not seem to add anything useful to it. –  Mariano Suárez-Alvarez Apr 17 '12 at 20:34
    
I know how to calculate the smith normal form but how do you work out the isomorphisms? –  user29784 Apr 23 '12 at 17:49
    
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 Euden –  Euden Apr 23 '12 at 19:56

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
    
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. –  Euden Apr 23 '12 at 19:55
    
Thankyou so much, I just completed it, so relieved. :) –  Euden Apr 25 '12 at 12:36
    
how did you complete it? any help would be really helpful right now:) –  user30660 May 4 '12 at 21:22
    
How far did you get? At what point are you stuck? –  Will Orrick May 5 '12 at 11:52
    
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? –  Ale Feb 26 at 16:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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