structural:scholar_edition
Bareiss algorithm

The first strongly-polynomial time algorithm for Gaussian elimination was published by Jack Edmonds in 1967. Independently, and almost simultaneously, Erwin Bareiss discovered another algorithm, based on the following remark, which applies to a division-free variant of Gaussian elimination.

In standard Gaussian elimination, one subtracts from each row R i {\displaystyle R_{i}} below the pivot row R k {\displaystyle R_{k}} a multiple of R k {\displaystyle R_{k}} by r i, k / r k, k, {\displaystyle r_{i,k}/r_{k,k},} where r i, k {\displaystyle r_{i,k}} and r k, k {\displaystyle r_{k,k}} are the entries in the pivot column of R i {\displaystyle R_{i}} and R k, {\displaystyle R_{k},} respectively.

Bareiss variant consists, instead, of replacing R i {\displaystyle R_{i}} with r k, k R i − r i, k R k r k − 1, k − 1. {\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.} This produces a row echelon form that has the same zero entries as with the standard Gaussian elimination.

Bareiss' main remark is that each matrix entry generated by this variant is the determinant of a submatrix of the original matrix.

In particular, if one starts with integer entries, the divisions occurring in the algorithm are exact divisions resulting in integers. So, all intermediate entries and final entries are integers. Moreover, Hadamard inequality provides an upper bound on the absolute values of the intermediate and final entries, and thus a bit complexity of O ~ (n 5), {\displaystyle {\tilde {O}}(n^{5}),} using soft O notation.

Moreover, as an upper bound on the size of final entries is known, a complexity O ~ (n 4) {\displaystyle {\tilde {O}}(n^{4})} can be obtained with modular computation followed either by Chinese remaindering or Hensel lifting.

As a corollary, the following problems can be solved in strongly polynomial time with the same bit complexity: