**Proof plan.** The algorithm uses the Euclidean [function](/page/Function) $\varphi$ to reduce the top-left entry. Three moves are performed cyclically until no further reduction is possible: (i) use the division algorithm on a non-divisible entry in the first row, (ii) same for the first column, and (iii) use an off-diagonal entry not divisible by the current pivot to pull it into position. Termination is guaranteed since $\varphi(A_{11})$ strictly decreases at each step. **Step 1: Arrange a non-zero entry at position $(1,1)$.** If $A = 0$, we are done. Otherwise some entry is non-zero; by row and column swaps (which are elementary operations), bring it to position $(1,1)$. **Step 2: Reduce $A_{11}$ by the division algorithm (Steps i and ii).** If any entry $A_{1j}$ in the first row is not divisible by $A_{11}$, write $A_{1j} = q A_{11} + r$ with $\varphi(r) < \varphi(A_{11})$ and $r \neq 0$. Subtracting $q$ times column 1 from column $j$ places $r$ at position $(1, j)$. Swapping columns 1 and $j$ gives a strictly smaller $\varphi$ value at the $(1,1)$ position. Apply the same argument to the first column. **Step 3: Ensure $A_{11}$ divides all entries of the remaining block (Step iii).** Once $A_{11}$ divides every entry in the first row and column, clear them by elementary operations to reach a block form \begin{align*} A = \begin{pmatrix} d & 0 \\ 0 & C \end{pmatrix}. \end{align*} If some entry $A_{ij}$ ($i, j > 1$) of $C$ is not divisible by $d$, write $A_{ij} = qd + r$ with $r \neq 0$. Add column 1 to column $j$ and subtract $q$ times row 1 from row $i$; this places $r$ at position $(i, j)$. Swapping rows $i$ and 1, then columns $j$ and 1, brings $r$ to position $(1,1)$ with $\varphi(r) < \varphi(d)$. Return to Step 2 with a strictly smaller pivot. Since $\varphi$ takes non-negative integer values, this process terminates. **Step 4: Recursion on $C$.** When the process terminates at position $(1,1)$ with pivot $d_1$, we have $d_1 \mid C_{ij}$ for all $i, j$. Apply the entire algorithm recursively to $C$, obtaining invariant factors $d_2, d_3, \ldots, d_r$ with $d_2 \mid d_3 \mid \cdots \mid d_r$. The divisibility $d_1 \mid d_2$ holds since $d_1$ divides every entry of $C$, in particular the pivot $d_2$ found by the algorithm. The resulting diagonal matrix has the stated form. **Step 5: Uniqueness via Fitting ideals.** The $k$th Fitting ideal $\mathrm{Fit}_k(A)$ — the ideal generated by all $k \times k$ minors of $A$ — is preserved under elementary row and column operations. For the Smith normal form $D$, one computes $\mathrm{Fit}_k(D) = (d_1 d_2 \cdots d_k)$. Since Fitting ideals are invariants of the equivalence class of $A$, the products $d_1 \cdots d_k$ are uniquely determined (up to units), hence so are $d_1, \ldots, d_r$ up to associates. $\square$