imported>D.Lazard: /* History */ Assertion about Montante is dubious and unsourced. Assertion about Edmonds is also dubious. It is possible that Edmonds descibed the algorithm independently of Bareiss, in the same year, but asserting this requires a reliable source.

2025-03-19T03:24:07Z

History: Assertion about Montante is dubious and unsourced. Assertion about Edmonds is also dubious. It is possible that Edmonds descibed the algorithm independently of Bareiss, in the same year, but asserting this requires a reliable source.

New page

{{Short description|Algorithm for determinants of integers}}
In mathematics, the '''Bareiss algorithm''', named after [[Erwin Bareiss]], is an [[algorithm]] to calculate the [[determinant]] or the [[echelon form]] of a [[Matrix (mathematics)|matrix]] with [[integer]] entries using only integer arithmetic; any [[division (mathematics)|division]]s that are performed are guaranteed to be exact (there is no [[remainder]]). The method can also be used to compute the determinant of matrices with (approximated) [[real number|real]] entries, avoiding the introduction of any round-off errors beyond those already present in the input.

==Overview==
[[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 or [[Leibniz_formula_for_determinants|Leibniz formula]] is impractical, as it requires O(''n!'') operations.

[[Gaussian_elimination#Computing_determinants|Gaussian elimination]] has O(''n''3) complexity, but introduces division, which results in round-off errors when implemented using floating point numbers.

[[Round-off_error|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.<ref>{{citation|last1=Middeke|first1=J.|last2=Jeffrey|first2=D.J.|last3=Koutschan|first3=C.|title=Common Factors in Fraction-Free Matrix Decompositions|journal= Mathematics in Computer Science|year=2020|volume=15|issue=4|pages=589–608|doi=10.1007/s11786-020-00495-9|arxiv=2005.12380|doi-access=free}}</ref>

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:<ref name="bareiss">{{citation|first=Erwin H.|last=Bareiss|title= Sylvester's Identity and multistep integer-preserving Gaussian elimination|pages=565–578|url=https://www.ams.org/journals/mcom/1968-22-103/S0025-5718-1968-0226829-0/S0025-5718-1968-0226829-0.pdf|journal=[[Mathematics of Computation]]|year=1968|volume=22|issue=103|doi=10.2307/2004533|jstor=2004533}}</ref><ref>{{citation|first=Erwin H.|last=Bareiss|title=MULTISTEP INTEGER-PRESERVING GAUSSIAN ELIMINATION|url=https://digital.library.unt.edu/ark:/67531/metadc1035277/m2/1/high_res_d/4474185.pdf|year=1966}}. ''(Contains a clearer picture of the operations sequence)''</ref>
# Division-free algorithm — performs matrix reduction to triangular form without any division operation.
# Fraction-free algorithm — uses division to keep the intermediate entries smaller, but due to the [[Sylvester's determinant identity | Sylvester's Identity]] the transformation is still integer-preserving (the division has zero remainder).

For completeness Bareiss also suggests fraction-producing multiplication-free elimination methods.<ref name="bareiss"/>

==The algorithm==
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 each {{mvar|M}}{{mvar|k,k}} entry contains the leading principal [[Minor_(linear_algebra)|minor]] [{{mvar|M}}]{{mvar|k,k}}. Algorithm correctness is easily shown by induction on {{mvar|k}}.<ref>{{citation|last=Yap|first=Chee Keng|title=Fundamental Problems of Algorithmic Algebra|publisher=Oxford University Press|year=2000}}</ref>

{{framebox|blue}}
* Input: {{mvar|M}} — an {{mvar|n}}-square matrix assuming its leading principal minors [{{mvar|M}}]{{mvar|k,k}} are all non-zero.
* Let ''M''0,0 {{=}} 1 (Note: ''M''0,0 is a special variable)
* For {{mvar|k}} from 1 to {{mvar|n}}−1:
** For {{mvar|i}} from {{mvar|k}}+1 to {{mvar|n}}:
*** For {{mvar|j}} from {{mvar|k}}+1 to {{mvar|n}}:
**** Set <math>M_{i,j} = \frac{M_{i,j} M_{k,k} - M_{i,k} M_{k,j}}{M_{k-1,k-1}}</math>
*** Set ''M''i,k {{=}} 0
* Output: The matrix is modified [[In-place_algorithm|in-place]], each {{mvar|M}}{{mvar|k,k}} entry contains the leading minor [{{mvar|M}}]{{mvar|k,k}}, entry {{mvar|Mn,n}} contains the determinant of the original {{mvar|M}}.
{{frame-footer}}

If the assumption about principal minors turns out to be false, e.g. if {{mvar|M}}{{mvar|k}}−1,{{mvar|k}}−1 = 0 and some {{mvar|M}}{{mvar|i}},{{mvar|k}}−1 ≠ 0 ({{mvar|i}} = {{mvar|k}},...,{{mvar|n}}) then we can exchange the {{mvar|k}}−1-th row with the {{mvar|i}}-th row and change the sign of the final answer.

==Analysis==
During execution of the Bareiss algorithm, every integer that is computed is the determinant of a submatrix of the input matrix. This allows, using the [[Hadamard inequality]], to bound the size of these integers. Otherwise, the Bareiss algorithm may be viewed as a variant of [[Gaussian elimination]] and needs roughly the same number of arithmetic operations.

It follows that, for an ''n'' × ''n'' matrix of maximum (absolute) value 2''L'' for each entry, the Bareiss algorithm runs in [[Big O notation|O(''n''3)]] elementary operations with an O(''n''''n''/2 2''nL'') bound on the absolute value of intermediate values needed. Its [[computational complexity]] is thus O(''n''5''L''2 (log(''n'')2 + ''L''2)) when using elementary arithmetic or O(''n''4''L'' (log(''n'') + ''L'') log(log(''n'') + ''L''))) by using [[fast multiplication]].

==References==
{{reflist}}

{{Numerical linear algebra}}

{{DEFAULTSORT:Bareiss Algorithm}}
[[Category:Determinants]]
[[Category:Numerical linear algebra]]
[[Category:Exchange algorithms]]
[[Category:Computer algebra]]

Bareiss algorithm - Revision history

imported>D.Lazard: /* History */ Assertion about Montante is dubious and unsourced. Assertion about Edmonds is also dubious. It is possible that Edmonds descibed the algorithm independently of Bareiss, in the same year, but asserting this requires a reliable source.