Editing Gaussian elimination (section)

===Bareiss algorithm===
{{main|Bareiss algorithm}}
The first [[strongly-polynomial time]] algorithm for Gaussian elimination was published by [[Jack Edmonds]] in 1967.<ref name=":0">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=37}} 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 <math>R_i</math> below the pivot row <math>R_k</math> a multiple of <math>R_k</math> by <math>r_{i,k}/r_{k,k},</math> where <math>r_{i,k}</math> and <math>r_{k,k}</math> are the entries in the pivot column of <math>R_i</math> and <math>R_k,</math> respectively.

Bareiss variant consists, instead, of replacing <math>R_i</math> with <math display=inline>\frac{r_{k,k}R_i-r_{i,k}R_k}{r_{k-1,k-1}}.</math> 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's inequality]] provides an upper bound on the absolute values of the intermediate and final entries, and thus a bit complexity of <math>\tilde O(n^5),</math> using [[soft O notation]].

Moreover, as an upper bound on the size of final entries is known, a complexity <math>\tilde O(n^4)</math> can be obtained with [[modular arithmetic|modular computation]] followed either by [[Chinese remainder theorem|Chinese remaindering]] or [[Hensel lifting]].

As a corollary, the following problems can be solved in strongly polynomial time with the same bit complexity:<ref name=":0" />{{Rp|page=40}}

* Testing whether ''m'' given rational vectors are [[linearly independent]]
* Computing the [[determinant]] of a rational matrix
* Computing a solution of a rational equation system ''Ax'' = ''b''
* Computing the [[inverse matrix]] of a nonsingular rational matrix
* Computing the [[Rank (linear algebra)|rank]] of a rational matrix