Reducing a matrix to Smith normal form I am trying to reduce the following matrix to Smith normal form 
$$A= \begin{pmatrix}
1&0&0\\
1&2&0\\
1&0&3
\end{pmatrix}$$
Whatever row and column operations I try, I end up with the diagonal matrix 
$$A= \begin{pmatrix}
1&0&0\\
0&2&0\\
0&0&3
\end{pmatrix}$$
However for Smith normal form I need diagonal entries $a_i$ such that $a_j|a_{j+1}$. But $2$ does  not divide $3$ here. How do I rectify this? 
 A: Newman says that Smith form can be accomplished with elementary row and column operations as long as the coefficient ring is Euclidean, as here. Since we are not going to change the determinant, this means diagonal $(1,1,6).$ Newman's assurance means that we can accomplish this for the two by two square with entries $(2,3).$
Take distinct positive integers $p,q$ such that $\gcd(p,q) = 1$ and
$$ px + qy = 1. $$ Then the sequence of resulting matrices is
$$
\left(
\begin{array}{rr}
p & 0 \\
0 & q
\end{array}
\right),
$$
$$
\left(
\begin{array}{rr}
p & 0 \\
px & q
\end{array}
\right),
$$
$$
\left(
\begin{array}{rr}
p & 0 \\
1 & q
\end{array}
\right),
$$
$$
\left(
\begin{array}{rr}
1 & (1-p)q \\
1 & q
\end{array}
\right) =
\left(
\begin{array}{rr}
1 & q-pq \\
1 & q
\end{array}
\right)
$$
$$
\left(
\begin{array}{rr}
1 & 0 \\
1 & pq
\end{array}
\right)
$$
$$
\left(
\begin{array}{rr}
1 & 0 \\
0 & pq
\end{array}
\right)
$$
A: Here's the way I determine the Smith normal form. 


*

*First find the gcd of all entries of the matrix - its easy to see this is 1. So $f_1(x) = d_1(A)/d_0(A) = 1/1 = 1$

*Now you need to find the gcd of determinants of ALL $2 \times 2$ submatrices. There are 7 such submatrices. The determinant of the upper left matrix is 2. The determinant of the upper right matrix is 0. The determinant of the lower left matrix is -2. The determinant of the lower right matrix is 6.  Now consider submatrices obtained by removing the middle column. The first is obtained by removing the bottom row, and its determinant is 0. The second by removing the middle row, its determinant is 3. The last by removing the top row, its determinant is also 3. So here we see that the gcd is again 1. Now $f_2(x) = d_2(A)/d_1(A) = 1/1 = 1$. 

*Lastly, the only $3 \times 3$ submatrix is the matrix itself, and it has determinant 6. So  $f_3(x) = d_3(A)/d_2(A) = 6/1 = 6$. 


So we have Smith normal form $\text{Dg}[1,1,6]$. I have elaborated step number 2, as it is a common error not to consider ALL the relevant minors. This step can be considerably shortened with a smarter heuristic type of search, in this case I would follow a "hunch" that most probably I can find determinants 2, 3 which are relatively prime. Its easy to find the submatrix with determinant 2, and then if I start by deleting the middle column I can quickly find the submatrix with determinant 3. Once I have these two I know the gcd is 1, so no further calculation is required. 
