# Finding the correct pivot in Smith 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?

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}

• Thanks for your help I was confused about the wikipidea example for the two matrices $$A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}, B = \begin{pmatrix} 3 & -4 \\ 1 & -1 \end{pmatrix}$$ I was just tyring to compute the Smith normal form of $(xI -A)$ and $(xI-B)$ and I was able to arrive at the same answer they have for $B$ i.e. $SNF(xI-B) = \begin{pmatrix}1&0 \\0 &(x-1)^2 \end{pmatrix}$ but I could not find a valid pivot for $(xI-A)$ – user7980 Jul 28 '11 at 15:29
• In particular if we look at the matrix $(xI-A) = \begin{pmatrix} x-1 & 2 \\0 &x-1 \end{pmatrix}$ how do I get a 1 in the top 1-1 position of the matrix? I am assuming they are working in the field on integers is this wrong? – user7980 Jul 28 '11 at 15:35
• The operations I keep trying are something like $\begin{pmatrix} x-1 & 2 \\0 &x-1 \end{pmatrix} \sim \begin{pmatrix} x-1 & x+1 \\0 &x-1 \end{pmatrix} \sim \begin{pmatrix} -2 & x-1 \\x-1 &x-1 \end{pmatrix}$ – user7980 Jul 28 '11 at 15:38
• The integers are not a field since integers don't generally have multiplicative inverses within the integers; therefore since the Wikipedia example is concerned with equivalence of matrices over a field, it can't be the integers they're working over. They don't actually specify the field, but either the rationals or the reals would be fine for this example. Once you've realized that rational numbers are allowed, you can multiple row 1 by 1/2 to get your pivot. – Will Orrick Jul 28 '11 at 16:46
• The SNF is useful when working over a principal ideal domain, which is a type of ring. In this case, the ring is the ring of polynomials with coefficients in a field - perhaps the field of rational numbers. In this ring, nonzero numbers such as 2 are invertible. Expressions like $x$ or $x^2+1$, on the other hand, do not have multiplicative inverses within the ring. This means that in computing the SNF, you can multiply by a row by a nonzero rational number, but not by a polynomial. – Will Orrick Jul 28 '11 at 16:51

To answer your Question 1: We don't divide by $2$ or any other non-unit in $\mathbb{Z}$ because division by $2$ is not a $\mathbb{Z}$-map from $\mathbb{Z}$ to itself. In fact, we are not permitted to multiply by a non-unit as well, because multiplication by $m$ is not an invertible $\mathbb{Z}$-map unless $m = \pm 1$.

Your SNF computation seems fine, and you get the correct invariant factors.

• The only operations available to reduce a matrix to SNF over a ring $R$ are: 1. Multiply a row/col by a unit of $R$. 2. Exchange two rows/cols. 3. Add $r \cdot Row_i$ to any $Row_j$ for $i \neq j$ and arbitrary $r \in R$ (and analogous for columns). – Shaun Ault Jul 27 '11 at 20:36