Efficiently Calculating the Determinant of a Matrix

Felix Limanta 13515065

Program Studi Teknik Informatika
Sekolah Teknik Elektro dan Informatika
Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia
13515065@std.stei.itb.ac.id
felixlimanta@gmail.com

Abstract—There are three commonly-used algorithms to infotype is either real or integer, depending on
calculate the determinant of a matrix: Laplace expansion, LU implementation, while matrix is an arbitrarily-sized
decomposition, and the Bareiss algorithm. In this paper, we
array of array of infotype.
first discuss the underlying mathematical principles behind
the algorithms. We then realize the algorithms in pseudocode
Finally, we analyze the complexity and nature of the
algorithms and compare them after one another. II. BASIC MATHEMATICAL CONCEPTS

Keywords—asymptotic time complexity, Bareiss algorithm, A. Determinant

determinant, Laplace expansion, LU decomposition. The determinant is a real number associated with every
square matrix. The determinant of a square matrix A is
commonly denoted as det A, det(A), or |A|.
I. INTRODUCTION Singular matrices are matrices which determinant is 0.
In this paper, we describe three algorithms to find the Unimodular matrices are matrices which determinant is 1.
determinant of a square matrix: Laplace expansion (also The determinant of a 1×1 matrix is the element itself.
known as determinant expansion by minors), LU 𝐴 = [𝑎] ⇒ det(𝐴) = 𝑎
decomposition, and the Bareiss algorithm. The determinant of a 2×2 matrix is defined as the product
The paper is organized as follows. Section II reviews the of the elements on the main diagonal minus the product of
basic mathematical concepts for this paper, which includes the elements off the main diagonal.
determinants, elementary matrix operations, algorithm 𝑎 𝑏
| | = 𝑎𝑑 − 𝑏𝑐
𝑐 𝑑
complexities, time complexities, and asymptotic time Finding the determinant of larger matrices will be
complexities. In Section III, the three methods are discussed in later sections.
discussed in-depth mathematically, whereas in Section IV, Some basic properties of determinants are
the three methods, as well as subroutines necessary to
1. det(𝐼) = 1
implement them, are implemented in a language-agnostic
2. det(𝐴𝑇 ) = det(𝐴)
pseudocode. In Section V, the methods implemented in 1
Section V are analyzed regarding its asymptotic time 3. det(𝐴−1 ) =
det(𝐴)
complexity and other features before being compared to 4. For square matrices A and B of equal size,
one another. Finally, Section VI concludes the paper while det(𝐴𝐵) = det(𝐴) × det(𝐵)
suggesting further improvements. 5. The determinant of a triangular matrix is the product
of the diagonal entries (pivots) d1, d2, …, dn.
𝑛
Terminology and Notation
Unless noted otherwise, all mentions of matrices in this det(𝐴) = 𝑎1,1 𝑎2,2 … 𝑎𝑛,𝑛 = ∏ 𝑎𝑖,𝑖
𝑖=1
paper are assumed to be square matrices.
Determinants are useful for other mathematical subjects.
To describe iterations mathematically, the notation 𝑖 ∈
For example, following Cramer’s rule, a matrix can be used
[𝑎. . 𝑏] is introduced. The notation is taken from the
to represent the coefficients of a system of linear equations,
mathematical concept of number intervals, but instead of
and the determinant can be used to solve the system of
describing whether i is between a and b or not, it denotes
linear equations if and only if the matrix is nonsingular.
that the iterator i starts from a and ends in b, incrementing
Determinants are also used in determining the inverse of a
i by 1 after each iteration. It is equivalent to the for syntax matrix, where any matrix has a unique inverse if and only
in programming languages, in which 𝑖 ∈ [𝑎. . 𝑏] is if the matrix is nonsingular.
equivalent to for i = a to b.
The pseudocode described in section III follows the B. Elementary Matrix Operations
syntax detailed in reference [5].
For convenience, two data types are defined here: Elementary matrix operations play important roles in

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

various matrix algebra applications, such as solving a D. Time Complexity
system of linear equations using and finding the inverse of The time complexity of an algorithm is measured from
a matrix. the number of instructions executed. The time complexity
There are three kinds of elementary matrix operations: of an algorithm is not measured from the running time of
1. Switch two rows (or columns). said algorithm because of the differences between every
2. Multiply each element in a row (or column) by a computer’s architecture, every programming language and
non-zero number. its compiler, and so on. Because of that, the same algorithm
3. Add or subtract a row (or column) by multiples of implemented in different languages or the same executable
another row (or column). run in different machines would yield different running
When these operations are performed on rows, they are times.
called elementary row operations and, likewise, when they In calculating the time complexity of an algorithm,
are performed on columns, they are called elementary ideally, all operations are accounted for. For decently
column operations. complex algorithms, this is all but impossible, so
Elementary matrix operations have the following effect practically, only basic operations are accounted for. For
on determinants. example, the basic operation of a searching algorithm
1. Exchanging two rows or columns from a matrix would be the comparison of the searched element with
reverse the sign of its determinant from positive to elements in the array. By counting how many comparisons
negative and vice-versa. are made, we can obtain the relative efficiency of the
𝑎 𝑏 𝑐 𝑑 algorithm.
| | = −| |
𝑐 𝑑 𝑎 𝑏 The time complexity of an algorithm can be divided into
2. Multiplying one row or column of a matrix by t
three cases:
multiplies the determinant by t.
𝑡𝑎 𝑡𝑏 𝑡𝑎 𝑏 𝑎 𝑏  Tmin (𝑛): Best case
| |=| | = 𝑡| |  Tmax (𝑛): Worst case
𝑐 𝑑 𝑡𝑐 𝑑 𝑐 𝑑
3. If two rows or two columns of a matrix are equal, or  Tavg (𝑛): Average case
a row or column is the multiply of another row or
column, its determinant is zero. Example 1. Find the best case, worst case, and average
𝑎 𝑏 case time complexity of the following sequential search
| |=0
𝑡𝑎 𝑡𝑏 algorithm.
4. If 𝑖 ≠ 𝑗, adding or subtracting t times row i from
row j or vice-versa does not change the determinant. function SeqSearch (a: array of infotype,
𝑎 𝑏 𝑎 𝑏 n: integer, x: infotype) → integer
| |=| |
𝑐 − 𝑡𝑎 𝑑 − 𝑡𝑏 𝑐 𝑑 DICTIONARY
5. If A has a row that is all zeros, then det(𝐴) = 0. i: integer
𝑎 𝑏 found: boolean
| |=0 ALGORITHM
0 0
i ← 1
C. Algorithm Complexity found ← false
while ((i ≤ n) and not(found)) do
Algorithms are defined as the series of steps necessary found ← (a[i] = x)
to solve a problem systematically. An algorithm, first and if not(found) then
foremost, is not only required to be effective and actually i ← i + 1
solve the problem, but also expected to be efficient. An if (found) then
→ i
algorithm might be able to effectively solve a problem, but else
if the algorithm demands an unreasonable amount of → 0
processing time or takes up disproportionately large
amount of memory, the algorithm is next to useless.  Best case: 𝑎1 = 𝑥 ⇒ Tmin (𝑛) = 1
In application, every algorithm uses up two resources  Worst case: 𝑎𝑛 = 𝑛 or 𝑛 not found ⇒ Tmax (𝑛) = 𝑛
which can be used as measurement: the number of steps 1+2+⋯+𝑛 𝑛+1
 Average case: Tavg (𝑛) = =
taken (time) and the amount of memory reserved to execute 𝑛 2
those steps (space). The number of steps taken is defined
as the time complexity, denoted as T(n), whereas the E. Asymptotic Time Complexity
amount of memory reserved is defined as the space Usually, the exact time complexity of an algorithm is
complexity, denoted as S(n). unnecessary. Instead, what is needed is a rough estimate of
Matrices are a type of data structure which takes up a the time required by the algorithm and how fast that time
relatively large amount of memory, compared to more requirement grow with the size of the input. This is because
compact data structures such as linked lists. Therefore, the the efficiency of an algorithm would only be apparent at a
space complexity of the algorithms discussed later will not large number of inputs. Running the determinant-
be examined in favor of focusing on their time complexity. calculating algorithms on a 3×3 matrix would not yield
any notable differences between the algorithm running

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

times. However, if the algorithms are run on a large matrix More informally, expansion by minors can be written as
(say, 5000×5000), differences between running times 𝑎11 𝑎12 𝑎13 ⋯ 𝑎1𝑛
would be much more apparent. 𝑎21 𝑎22 𝑎23 ⋯ 𝑎2𝑛
| ⋮ ⋮ ⋮ ⋮ |
The asymptotic time complexity is a rough estimate of ⋱
the time complexity as the number of inputs approaches 𝑎𝑛1 𝑎𝑛2 𝑎𝑛3 ⋯ 𝑎𝑛𝑛
𝑎22 𝑎23 ⋯ 𝑎2𝑛
infinite. The asymptotic time complexity is commonly
= 𝑎11 | ⋮ ⋮ ⋱ ⋮ |
denoted with the Big-O notation, though other notations 𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛𝑛
exist. Generally, the asymptotic time complexity of an 𝑎21 𝑎23 ⋯ 𝑎2𝑛
algorithm can be taken from the most significant term in − 𝑎12 | ⋮ ⋮ ⋱ ⋮ |+⋯
the time complexity function. For example, 𝑎𝑛2 𝑎𝑛2 ⋯ 𝑎𝑛𝑛
T(𝑛) = 192𝑛5 + 2𝑛 + log 𝑛! = O(2𝑛 ) 𝑎21 𝑎22 ⋯ 𝑎2(𝑛−1)
because for non-negative integer values of 𝑛, 2𝑛 ± 𝑎1𝑛 | ⋮ ⋮ ⋱ ⋮ |
contributes the most to the function T(𝑛). 𝑎𝑛1 𝑎𝑛2 ⋯ 𝑎𝑛(𝑛−1)
Table I shows categories of algorithm based on its Big-
O notation. Finding the determinant of a 3×3 matrix using
expansion by minors can be illustrated with the following
Table I. Algorithm categories based on asymptotic time
complexity, ordered from smallest to largest
example.

Complexity Category Example 2. Find det(A) using expansion by minors, where

O(1) constant 1 3 5
O(log 𝑛) logarithmic 𝐴 = [0 5 1].
O(𝑛) linear 6 5 0
O(𝑛 log 𝑛) 𝑛 log 𝑛
O(𝑛2 ) quadratic Following the above definition, the matrix A can be
O(𝑛3 ) cubic expanded to minor matrices:
O(2𝑛 ) exponential 5 1 0 1 0 5
det(𝐴) = 1 | | − 3| | + 5| |
5 0 6 0 6 5
O(𝑛!) factorial
= 1×(−5) − 3×(−6) + 5×(−30)
= −137
The top six (O(1) to O(𝑛3 )) are called polynomial Determinant expansion by minors is the simplest method
algorithms, while O(2𝑛 ) and O(𝑛!) are called exponential among the three and is commonly taught in class. A
algorithms. Exponential algorithms grow much faster than derivation of determinant expansion by minors exclusive
polynomial algorithms. For example, if 𝑛 = 100, then to 3×3 matrices, called the Sarrus method, is available,
𝑛3 = 106 , whereas 2𝑛 = 1.268×1030 and 𝑛! = 9.333× although the method cannot be used for larger matrices.
10157 .
B. LU Decomposition
LU decomposition is a procedure for decomposing a
III. MATHEMATICAL CONCEPTS OF DETERMINANT
𝑛×𝑛 matrix into a product of a lower triangular matrix L
FINDING ALGORITHMS and an upper triangular matrix U.
A. Determinant Expansion by Minors 𝐿𝑈 = 𝐴
Also known as the Laplace Expansion, expansion by For a 3×3 matrix, the LU decomposition is as the
minors is a technique to find the determinant of a given following.
square matrix. Although sufficiently efficient for small 𝑙11 0 0 𝑢11 𝑢12 𝑢13 𝑎11 𝑎12 𝑎13
matrices, other techniques detailed later are much more [𝑙21 𝑙32 0 ] [ 0 𝑢22 𝑢23 ] = [𝑎21 𝑎22 𝑎23 ]
𝑙31 𝑙32 𝑙33 0 0 𝑢33 𝑎31 𝑎32 𝑎33
efficient for very large matrices.
Formally, expansion by minors is defined by Intuitively, LU decomposition can be performed by
𝑛 applying Gauss elimination, where matrix U is the
det(𝐴) = ∑(−1)𝑖+𝑗 𝑎𝑖𝑗 𝑀𝑖𝑗 reduction of matrix A to an upper triangular matrix and
𝑖=1 matrix L is the multipliers used in each elementary row
where 𝑀𝑖𝑗 is the i, j minor matrix of A: the determinant of operation.
the (𝑛 − 1)×(𝑛 − 1) matrix obtained by deleting the i-th More rigidly, let A be a 𝑛×𝑛 matrix. First, copy matrix
row and the j-th column of A. A to matrix U. Iterations denoted by i and j process every
element of the matrix, where 𝑖 = [1. . 𝑛] and 𝑗 = [(𝑖 +
1). . 𝑛],
𝑢𝑗𝑖
𝑙𝑖𝑗 =
𝑢𝑖𝑖
and
Figure 1. Obtaining minor matrices from a larger main matrix 𝑢𝑗𝑘 = 𝑢𝑗𝑘 − 𝑙𝑖𝑗 ×𝑢𝑖𝑘

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

where 𝑘 ∈ [1. . 𝑛].
For calculating determinants, properties 4 and 5 Example 4. Find det(A) using the Bareiss algorithm, where
discussed in Section II-1 are used, where det(𝐴) = 1 3 5
det(𝐿) × det(𝑈) and the determinants of L and U are the 𝐴 = [0 5 1].
product of their diagonals. 6 5 0

Example 3. Find det(A) using LU decomposition, where Following the algorithm denoted above, we begin by
1 3 5 defining 𝑎00 = 1. For the 1st iteration (𝑘 = 1), we alter
𝐴 = [0 5 1]. 𝑎22 , 𝑎23 , 𝑎32 , and 𝑎33 . For 𝑖 = 2 and 𝑗 = 2, we have
6 5 0 (2} 1×5 − 3×0
𝑎22 = = 5.
1
Using Gauss elimination, matrices L and U can be found Continuing the process for the remaining elements gives
1 0 0 1 3 5 us
to be 𝐿 = [ 0 1 0 ] and 𝑈 = [ 0 5 1 ]. 1 3 5
6 −
13
1 0 0 −
137 𝐴(2) = [0 5 1 ].
5 5
0 −13 −30
To check if L and U are correct, simply multiply L with U For 𝑘 = 2, only 𝑎33 is changed:
and check if the product matrix is equal to A. 5×(−30) − 1×(−13)
(3}
After obtaining L and U, find their determinants by 𝑎33 = = −137,
1
multiplying their diagonals: giving
det(𝐿) = 1×1×1 = 1 1 3 5
137 𝐴(3) = [0 5 1 ].
det(𝑈) = 1×5× (− ) = −137
5 0 −13 −137
Then, calculate the determinant of A by multiplying the (3)
Thus, det(𝐴) = 𝑎33 = −137.
determinants of L and U:
det(𝐴) = det(𝐿) × det(𝑈) = 1×(−137) = −137 As with LU decomposition, division by zero is possible
without a proper ordering. Before inputting the matrix into
Without a proper ordering, the decomposition may fail the Bareiss algorithm, swap rows whose pivots are 0, then
as a division by 0 occurs somewhere in the decomposition multiply it by -1.
process and mistakenly imply that matrix A is singular. To
rectify this, if pivot 𝑎𝑖𝑖 = 0 for 𝑖 ∈ [1. . 𝑛], simply swap
row i with another row j where 𝑎𝑗𝑖 ≠ 0, then multiply the IV. IMPLEMENTING DETERMINANT FINDING
entire row by -1 to preserve the determinant value. If this ALGORITHMS IN PROGRAMS
is impossible (a column is composed entirely of 0s), then
the matrix is singular and det(𝐴) = 0. Note that the snippets in this section assumes that the
In practice, because the determinant of L is always 1, indices of the matrix start from 1. If the snippets are
det(𝐴) = det(𝑈). Because of this, in algorithms to implemented in languages whose indices start from 0 (such
calculate determinants using LU decomposition (including as C), simply decrease iterators by 1.
the one in this paper), the matrix L is often not computed
alongside matrix U and the multipliers used in each A. Forming Minor Matrices
elementary row operation is discarded after every iteration. The following pseudocode snippet is used to form the
minor matrix of a given larger matrix. The function
C. Bareiss Algorithm receives the main matrix and integers i and j, which are the
The Bareiss algorithm, named after Erwin Bareiss, is an respectively, the rows and columns to cross out, and returns
algorithm to calculate the determinant or the echelon form the minor matrix formed.
of an integer matrix using only integer arithmetic; that is,
any divisions performed are exact (there is no remainder).
The method is also used to compute the determinant of a
real number matrix and avoids the introduction of rounding
errors not present in the input matrix.
Let A be a 𝑛×𝑛 matrix. For every iteration denoted by
𝑘 ∈ [1. . (𝑛 − 1)], every element in the matrix is processed
with the following formula:
(𝑘−1) (𝑘−1)
(𝑘+1) 1 𝑎𝑘𝑘 𝑎𝑘𝑗
𝑎𝑖𝑗 = | (𝑘−1) (𝑘−1)
|
𝑎(𝑘−1)(𝑘−1) 𝑎 𝑎𝑖𝑗
𝑖𝑘
where 𝑎00 = 1, 𝑖 ∈ [(𝑘 + 1). . 𝑛], and 𝑗 ∈ [(𝑘 + 1). . 𝑛].
(𝑛)
The determinant is element 𝑎𝑛𝑛 ; that is, the element in the
lower right corner after the last iteration is completed.

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

function MinorMatrix (M: matrix, input i, check if any of the matrix’ pivots are 0. If there are, it then
j: integer) → matrix searches the column where the offending pivot is for a non-
DICTIONARY
minor: matrix
zero value. If found, the code then swaps the row where the
n, a, b, c, d: integer non-zero value is found with the offending row. Otherwise,
ALGORITHM if all values of a given column is zero, the matrix is singular
n ← NRow(M) and the code terminates.
c ← 1
i traversal [1..n] { Traverse rows } C. Laplace Expansion
if (a ≠ i) then { Skip row i }
d ← 1 The following pseudocode snippet is used to calculate
j traversal [1..n] { Traverse columns } the determinant of the inputted matrix through Laplace
if (b ≠ j) then { Skip column j } expansion recursively. The function receives the matrix
minor[c][d] ← M[a][b] whose determinant shall be calculated and an integer n,
d ← d + 1 which represents the number of rows or columns in the
c ← c + 1
→ minor matrix, and then returns the determinant of the matrix.

function DetLaplace (M: matrix, n: integer)

The code snippet above traverses the main matrix and → infotype
copies its values, but skips row i and column j. It first sets DICTIONARY
the minor row iterator to 1, then traverses the row of the det: infotype
main matrix. If the loop is not on row i, it resets the minor minor: matrix
column iterator to 1, then traverses the column of the main i, cofactor: integer
ALGORITHM
matrix. If the loop is not on column j, it copies the value if (n = 1) then { Basis, single element matrix }
from the main matrix to the minor matrix, then increment det ← M[1][1]
the minor column iterator. After traversing the column, the else { Recurrence }
minor row iterator is incremented. The resultant minor det ← 0 { Initialize determinant value }
matrix is then returned. cofactor ← -1 { Initialize cofactor }
i traversal [1..n] { Traverse rows }
B. Swapping Rows Whose Pivots are 0 cofactor ← -cofactor { Alternate cofactor }
minor ← MinorMatrix(M,1,i)
Before implementing LU decomposition and/or Bareiss { Add determinant of current submatrix }
algorithm in programs, rows whose pivots are 0 must first det ← det + cofactor * M[1,i] *
be swapped in order to avoid a divide by 0 problem. DetLaplace(minor,n-1)
The following pseudocode snippet describes the → det
algorithm to achieve this. The procedure receives matrix M
as input, and returns the changed matrix as well as well as The basis of the recursive function is that if the matrix
a Boolean value denoting whether the matrix is singular or only has a single element, that element is returned as the
not. determinant.
In the recurrence of the function, the determinant is first
procedure SwapRowsWith0Pivot (input/output initialized as 0 and the cofactor as -1. It then traverses the
M: matrix, output singular: boolean) column of the matrix by first negating the cofactor, forming
DICTIONARY the minor matrix, and finally adding the current value of
n, i, j, k: integer the determinant with the product of cofactor, the iterated
temp: infotype
ALGORITHM
element, and the value returned by the Laplace expansion
n ← NRow(M) of the minor matrix. The resultant determinant of the main
singular ← false matrix is then returned.
i ← 1
{ Search for 0 pivots } D. LU Decomposition
while ((i ≤ n) and not(singular)) do
if (M[i][i] = 0) then The following pseudocode snippet is used to calculate
j ← 1 the determinant of the inputted matrix through LU
{ Search for swappable rows } decomposition iteratively. The function receives the matrix
while ((j < n) and (M[j][i] = 0)) do whose determinant shall be calculated and then returns the
j ← j + 1
determinant of the matrix.
if (M[j][i] ≠ 0) then { Swap rows }
k traversal [1..n] The code snippet below differs from the mathematical
temp ← M[i][k] concept previously described in section II. In the concept,
M[i][k] ← M[j][k] the ratios are stored in the matrix L, whereas in the code
M[j][k] ← -temp below, the ratio is single-use; it is only used for that
else particular iteration. This is because, in practice, the
singular ← true
determinant of the matrix L formed through the LU
decomposition method described in the concept is almost
The code snippet above traverses the main diagonal to

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

always 1, which makes det(𝐴) = det(𝑈) and renders
calculating L unnecessary. function DetBareiss (M: matrix) → infotype
DICTIONARY
function DetLU (M: matrix) → real pivot: infotype
DICTIONARY n, i, j, k: integer
det, ratio: real singular: boolean
n, i, j, k: integer ALGORITHM
singular: boolean SwapRowsWith0Pivot(M,singular)
ALGORITHM if (singular) then { Singular matrix }
SwapRowsWith0Pivot(M,singular) det ← 0
if (singular) then { Singular matrix } else { Nonsingular matrix }
det ← 0 n ← NRow(M)
else { Nonsingular matrix } pivot ← 1
n ← NRow(M) k traversal [1..(n-1)] { Traverse pivots }
i traversal [1..n] { Traverse columns } i traversal [(k+1)..n] { Traverse rows }
j traversal [(i+1)..n] { Traverse rows } j traversal [(k+1)..n] {Traverse columns}
ratio ← M[j][i]/M[i][i] { Apply formula }
M[i][j] ← M[k][k] * M[i][j] –
k traversal [1..n] { Subtract elements }
M[i][k] * M[k][j]
M[j][k] ← M[j][k] - ratio *
M[i][j] ← M[i][j]/pivot
M[i][k]
det ← 1 pivot ← M[k][k] { Set next pivot }
i traversal [1..n] { Multiply pivots } det ← M[n][n] { Assign determinant }
det ← det * M[i][i] → det
→ det
Before going to the actual part of LU decomposition, the
The code snippet above can be divided to two parts: code first calls SwapRowsWith0Pivot to transform the
transforming the matrix to an upper triangular form and matrix so that there are no zeros in the pivot. If the function
calculating the determinant itself. fails, the matrix is singular and its determinant is zero.
Before going to the actual part of LU decomposition, the Otherwise, the code continues.
code first calls SwapRowsWith0Pivot to transform the First, pivot is initialized to 1. In accordance to the
matrix so that there are no zeros in the pivot. If the function Bareiss algorithm described in the concept, the code
fails, the matrix is singular and its determinant is zero. traverses the main diagonal of the matrix, then transforms
Otherwise, the code continues. every element to the bottom right of the traversed element
The code then traverses the elements below the main through the formula previously described. pivot is then
diagonal. It first calculates the ratio needed to gradually updated to the traversed diagonal element. The determinant
zero out elements in the bottom, then traverses the column is the lower-rightmost element of the matrix after the
while subtracting the traversed elements. At the end of the algorithm.
iterations, the matrix would be in an upper triangular form.
In a triangular form, the determinant is easily calculated
as the product of the matrix’ pivot. V. ANALYSIS AND COMPARISON
A. Asymptotic Time Complexity Analysis
E. Bareiss Algorithm
The following analyses assume that all basic arithmetic
The following pseudocode snippet is used to calculate
operations, assignment, calls, etc. all run in O(1). All time
the determinant of the inputted matrix through the Bareiss
complexities calculated are worst-case scenarios.
algorithm iteratively. The function receives the matrix
whose determinant shall be calculated and then returns the
For the minor-matrices-forming algorithm, the
determinant of the matrix.
asymptotic time complexity is as follows.
The code snippet below differs from the mathematical
 Outer loop (row traversal): O(𝑛)
concept previously described in section II. In the concept,
the elements are divided with the diagonal element of the  Inner loop (column traversal): O(𝑛)
previous iteration, whereas in the code below, the variable Therefore, the asymptotic time complexity of the algorithm
pivot is introduced and used as the divisor. The value of
is O(𝑛×𝑛) = O(𝑛2 ).
pivot starts at 1 and is continually updated in each
For the row-swapping algorithm, the asymptotic time
iteration as the diagonal element of the previous iteration.
complexity is as follows.
This is done because in most programming languages,
adding M[0][0] is unfeasible. If indices start with 1,  Outer loop (search for 0 pivots): O(𝑛)
defining M[0][0] would take a considerable amount of  1st inner loop (search for swappable row): O(𝑛)
space since, in effect, an entire row and column must be  2nd inner loop (swap rows): O(𝑛)
added. On the other hand, if indices start with 0, the value Therefore, the asymptotic time complexity of the algorithm
of M[0][0] is occupied already. is O(𝑛×max(𝑛, 𝑛)) = O(𝑛2 ).

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

 For the Laplace expansion algorithm, the asymptotic in a real number matrix, the division will not significantly
time complexity is as follows. change the length of the mantissa.
 Loop (row traversal): O(𝑛) In conclusion, for arbitrarily large matrices, the Bareiss
 Minor matrix forming: O(𝑛2 ) expansion is slightly superior to the LU decomposition and
 Recursion: O((𝑛 − 1)!) both the Bareiss algorithm and LU decomposition are
Therefore, the asymptotic time complexity of the algorithm vastly superior to Laplace expansion.
is O(𝑛×max(𝑛2 , (𝑛 − 1)!)) = O(𝑛!).

For LU decomposition, the asymptotic time complexity VI. CONCLUSION

is as follows. For arbitrarily large matrices, the Bareiss expansion is
 Row swapping: O(𝑛2 ) slightly superior to the LU decomposition and both the
 1st loop i (column traversal): O(𝑛) Bareiss algorithm and LU decomposition are vastly
 Loop j (row traversal): O(𝑛) superior to Laplace expansion. The Laplace expansion is
 Loop k (subtracting elements): O(𝑛) superior if and only if the size of the matrix does not exceed
 2nd loop i (multiplying pivots): O(𝑛) 5×5—even then, the difference is only notable if the
Therefore, the asymptotic time complexity of the algorithm algorithm is applied on multiple matrices.
is O(max(𝑛2 , 𝑛×𝑛×𝑛, 𝑛) = O(𝑛3 ). Besides the algorithms elaborated in this paper, there are
also algorithms to find determinants using fast matrix
For the Bareiss algorithm, the asymptotic time multiplication (Strassen algorithm with O(𝑛2.807 ) and
complexity is as follows. Coppersmith–Winograd algorithm with O(𝑛2.376 )), which
 Row swapping: O(𝑛2 ) are theoretically better but use heavy mathematical
 Loop i (pivot traversal): O(𝑛) calculations, thus rendering it impractical in most cases.
 Loop j (row traversal): O(𝑛) LU decomposition and the Bareiss algorithm, although
 Loop k (column): O(𝑛) theoretically worse with O(𝑛3 ) complexity, does not use
Therefore, the asymptotic time complexity of the algorithm any mathematical calculations more complex than
is O(max(𝑛2 , 𝑛×𝑛×𝑛) = O(𝑛3 ). division, making it more practical for all but the most
sophisticated machines to use.
B. Comparison Besides real and integer matrices, the aforementioned
algorithms can also be expanded to cover complex number
Because the Laplace expansion runs in O(𝑛!), Laplace
or even quaternion matrices, with the resulting determinant
expansion is only faster than the other two algorithms if the
being a complex number or quaternion itself.
matrix is at most 5×5—at which the difference is too
minute to have any significant impact to running time
unless the algorithm is performed consecutively on
VII. ACKNOWLEDGMENT
multiple matrices. For even moderately sized matrices, it is
significantly outperformed by both the LU decomposition We thank God for His Blessing that enables this paper
and the Bareiss algorithm. to be completed on schedule. We also thank Dr. Ir. Rinaldi
At a glance, LU decomposition and the Bareiss Munir, M.T. and Dra. Harlili, M.Sc. as the lecturer of
algorithm performs the same—their asymptotic time IF2121 Discrete Mathematics. We then thank our parent
complexities are both O(𝑛3 ). Performance-wise, they are for granting us both material and moral support and
the same, but LU decomposition has a weakness that makes guidance in the making of this paper. Finally, we thank our
the Bareiss algorithm better than LU decomposition. classmates for helping us in class, giving us ideas for this
LU decomposition has a weakness in that the ratio paper, and giving us moral support.
needed to transform the matrix to an upper triangular form
is not necessarily an integer. Meaning, if the determinant
of an integer matrix is to be found using LU REFERENCES
decomposition, the resultant upper triangular matrix will [1] Aho, A.V., J.E. Hopcroft, and J.D. Ullman, The Design and Analysis
most likely be converted to a real number matrix. of Computer Algorithms. Boston, MA: Addison-Wesley Longman,
Furthermore, finding the determinant of a real number 1974, ch. 6.
[2] Bareiss, E.H., “Sylvester’s identity and multistep integer-preserving
matrix is subject to rounding errors due to limitations of Gaussian elimination,” Math. Comp. 22, 1968.
information representation, making the resulting [3] Jones, J.. (accessed 2016, Dec 3). The Determinant of a Square
determinant slightly less accurate. Matrix [Online]. Available:
Neither the Laplace expansion nor the Bareiss algorithm https://people.richland.edu/james/lecture/m116/matrices/determina
nt.html.
have the weakness mentioned above; they both preserve [4] Leggett, D.R, “Fraction-Free Methods for Determinants,” M.Sc.
the identity of the info type. The Laplace expansion does thesis, Dept. Math., Univ. Southern Mississippi, Hattiesburg, MS,
not use division in its process. The Bareiss algorithm does 2011.
[5] Liem, I., Draft Diktat Kuliah Dasar Pemrograman (Bagian
have division, but it is guaranteed to be exact; that is, in an Pemrograman Prosedural). unpublished.
integer matrix, the division will have no remainder, while

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017

[6] Munir, R., Matematika Diskrit, Ed. 3. Bandung: Teknik Informatika
ITB, 2006, ch. 10.
[7] Strang, G., Introduction to Linear Algebra, 5th ed. Wellesey:
Wellesey-Cambridge Press, 2016, ch. 1.
[8] Weisstein, E.W.. (accessed 2016, Dec 3). Determinant [Online].
Available: http://mathworld.wolfram.com/Determinant.html.
[9] Weisstein, E.W.. (accessed 2016, Dec 3). Determinant Expansion
by Minors [Online]. Available:
http://mathworld.wolfram.com/DeterminantExpansionbyMinors.ht
ml.
[10] Weisstein, E.W.. (accessed 2016, Dec 3). LU Decomposition
[Online]. Available:
http://mathworld.wolfram.com/LUDecomposition.html.
[11] anonymous. (accessed 2016, Dec 3). Elementary Matrix Operations
[Online]. Available: http://stattrek.com/matrix-algebra/elementary-
operations.aspx.
[12] anonymous. (accessed 2016, Dec 4). Fastest algorithm for
computing the determinant of a matrix? [Online]. Available:
https://stackoverflow.com/questions/27003062/fastest-algorithm-
for-computing-the-determinant-of-a-matrix.
[13] anonymous. (accessed 2016, Dec 3). Lecture 12 – LU
Decomposition [Online]. Available:
http://www.math.ohiou.edu/courses/math3600/lecture12.pdf.

PERNYATAAN
Dengan ini saya menyatakan bahwa makalah yang saya
tulis ini adalah tulisan saya sendiri, bukan saduran, atau
terjemahan dari makalah orang lain, dan bukan plagiasi.

Bandung, 8 Desember 2016

Felix Limanta 13515065

Makalah IF2120 Matematika Diskrit – Sem. I Tahun 2016/2017