What does this step in the following matrix algorithm mean?

I am trying for hours to calculate in every step the Smith Normal form of this matrix but without success: $$\left(\begin{array}{rrr} 6 & 18 & 15 \\ 12 & 8 & 9 \\ 10 & 6 & 8 \end{array}\right)$$

I am following step by step the instructions in Wikipedia: https://en.wikipedia.org/wiki/Smith_normal_form and in the Step 2 it says to fit the matrix $L_0$ to the identity Matrix and then do left multiplication.

Can someone explain to me what it means to "fit" a $2\times2$ Matrix in the $t$-th and $k$-th row to the $3\times3$ identity matrix in order to do this left multiplication?

Thanks

Solution 1:

That statement is to be more explicit about the particular step in the Gaussian elimination. In general, if we have a $2\times 2$ invertible matrix $\begin{pmatrix} a& b\\c& d\end{pmatrix}$, we can think of it as an $n\times n$ invertible matrix for any integer $n\geq3$ by the "fitting" procedure (I am not claiming that this fitting procedure is the only way of thinking of $2\times 2$ matrices as matrices of higher dimension). E.g. in the case of $n=3$, we can think of $A=\begin{pmatrix} a& b\\c& d\end{pmatrix}$ as

$$\iota_{1,2}(A)=\begin{pmatrix} a& b&0\\c& d&0\\0&0&1\end{pmatrix} \quad\text{ or }\quad\iota_{2,3}(A)=\begin{pmatrix} 1&0&0\\0&a& b\\0&c& d\end{pmatrix}\quad \text{ or }\quad \iota_{1,3}(A)=\begin{pmatrix} a&0& b\\0&1&0\\c&0& d\end{pmatrix}.$$

Here the subscripts are supposed to signify which two rows are affected by the original $2\times 2$ matrix $A$ when the associated higher dimensional version is multiplied with another matrix. So in the case of $n=3$, if $B$ is another anonymous $3\times 3$ matrix, we have that the third rows of $\iota_{1,2}(A)B$ and $B$ are identical, the first rows of $\iota_{2,3}(A)B$ and $B$ are identical, and the second rows of $\iota_{1,3}(A)B$ and $B$ are identical. (Analogously $B\iota_{\bullet,\bullet}(A)$ and $B$ would have all but two columns identical; I'm leaving the verification of these to you.)

Now let us see how these fitted matrices come into play in finding the Smith normal form of the matrix $B=\begin{pmatrix} 6 & 18 & 15 \\ 12 & 8 & 9 \\ 10 & 6 & 8 \end{pmatrix}$ in question. I'll start the algorithm discussed on Wikipedia (but won't finish it; according to http://www.numbertheory.org/php/smith.html (with the entry "6 18 15 12 8 9 10 6 8") the Smith normal form ought to be $\begin{pmatrix} 1&0&0\\0&2&0\\0&0&84\end{pmatrix}$).

First, $t$ runs $1\to2\to3$.

Step I ($t=1$): The first column has nonzero entries, so that $j_1=1$, so we focus on the first column. We want $a_{1,1}\neq0$, which is the case; so onwards.

Step II ($t=1$): $12=a_{2,1}$ is a multiple of $6=a_{1,1}$, so we won't touch it (which indicates that we will be using an $\iota_{1,3}$ in this step), however $10=a_{3,1}$ is not a multiple of $6=a_{1,1}$, so that $k=3$ (all multiples, divisors etc. are within the integer system). The greatest common divisor of $6$ and $10$ is $2$. We need a solution to the Bézout equation $6\sigma+10\tau=2$ (this equation is always solvable). A solution is $\sigma=2,\tau=-1$. Putting $\alpha=6/2$ and $\gamma=10/2$, the Bézout equation becomes $\alpha\sigma+\gamma\tau=1$, which is to say $A=\begin{pmatrix} \sigma& \tau\\ -\gamma& \alpha\end{pmatrix}=\begin{pmatrix} 2& 1\\ -5& 3\end{pmatrix}$ is an invertible matrix with determinant $1$. Fitting $A$ using $\iota_{1,3}$ and multiplying, we get

\begin{align*} \iota_{1,3}(A)B &=\begin{pmatrix} \sigma&0& \tau\\0&1&0\\-\gamma&0& \alpha\end{pmatrix}\begin{pmatrix} 6 & 18 & 15 \\ 12 & 8 & 9 \\ 10 & 6 & 8 \end{pmatrix}\\ &= \begin{pmatrix} 6\sigma+10\tau & 18\sigma+6\tau & 15\sigma+8\tau \\ 12 & 8 & 9 \\ -6\gamma+10\alpha & -18\gamma+6\alpha & -15\gamma+8\alpha \end{pmatrix} = \begin{pmatrix} 2 & 30 & 22 \\ 12 & 8 & 9 \\ 0 & -72 & -51 \end{pmatrix}. \end{align*}

(In words, we replaced the pivot $6=a_{1,1}$ with the better pivot $2$ that divides any other entry by getting rid of the factor $3=\alpha=a_{1,1}/\operatorname{gcd}(a_{1,1},a_{3,1})$. If there were other entries that this new pivot didn't divide we would have applied the same procedure, again taking an entry that is not divisible.)

We are done with this step, as the new pivot $2=a_{1,1}'$ divides any other entry in the column $1=j_1$.

Step III ($t=1$): Now we get rid of $12=a_{2,1}$ by adding $-6$ times the first row to it:

\begin{align*} \iota_{1,2}\left(\begin{pmatrix} 1&0\\-6&1\end{pmatrix}\right)\begin{pmatrix} 2 & 30 & 22 \\ 12 & 8 & 9 \\ 0 & -72 & -51 \end{pmatrix} &=\begin{pmatrix} 1& 0&0\\-6& 1&0\\0&0&1\end{pmatrix} \begin{pmatrix} 2 & 30 & 22 \\ 12 & 8 & 9 \\ 0 & -72 & -51 \end{pmatrix}\\ &=\begin{pmatrix} 2 & 30 & 22 \\ 0 & -172 & -123 \\ 0 & -72 & -51 \end{pmatrix}=B'. \end{align*}

Next applying analogous procedures to the first row produces a matrix of the form

$$\begin{pmatrix} 2 & 0 & 0 \\ 0 & \ast & \ast \\ 0 & \ast & \ast \end{pmatrix}.$$

(In our case $30=a_{1,2}$ and $22=a_{1,3}$ were both multiples of the pivot $2=a_{1,1}$, so all we needed to do was to multiply $B'$ from the right by some $\iota_{1,2}$ and $\iota_{1,3}$. In the general case we would have to go through a step analogous to Step II($t=1$) above for rows. This could mess up the zeros we obtained so far; the point is that each time we do Step II for rows or columns, we end up taking a multiple out to get more divisibility, so that in finitely many steps we will be done.)

We can now set $t=2$ and go back to Step I. In our case this means to apply the same procedure so far to the $2\times 2$ matrix on the bottom right corner of $\begin{pmatrix} 2 & 0 & 0 \\ 0 & \ast & \ast \\ 0 & \ast & \ast \end{pmatrix}$.

Going through the algorithm we end up with a diagonal matrix; the final step is to ensure the divisibility condition (I'm skipping explaining this; it should be $D=\begin{pmatrix} 1&0&0\\0&2&0\\0&0&84\end{pmatrix}$ provided that the aforementioned calculator is working properly). Note that this means that

$$\begin{pmatrix} 1&0&0\\0&2&0\\0&0&84\end{pmatrix}= L \begin{pmatrix} 6 & 18 & 15 \\ 12 & 8 & 9 \\ 10 & 6 & 8 \end{pmatrix} R,$$

where both $L$ and $R$ are $3\times 3$ matrices that are the products of finitely many $\iota_{\bullet,\bullet}(\bullet)$. Each such matrix is with integer coefficients and invertible, and the inverse of each such matrix will also be with integer coefficients, so that we have $B=L^{-1} D R^{-1}$, and $\det(L)=1=\det(R)$. In words, this means that any square matrix with integer coefficients is diagonal with integer coefficients up to volume preserving linear coordinate changes (of course Smith normal forms apply to non-square matrices too).