[Math] Finding the correct pivot in Smith normal form

abstract-algebralinear algebrasmith-normal-form

I have been working through Smith normal form examples and I am wondering if I am finding the correct pivot in order to carry out the calculation.

Let $V \subset \mathbb{Z}$ be an Abelian group with relation matrix $A$.

$$
A = \begin{pmatrix}
2 & -6 & 0 \\
0 & 2 & -6 \\
-6 & 0 & 2 \end{pmatrix}
$$

Question 1: For the case of entries in $\mathbb{Z}$, is the first step always to bring smallest integer to 1-1 position in the matrix? So we don't divide by 2 in this case right?

(I was trying to do something similar to the matrix A in the Wikipedia article but I have no idea how to make the first pivot 1 and still get $SNF(xI-A) = \begin{pmatrix}1&0 \\0 &(x-1)^2 \end{pmatrix}$

Applying my logic this is what I get for the Smith normal form (SNF) of the original problem

$$\begin{pmatrix}
2 & -6 & 0 \\
0 & 2 & -6 \\
-6 & 0 & 2 \end{pmatrix} \sim \begin{pmatrix}
2 & -6 & 0 \\
0 & 2 & -6 \\
0 & -18 & 2 \end{pmatrix} \sim \begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & -6 \\
0 & -18 & 2 \end{pmatrix} \sim \begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & -6 \\
0 & 0 & 52 \end{pmatrix} \sim \begin{pmatrix}
2 & 0 & 0 \\
0 & 2 & 0 \\
0 & 0 & 52 \end{pmatrix}$$

Question 2: Is $V = \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z}/2\mathbb{Z} \oplus \mathbb{Z} / 52\mathbb{Z}$ based on the above Smith normal form?

Best Answer

In Wikipedia's example of SNF$(xI-A)$, the purpose is to determine whether two matrices over a field are similar by computing the Smith normal forms of their characteristic matrices. The field might, for example, be the rational numbers. In that case, the elements of the characteristic matrix live in the ring of polynomials with rational coefficients. The units in this ring, i.e. the elements that have inverses, are the nonzero rational numbers. So in this case you are allowed to multiply rows or columns by nonzero rational numbers. You just can't multiply rows or columns by polynomials of nonzero degree, since they don't have inverses in the ring. But you would be allowed, for example, to multiply row 1 of the matrix by $1/2$. Then, by adding a suitable multiple of column 2 to column 1, and a suitable multiple of row 1 to row 2, you can obtain the result Wikipedia gives, up to permutation.

In general, the operations you are allowed to do are

  1. Permute rows.
  2. Multiply a row by a unit (invertible element) of the ring. (In the ring of integers this means only $\pm1$, but in a ring of polynomials over a field, it could be any nonzero field element.)
  3. Add a multiple of an row to another row.
  4. Do any of the corresponding column operations.

Note that you cannot always clear the first row and column in a single pass. In a Euclidean domain, you can, by suitable row operations, bring the GCD of the first column into the (1,1) position and clear the remainder of the column. Then by suitable column operations, you can bring the GCD of the first row into the (1,1) position and clear the remainder of the row. But at that point the first column may no longer be cleared, so you may have to repeat the process. It is guaranteed that, in finitely many steps, you will end up with both the first row and column cleared. (Think about why.) By an iterative process, you eventually reach diagonal form. The diagonal elements may not satisfy the divisibility requirements of the SNF, however. That can always be fixed by suitable operations involving pairs of diagonal elements. For example, $$ \begin{aligned} \begin{bmatrix} 18 & 0\\0 & 30 \end{bmatrix}&\sim \begin{bmatrix} 18 & 18\\0 & 30 \end{bmatrix}\sim \begin{bmatrix} 18 & 18\\-18 & 12 \end{bmatrix}\sim \begin{bmatrix} 36 & 18\\-6 & 12 \end{bmatrix}\sim \begin{bmatrix} 0 & 90\\-6 & 12 \end{bmatrix}\sim \begin{bmatrix} 0 & 90\\-6 & 0 \end{bmatrix}\\ &\sim\begin{bmatrix} -6 & 0\\0 & 90 \end{bmatrix} \sim\begin{bmatrix} 6 & 0\\0 & 90 \end{bmatrix} \end{aligned} $$

Related Question