It is given that $a_1=\gcd(a_{11}, a_{12} , \cdots , a_{mn})$. Then prove that after elementary row and column operation we get …

euclidean-domainlinear algebramatricesmodulessmith-normal-form

This is a question related to Smith Normal form I guess but I couldn't do the proof by my own using elementary row and column operation. So here is the problem:

Suppose $$(a_{ij})=
\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{pmatrix}
$$
It is given that $a_{ij} \in \Bbb Z$(or any euclidean domain) $a_1=gcd(a_{11}, a_{12} , \cdots , a_{mn})$.
Then prove that after elementary row and column operation we get $$(a_{ij}) \rightarrow \begin{pmatrix}
a_{1} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}\\
\end{pmatrix}
$$ where $a_1|a_{ij}$

Now I was trying in this way that let us take $m=2$ and $n=3$ $a_1=\gcd(a_{11}, a_{12} , \cdots , a_{23})$, so $a_1=b_{11}a_{11}+\cdots+b_{23}a_{23}$ and the matrix is
$$
\begin{pmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
\end{pmatrix} \rightarrow^{b_{11}R_1+b_{21}R_2} \begin{pmatrix}
b_{11}a_{11}+b_{21}a_{21} & b_{11}a_{12}+b_{21}a_{22} & b_{11}a_{13}+b_{21}a_{23} \\
a_{21} & a_{22} & a_{23} \\
\end{pmatrix} \rightarrow^{C_1+\frac{b_{12}}{b_{11}}C_2+\frac{b_{13}}{b_{11}}C_3} \begin{pmatrix}
b_{11}a_{11}+b_{21}a_{21}+b_{12}a_{12}+\frac{b_{12}b_{21}}{b_{11}}a_{22}+b_{13}a_{13}+\frac{b_{21}b_{13}}{b_{11}} a_{23}& b_{11}a_{12}+b_{21}a_{22} & b_{11}a_{13}+b_{21}a_{23} \\
a_{21} & a_{22} & a_{23} \\
\end{pmatrix}
$$

1.Now how can we fix $\frac{b_{12}b_{21}}{b_{11}}a_{22}+\frac{b_{21}b_{13}}{b_{11}} a_{23}$?

  1. After explaining with simple matrix, can you give me some hint about the general case? (I think that my way of thinking is not proper here as well)

Best Answer

A key observation is that whenever we add a multiple of one row or a column to another, the gcd of the entries stays the same. This is because the entries of the "new" matrix are surely all divisible by the gcd of the entries of the old matrix. The reverse also holds because such row/column operations are reversible.

A possibility is to do it in several stages. A key observation is that if the entries on some row have $\gcd=d$, say $d=\gcd(a_{i1},a_{i2},\ldots,a_{in})$, then we can perform a sequence of column operations to make $d$ appear on that row:

  • By performing column operations involving the two first columns only, we can make $\gcd(a_{i1},a_{i2})$ appear in position $(i,1)$.
  • Then by performing column operations involving columns one and three, we can make $\gcd(a_{i1},a_{i2},a_{i3})$ appear in position $(i,1)$ et cetera.

Similarly, by performing a sequence of row operations, we can make the gcd of entries on a column to appear in that column.

This leads to the following pseudocode/algorithm:

  1. Perform a sequence of column operations such that $d=\gcd(a_{11},a_{12},\ldots,a_{1n})$ appears at position $(1,1)$.
  2. Because all the entries $a_{12},\ldots,a_{1n}$ arenow divisible by $a_{11}$, we can perform a sequence of column operations such that the first row has the form $(a_{current},0,0,\ldots,0)$.
  3. If all the matrix entries are divisible by $a=a_{current}$, we are done. Otherwise there is an entry $a_{ij}, i>1$, such that $a\nmid a_{ij}$.
  4. If $a\nmid a_{i1}$, then we don't need to anything in this step. Otherwise we can add a multiple of column $j$ to the first column so that $a\nmid a_{i1}$. Observe that as a consequence of step 2 this column operation does not change the first row at all.
  5. Let $a_{new}=\gcd(a_{11}=a_{current},a_{i1})$. By a sequence of row operations we get a matrix such that $a_{new}$ appears at position $(1,1)$. Observe that because $a_{i1}\nmid a_{11}$, $a_{new}$ is a proper divisor of $a_{current}$.
  6. In step 5 the first row received new non-zero entries. Let's go back to step 1.

The algorithm terminates because we can find a proper divisor of a non-zero integer only finitely many times. So after some number of iterations we can exit in step 3.

A numerical example $$ A=\left(\begin{array}{ccc}18&12&24\\51&33&60\\15&-3&22\end{array}\right). $$ We see that the gcd of the top row is $6$. We can arrange it to appear at position $(1,1)$ simply by subtracting the second column from the first $$ \to\left(\begin{array}{ccc}6&12&24\\18&33&60\\18&-3&22\end{array}\right). $$ Then we create those zeros: $$ \to\left(\begin{array}{ccc}6&0&0\\18&-3&12\\18&-39&-50\end{array}\right). $$ The entry at $(2,2)$ is not divisible by six but the entry $(2,1)$ is, so we "fix" this by adding the second column to the first. Might as well add it multiplied by $5$ to create a smaller entry: $$ \to\left(\begin{array}{ccc}6&0&0\\3&-3&12\\-177&-39&-50\end{array}\right). $$ It is our lucky day in that $\gcd(a_{11},a_{12})=\gcd(6,3)=3$ already appears at $(2,1)$, so we simply swap the two rows: $$ \to\left(\begin{array}{ccc}3&-3&12\\ 6&0&0\\-177&-39&-50\end{array}\right). $$ We are back in step 1 with $a_{new}=3$ having replaced $a_{old}=6$. Again, we are lucky, and $3$ is the gcd of the top row. Let's just create those zeros again: $$ \to\left(\begin{array}{ccc}3&0&0\\ 6&6&-24\\-177&-216&-758\end{array}\right). $$ We see that the entry $a_{33}=-758$ is the only entry not divisibly by $a_{current}=3$. We use it to make the entry $a_{31}$ not divisible by three by adding the last colum to the first: $$ \to\left(\begin{array}{ccc}3&0&0\\ -18&6&-24\\-935&-216&-758\end{array}\right). $$ We then produce $\gcd(3,-758)=1$ to the first column simply by adding a multiple of the top row to the third: $$ \to\left(\begin{array}{ccc}3&0&0\\ -18&6&-24\\1&-216&-758\end{array}\right). $$ Then we swap the 1st and 3rd rows and we are done: $$ \to\left(\begin{array}{ccc}1&-216&-758\\ -18&6&-24\\ 3&0&0\end{array}\right). $$

Many obviously unnecessary steps here. Different combos of operations will surely make it cleaner. My numerical example was crafted to make the Euclidean algorithms calculating the gcd of two integers extremely simple. In general you may need to do several row/column operations while calculating the gcd of two chosen entries.

Related Question