Bareiss Fraction-Free Elimination

Gaussian elimination typically introduces fractions when eliminating variables. This can lead to severe numerical instability in floating-point arithmetic or require expensive rational number arithmetic. The Bareiss algorithm is a fraction-free variant of Gaussian elimination that ensures all intermediate entries in the matrix remain exact integers (provided the initial matrix contains integers).

Experiment

To see how the algorithm behaves with different inputs, visit the Bareiss Fraction-Free Elimination module.

1. Select the Dense matrix from the Matrix dropdown. Observe that the Final stored entry is 6 and the Determinant is 6.
2. Change the Matrix to Row swap. The algorithm must swap the first and second rows because the first pivot is zero. This changes the sign of the determinant to negative, so the final entry -16 is multiplied by -1 to give a Determinant of 16.
3. Select the Singular matrix. A pivot column cannot be found, which immediately identifies the determinant as 0 and the matrix as singular.
4. Select Larger entries. Notice how the Maximum stored magnitude grows up to 26, larger than the initial entries or final determinant.