Editing Smith normal form (section)

===Step II: Improving the pivot===
If there is an entry at position (''k'',''j''<sub>''t''</sub>) such that <math>a_{t,j_t} \nmid a_{k,j_t}</math>, then, letting <math>\beta =\gcd\left(a_{t,j_t}, a_{k,j_t}\right)</math>, we know by the Bézout property that there exist σ, τ in ''R'' such that

:<math>
a_{t,j_t} \cdot \sigma + a_{k,j_t} \cdot \tau=\beta.
</math>

By left-multiplication with an appropriate invertible matrix ''L'', it can be achieved that row ''t'' of the matrix product is the sum of σ times the original row ''t'' and τ times the original row ''k'', that row ''k'' of the product is another [[linear combination]] of those original rows, and that all other rows are unchanged. Explicitly, if σ and τ satisfy the above equation, then for <math>\alpha=a_{t,j_t}/\beta</math> and <math>\gamma=a_{k,j_t}/\beta</math> (which divisions are possible by the definition of β) one has

:<math>
\sigma\cdot \alpha + \tau \cdot \gamma=1,
</math>

so that the matrix

:<math> L_0=
\begin{pmatrix}
\sigma & \tau \\
-\gamma & \alpha \\
\end{pmatrix}
</math>

is invertible, with inverse

:<math>
\begin{pmatrix}
\alpha & -\tau \\
\gamma & \sigma \\
\end{pmatrix}
.</math>

Now ''L'' can be obtained by fitting <math>L_0</math> into rows and columns ''t'' and ''k'' of the [[identity matrix]]. By construction the matrix obtained after left-multiplying by ''L'' has entry β at position (''t'',''j''<sub>''t''</sub>) (and due to our choice of α and γ it also has an entry 0 at position (''k'',''j''<sub>''t''</sub>), which is useful though not essential for the algorithm). This new entry β divides the entry <math>a_{t,j_t}</math> that was there before, and so in particular <math>\delta(\beta) < \delta(a_{t,j_t})</math>; therefore repeating these steps must eventually terminate. One ends up with a matrix having an entry at position (''t'',''j''<sub>''t''</sub>) that divides all entries in column ''j''<sub>''t''</sub>.