Euclidean row and column reduction computes Smith normal form

If the matrix is empty or zero, return the empty or zero Smith form. Otherwise move a nonzero entry of least Euclidean value among the current entries into the upper-left pivot position by row and column swaps.

Divide every entry in the pivot row and column by the pivot and use elementary operations to replace a nonzero remainder into the pivot position. If an entry outside that row and column is not divisible by the pivot, add its row to the pivot row and repeat. Each nonzero remainder has strictly smaller Euclidean value, so this descent terminates with a pivot dividing every entry.

Clear the rest of the pivot row and column using exact division, then apply the same procedure to the smaller remaining rectangle. The row or column count strictly decreases at each recursion, and zero or rank-deficient tails stop immediately.

Because each chosen pivot divides every entry in the remaining rectangle, successive nonzero pivots satisfy $d_1\mid d_2\mid \cdots$. Unit normalization gives Smith form; equivalently, adjacent diagonal factors may be replaced by their gcd and lcm through elementary operations without changing equivalence. The output agrees with the existence theorem [L1], but termination here uses the Euclidean function and is not a proof over an arbitrary PID.