Construction of the Smith Normal Form of a matrix

Question

When finding the Smith Normal Form of a given matrix $A$, I do not understand why we can assume $(A_{11})$ is the $\gcd$ of all the entries of the matrix $A$, i.e., how can we generate the $\gcd$ of all the entries (performing elementary columns and row operations) and put it in the position $(1,1)$ of the matrix?

Answer 1

Using the Euclidean algorithm on rows/columns, first ensure that $A_{11}$ divides all entries $A_{i1}$ in the same column, and then use this to set all $A_{i,1}:=0$ (for $i>1$). Ditto for the row $A_{1i}$. Now suppose there is an entry $A_{ij}$ (for $i,j>1$) that is not divisible by $A_{11}$. Then add the $i$-th row to the first, this keeps $A_{11}$ the same and sets $A_{1j}=A_{ij}$. return to cleaning out row $1$.