In mathematics, theBareiss algorithm, named afterErwin Bareiss, is analgorithm to calculate thedeterminant or theechelon form of amatrix withinteger entries using only integer arithmetic; anydivisions that are performed are guaranteed to be exact (there is noremainder). The method can also be used to compute the determinant of matrices with (approximated)real entries, avoiding the introduction of any round-off errors beyond those already present in the input.
Determinant definition has only multiplication, addition and subtraction operations. Obviously the determinant is integer if all matrix entries are integer. However actual computation of the determinant using the definition orLeibniz formula is impractical, as it requires O(n!) operations.
Gaussian elimination has O(n3) complexity, but introduces division, which results in round-off errors when implemented using floating point numbers.
Round-off errors can be avoided if all the numbers are kept as integer fractions instead of floating point. But then the size of each element grows in size exponentially with the number of rows.[1]
Bareiss brings up a question of performing an integer-preserving elimination while keeping the magnitudes of the intermediate coefficients reasonably small. Two algorithms are suggested:[2][3]
For completeness Bareiss also suggests fraction-producing multiplication-free elimination methods.[2]
The program structure of this algorithm is a simple triple-loop, as in the standard Gaussian elimination. However in this case the matrix is modified so that eachMk,k entry contains the leading principalminor [M]k,k. Algorithm correctness is easily shown by induction onk.[4]
If the assumption about principal minors turns out to be false, e.g. ifMk−1,k−1 = 0 and someMi,k−1 ≠ 0 (i =k,...,n) then we can exchange thek−1-th row with thei-th row and change the sign of the final answer.
During execution of the Bareiss algorithm, every integer that is computed is the determinant of a submatrix of the input matrix. This allows, using theHadamard inequality, to bound the size of these integers. Otherwise, the Bareiss algorithm may be viewed as a variant ofGaussian elimination and needs roughly the same number of arithmetic operations.
It follows that, for ann ×n matrix of maximum (absolute) value 2L for each entry, the Bareiss algorithm runs inO(n3) elementary operations with an O(nn/2 2nL) bound on the absolute value of intermediate values needed. Itscomputational complexity is thus O(n5L2 (log(n)2 + L2)) when using elementary arithmetic or O(n4L (log(n) + L) log(log(n) + L))) by usingfast multiplication.