TITLE: Smith normal form of a matrix A, prove first diagonal entry of the SNF is the hcf of the entries of A
QUESTION [0 upvotes]: So, as per the title, assuming that we know an $n \times n$ matrix $A$ with integer entries is equivalent (can be obtained via row/column operations on $A$) to a matrix with diagonal entries $d_1, d_2, ... , d_n$ where $0< d_i | d_{i+1}$ for each $1 \leq i \leq m-1$ (Smith Normal Form), show that $d_1$ is the highest common factor of the entries of the matrix $A$.
Firstly, it's obvious $d_1$ is the highest common factor of the entries in the diagonal matrix, for if there's some other common factor $d$ then $d | d_1$ by definition, but I've been unsuccessful in showing this is also true for the entries in the matrix $A$
Any help appreciated!

REPLY [1 votes]: If $d$ is the hcf, you can use it to clear out all entries in its row and column, and can then move $d$ to the upper left by swaps. What remains is a smaller matrix, so by induction, its SNF has ITS hcf in the upper left corner, and this HCF must be no less than $d$. 
So all that remains is to show that the upper left entry can't be LESS than the HCF. Well...all the row operations you perform don't change the hcf (recall that the row/col ops are only exchanges and "add k times row i to row j" for integers k (and similarly for cols). So since $d$ divides all the diagonal entries of the SNF, it also divides all the original entries. 
And I believe that's the whole story.
{"set_name": "stack_exchange", "score": 0, "question_id": 763931}