[Math] Reduce matrix to Smith Normal form.

linear algebramatricesmatrix decompositionsmith-normal-form

I've been given the finitely generated abelian group: $$\langle x_1, x_2 \mid 6x_1-6x_2, -6x_1-12x_2, 4x_1-8x_2\rangle$$ and written the corresponding matrix: $$A=\begin{pmatrix}
6 & -6 \\ -6 & -12 \\ 4 & -8 \end{pmatrix}$$ I now need to reduce this to Smith Normal form using the unimodular elementary row and column operations.

I keep running into difficulties that are usually because I'm not allowed to multiply rows or columns by fractions. How do I do it?

Best Answer

You want to find row/column operation for which your initial matrix looks like this

\begin{equation*} \begin{pmatrix}a_1 & 0 \\0&a_2 \\0&0 \end{pmatrix}\end{equation*}

and $a_1\mid a_2$. According to Wikipedia this numbers are unique up to multiplication by a unit, and they can be found by using the formula $a_i =\frac{d_i(A)}{d_{i-1}(A)}$, where $d_i(A)$ is the greatest common divisor of all $i\times i$ minor of you matrix.

Moreover according to this thread you are only 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).

Let us compute $a_1$. As you can see the greatest common divisor of all $1\times 1$ minor of your matrix is $2$, so we will have $a_1 =2$ once the algorithm is over.

To find $a_2$ you need to compute all the $2\times 2$ minor of your matrix, and you should get $d_2(A)= GCD(-24,108,96)=12$, so $a_2 = \frac{12}{2}=6$.

Now we should find operations that respects 1.,2.,3. such that the final matrix is

$$\begin{pmatrix}2&0\\0&6\\0&0\end{pmatrix}$$

This is done in the following way (I can try it by yourself, and you should get the same solution also with other operations, because $a_1,a_2$ are unique up to multiplication by unit):

\begin{align*} \begin{pmatrix} 6&-6 \\-6&-12\\4&-8\end{pmatrix} &\overset{Ir-IIIr; \, IIr + IIIr}{\leadsto} \begin{pmatrix} 2&2\\-2&-20\\4&-8\end{pmatrix} \\ \overset{IIc-Ic}{\leadsto}\begin{pmatrix}2&0\\-2&-18\\4&-12\end{pmatrix} &\overset{IIr+Ir;\, IIIr-2Ir}{\leadsto} \begin{pmatrix}2&0\\0&-18\\0&-12\end{pmatrix} \\ \overset{IIr-IIIr}{\leadsto}\begin{pmatrix} 2&0\\0&-6\\0&-12\end{pmatrix}&\overset{IIIr-2IIr}{\leadsto}\begin{pmatrix}2&0\\0&-6\\0&0\end{pmatrix} \end{align*}

Now you can mulitply by $-1$ the second row.

Related Question