In mathematics, the Bareiss algorithm, named after Erwin Bareiss, is an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 to calculate the determinant

Determinant

In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

 of a matrix

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 with integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 entries using only integer arithmetic; any division

Division (mathematics)

right|thumb|200px|20 \div 4=5In mathematics, especially in elementary arithmetic, division is an arithmetic operation.Specifically, if c times b equals a, written:c \times b = a\,...

s that are performed are guaranteed to be exact (there is no remainder

Remainder

In arithmetic, the remainder is the amount "left over" after the division of two integers which cannot be expressed with an integer quotient....

). The method can also be used to compute the determinant of matrices with (approximated) real

Real number

In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

 entries, avoiding the introduction any round-off errors beyond those already present in the input.

For an n × n matrix of maximum (absolute) value 2^L for each entry, the Bareiss algorithm runs in O(n³)

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

elementary operations with an O(n ⁿ 2^nL) bound on the absolute value of intermediate values needed.

Calculating the determinant

To compute the determinant using the bareiss algorithm you must find the total number of elements in each row and multiply them by the total number of elements in each column.