I am trying to understand the algorithm presented in Wikipedia on how to calculate the Smith Normal Form of a matrix. I understand how to transform the matrix into a diagonal matrix and that the number of steps in this process is finite is due to the finite number of prime factors that divide an element.
However, I am having trouble understanding how to transform the diagonal matrix into one such that $a_1|a_{2}|a_3…$.
I don't see how this process should be finite. Suppose we consider the diagonal matrix $diag(a_1,a_2,a_3,a_4,…)$.
According to the algorithm we can transform the matrix to a matrix $diag(a_1',a_2',a_3,…)$ where $a_1'|a_2'$. However, if we implement the step again for this new matrix, we get $diag(a_1',a_2'',a_3',a_4,…)$ such that $a_2''|a_3'$ but now, it might not be the case that $a_1'|a_2''$. So I'm confused as to how this process would terminate. I do not understand the terminating condition given in wikipedia.
Could someone care to explain?
Best Answer
Go from $(a_1,a_2,\ldots,a_n)$ to $(a_1,a'_2,a'_3,\ldots,a'_n)$ where $a_1 |a'_i$ for all $i>1$.
Rewrite that as $(a_1,a_1 b_2, a_1 b_3,\ldots,a_1 b_n)$.
Now do the same thing, but to $(b_2,b_3,\ldots,b_n)$. Et cetera.