Bareiss Algorithm

Purpose: Compute the determinant (or solve a linear system) over the integers with exact arithmetic and no intermediate coefficient blowup — a fraction-free variant of Gaussian elimination.

The Problem It Solves

Plain Gaussian elimination on an integer matrix introduces fractions, and clearing denominators makes entries grow exponentially in the matrix size. Bareiss’s insight: at every step, divide by the previous pivot, and the division is guaranteed to be exact.

The Recurrence

$a_{ij}^{(k)}=\frac{a_{ij}^{(k-1)}{a}_{kk}^{(k-1)}-a_{ik}^{(k-1)}{a}_{kj}^{(k-1)}}{a_{k-1,k-1}^{(k-2)}},a_{00}^{(-1)}=1.$

The numerator is the familiar $2\times 2$ elimination step; the denominator is the pivot from two steps back. The magic is that this quotient is always an integer.

Code

// exact integer determinant, O(n^3) operations
long long bareiss(vector<vector<long long>> a) {
    int n = a.size();
    long long prev = 1, sign = 1;
    for (int k = 0; k < n - 1; k++) {
        if (a[k][k] == 0) {                        // pivot
            int p = -1;
            for (int r = k + 1; r < n; r++) if (a[r][k]) { p = r; break; }
            if (p < 0) return 0;
            swap(a[k], a[p]); sign = -sign;
        }
        for (int i = k + 1; i < n; i++)
            for (int j = k + 1; j < n; j++)
                a[i][j] = (a[i][j] * a[k][k] - a[i][k] * a[k][j]) / prev;  // exact
        prev = a[k][k];
    }
    return sign * a[n-1][n-1];
}

Why the division is exact

Every intermediate $a_{ij}^{(k)}$ equals a minor of the original matrix — specifically the determinant of the submatrix formed by rows $\mathrm{1..}k,i$ and columns $\mathrm{1..}k,j$. This is Sylvester’s identity. Since minors are integers, and the recurrence computes exactly the next minor from the previous ones, the division must come out whole. ∎

That characterisation also bounds the entry sizes: by Hadamard’s inequality, a $k\times k$ minor of a matrix with entries bounded by $M$ is at most $k^{k/2}{M}^k$, so the intermediate values are $O(n\log (nM))$ bits — polynomial, not exponential.

Complexity

• Arithmetic operations: $O(n^3)$, the same count as Gaussian elimination
• Bit complexity: $O(n^3\cdot n\log (nM))=\tilde{O}(n^4\log M)$ with schoolbook big integers
• Entry size: $O(n\log (nM))$ bits — versus exponential for naive fraction-clearing

When to use which

Goal	Method
Determinant mod a prime $p$	Gaussian elimination with modular inverses — simplest and fastest
Determinant mod a composite	Gaussian elimination with a Euclidean-style row reduction (no inverses needed)
Exact integer determinant	Bareiss
Determinant of a huge integer matrix	compute mod several primes and CRT, with a Hadamard bound to know when to stop
Characteristic polynomial	Faddeev-LeVerrier or the Hessenberg method

Contest advice

Most determinant problems ask for the answer modulo a prime, where plain modular Gaussian elimination is enough. Reach for Bareiss when the problem needs the exact value — for example counting spanning trees without a modulus, or lattice/volume computations.

Variants / Use Cases

• Gaussian Elimination — the standard method
• Matrix-Tree Theorem — exact spanning tree counts need exact determinants
• Determinant — the topic page
• Smith and Hermite normal forms — the other classical fraction-free integer matrix algorithms
• Cramer’s rule with exact minors — Bareiss gives all the minors along the way