Wait, What?
Gaussian elimination can be exact without letting fractions explode everywhere.
The Bareiss algorithm is a fraction-free form of Gaussian elimination designed for exact arithmetic. It transforms an integer or polynomial matrix much like ordinary elimination, but uses a carefully chosen exact division at each stage so intermediate values stay far smaller than they would under naive rational arithmetic. The method is one of the clearest ways to learn how algebraic identities can change the computational behaviour of a familiar algorithm without changing the mathematical answer.
Quick Answer
Learn Bareiss through determinants → ordinary elimination → coefficient growth → fraction-free recurrence → exact-division invariant → pivoting → worked integer examples → symbolic domains → complexity → implementation and testing. The professional skill is not memorising a formula. It is understanding why the division is exact and when fraction-free elimination is preferable to floating-point or modular methods.
1. Start With the Problem Ordinary Gaussian Elimination Creates
Gaussian elimination is efficient because it replaces an expensive determinant expansion with a sequence of row eliminations. Over floating-point numbers this is standard. Over exact integers, however, ordinary elimination introduces rational fractions. If every intermediate result is stored as a reduced rational number, numerators and denominators can grow rapidly. The arithmetic operation count may still look cubic, yet the integers inside those operations become expensive to represent and manipulate.
Bareiss attacks that representation problem directly. It preserves exactness while controlling intermediate growth.
2. The Fraction-Free Update
Let the current pivot be a[k][k] and let the previous pivot-like divisor be p, initially 1. For entries below and to the right of the pivot, Bareiss uses the update
a[i][j] = (a[k][k] * a[i][j] - a[i][k] * a[k][j]) / pAfter the update, the eliminated column entries are set to zero. Then p becomes the current pivot before the next stage.
The remarkable part is the division. Under the algorithm’s conditions, that division is exact. It is not an approximate numerical division and it is not a heuristic simplification.
3. Work a 3×3 Integer Matrix by Hand
Take
A = [[2, 3, 1],
[4, 1, 5],
[6, 2, 4]]At the first stage, the previous divisor is 1 and the pivot is 2. Update the lower-right block:
- new a[1][1] = 2·1 − 4·3 = −10
- new a[1][2] = 2·5 − 4·1 = 6
- new a[2][1] = 2·2 − 6·3 = −14
- new a[2][2] = 2·4 − 6·1 = 2
The matrix has now moved one elimination stage forward without introducing any fractions. On the next stage, the denominator is the previous pivot 2. The next transformed bottom-right value becomes
((−10)·2 − (−14)·6) / 2 = 32For this 3×3 case, the final diagonal entry is the determinant, up to any sign changes introduced by row swaps. The determinant is 32.
4. Why the Division Is Exact
The exactness is linked to Sylvester-type determinantal identities. During fraction-free elimination, the transformed entries can be interpreted through minors of the original matrix. The denominator used at one stage divides the numerator constructed at the next stage because both arise from related determinants.
This is the central invariant to learn. A weak understanding says, “the denominator happens to divide.” A strong understanding says, “the recurrence is engineered so that determinant identities guarantee divisibility.”
5. Pivoting Still Matters
If the current pivot is zero, the algorithm cannot proceed with that pivot. Row interchange can restore progress when a suitable nonzero entry exists below it. Each row swap flips the determinant sign.
For exact arithmetic, pivot choice is not mainly about floating-point stability; it is about avoiding illegal division and, in some implementations, controlling coefficient growth. The pivot policy therefore remains part of the algorithm contract.
6. Bareiss Versus Rational Gaussian Elimination
Suppose an integer matrix is eliminated using exact fractions. Every row operation may create numerators and denominators that must be multiplied, reduced and stored. Bareiss instead keeps entries in the underlying integral domain when exact division is available. That can make a dramatic difference in symbolic computation.
This is why modern computer algebra systems still expose Bareiss-style determinant computation. SymPy, for example, documents Bareiss as one of its determinant methods for exact matrices.
7. Complexity: Arithmetic Count Is Not the Whole Story
The elimination structure uses roughly O(n³) arithmetic operations, comparable in shape to Gaussian elimination. But for exact algorithms, bit complexity matters because operands grow. Bareiss is valuable because the intermediate integers are tied to minors and therefore have controlled size relative to naive fraction arithmetic.
Professional analysis should distinguish:
- number of arithmetic operations;
- bit length of intermediate integers;
- cost of exact division;
- cost of gcd reduction avoided by fraction-free arithmetic;
- benefits of alternative modular or multimodular determinant methods on very large problems.
8. Integer Matrices Are Only the Beginning
The same fraction-free idea is useful over polynomial rings and other integral domains where exact division can be defined appropriately. This is one reason Bareiss belongs in symbolic linear algebra rather than only in a lesson about integer determinants.
Over floating point, however, fraction-free elimination is usually not the default numerical method. LU factorization with pivoting, QR methods and specialized numerical linear algebra are designed around floating-point error and conditioning rather than exact divisibility.
9. A Clean Implementation Skeleton
def bareiss_det(A):
A = deep_copy(A)
n = len(A)
sign = 1
prev = 1
for k in range(n - 1):
if A[k][k] == 0:
r = find_nonzero_row_below(A, k)
if r is None:
return 0
swap_rows(A, k, r)
sign *= -1
pivot = A[k][k]
for i in range(k + 1, n):
for j in range(k + 1, n):
num = pivot * A[i][j] - A[i][k] * A[k][j]
assert num % prev == 0
A[i][j] = num // prev
A[i][k] = 0
prev = pivot
return sign * A[n - 1][n - 1]The assertion is pedagogically valuable. During learning, exact divisibility should be tested rather than silently assumed. In polynomial domains, the corresponding exact-division operation must be domain-aware.
10. Test the Invariants, Not Just the Final Answer
A professional test suite should include:
- 1×1 and 2×2 matrices;
- singular matrices;
- matrices requiring a row swap;
- random small integer matrices checked against a trusted determinant routine;
- large-magnitude integer entries;
- polynomial-entry examples if the implementation supports them;
- an assertion that every Bareiss division is exact;
- determinant sign checks after multiple swaps.
11. Learn It With Predict–Trace–Explain–Modify–Build
Programming-education research supports beginning with readable working code before asking novices to invent a full solution. A strong learning sequence is:
- Predict: predict whether ordinary exact elimination will create a fraction on a small matrix.
- Trace: calculate one Bareiss stage by hand and mark the pivot, previous divisor and numerator.
- Explain: explain why the algorithm uses the previous pivot rather than the current one as divisor.
- Modify: add pivoting and exact-division assertions to a supplied implementation.
- Build: write an independent determinant routine and compare it with LU, Laplace expansion and a computer-algebra reference.
Subgoal-labelled worked examples are especially useful here because students can separate the jobs of choosing a pivot, forming the fraction-free numerator, performing exact division and updating the divisor.
Common Failure States
- Dividing by the current pivot instead of the previous pivot.
- Forgetting that the initial previous divisor is 1.
- Using ordinary floating-point division and losing the exactness property.
- Failing to change determinant sign after a row swap.
- Assuming every pivot sequence is valid when a pivot becomes zero.
- Confusing fraction-free elimination with “division-free” arithmetic; Bareiss does divide, but the division is exact.
- Claiming Bareiss is universally best for determinant computation; modular methods may outperform it for very large exact problems.
Practice Ladder
- Beginner: compare Laplace expansion and Gaussian elimination on a 3×3 integer matrix.
- Foundation: trace two Bareiss stages and verify every exact division.
- Intermediate: implement pivoting and determinant sign tracking.
- Advanced: compare operand growth in rational Gaussian elimination and Bareiss on random integer matrices.
- Professional: benchmark Bareiss, modular determinant methods and numerical LU across exact integer, polynomial and floating-point workloads, explaining why different domains prefer different algorithms.
Learning Hall Boundary
This article owns Bareiss as a fraction-free exact-elimination algorithm for determinants and symbolic linear algebra. It does not replace the existing general numerical-linear-algebra, LU/QR/SVD, Krylov, sparse-reordering or optimization articles. It also remains separate from MindOS, Bolt and Student/Studying Interface learner-operation jobs.
Evidence Boundary
The foundational reference is Erwin H. Bareiss, “Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination,” Mathematics of Computation 22 (1968). Modern symbolic-computation references continue to use fraction-free elimination, and current SymPy documentation exposes Bareiss as a determinant method. The teaching design here is informed by PRIMM-style code reading, subgoal-labelled worked examples and scaffolded code reconstruction research.
Professional rule: you understand Bareiss when you can derive the update from elimination, explain why the division is exact, handle zero pivots correctly, and justify when exact fraction-free arithmetic is preferable to floating-point or modular alternatives.
