position (t,jt) are zero. This can be achieved by left-multiplication with an appropriate matrix. However, to make the matrix fully diagonal we need to eliminate nonzero entries on the row of position (t,jt) as well. This can be achieved by repeating the steps in Step II for columns instead of rows, and using multiplication on the right by the transpose of the obtained matrix L. In general this will result in the zero entries from the prior application of Step III becoming nonzero again. However, notice that each application of Step II for either rows or columns must continue to reduce the value of , and so the process must eventually stop after some number of iterations, leading to a matrix where the entry at position (t,jt) is the only non-zero entry in both its row and column. At this point, only the block of A to the lower right of (t,jt) needs to be diagonalized, and conceptually the algorithm can be applied recursively, treating this block as a separate matrix. In other words, we can increment t by one and go back to Step I. Final step Applying the steps described above to the remaining non-zero columns of the resulting matrix (if any), we get an -matrix with column indices where . The matrix entries are non-zero, and every other entry is zero. Now we can move the null columns of this matrix to the right, so that the nonzero entries are on positions for . For short, set for the element at position . The condition of divisibility of diagonal entries might not be satisfied. For any index for which , one can repair this shortcoming by operations on rows and columns and only: first add column to column to get an entry in column i without disturbing the entry at position , and then apply a row operation to make the entry at position equal to as in Step II; finally proceed as in Step III to make the matrix diagonal again. Since the new entry at position is a linear combination of the original , it is divisible by β. The value does not change by the above operation (it is δ of the determinant of the upper submatrix), whence that operation does diminish (by moving prime factors to the right) the value of So after finitely many applications of this operation no further application is