## Echelon Form Lemma (Column Echelon vs Smith Normal Form)

The pivots in column-echelon form are the same as the diagonal elements in (Smith) normal form. Moreover, the degree of the basis elements on pivot rows is the same in both forms.

Proof:
Due to the initial sort, the degree of row basis elements $\hat{e}_i$ is monotonically decreasing from the top row down. For each fixed column $j$, $\deg e_j$ is a constant. We have, $\deg M_k(i,j)=\deg e_j-\deg \hat{e}_i$. Hence, the degree of the elements in each column is monotonically increasing with row. That is, for fixed $j$, $\deg M_k(i,j)$ is monotonically increasing as $i$ increases.

We may then eliminate non-zero elements below pivots using row operations that do not change the pivot elements or the degrees of the row basis elements. Finally, we place the matrix in (Smith) normal form with row and column swaps.