Efficient algorithm for calculating determinants

Question

Are there efficient algorithms for calculating determinants of matrices?

Answer 1

You can perform a slight variation of Gauss elimination on the determinant to bring it into row echelon form.

• adding a scalar multiple of a row to another row will not change the value of the determinant, because the determinant is linear in its arguments (here: row vectors) and because it is alternating: two equal arguments will make it vanish (here: the addition)
• switching rows will flip the sign of the value of the determinant, because it is an alternating form

Laplace expansion along colums then has only contributions at the diagonal positions.

This lowers the complexity for a $n\times n$ matrix from $O(n!)$ for the Leibniz formula or Laplace expansion to $O(n^3)$ for Gauss elimination.

Answer 2

Suppose I have a square matrix $A \in \mathbb{C}^{n \times n} $

now

$$A = LU $$

in general the determinant takes $ \mathcal{O}(n!)$

instead $$det(A) = det(LU) = det(L)det(U) $$ to calculate this

$$ det(A) = \prod_{i=1}^{n} l_{ii} \prod_{i=1}^{n} u_{ii} $$

however if the numerical stability is in question you could use the QR decomp

$$ A = QR$$ $$ det(A) = det(QR) = det(Q)det(R) $$ the determinant of $Q$ is 1 as it is orthogonal

$$ det(A) = \prod_{i=1}^{n} r_{ii}$$

now if the matrix is positive definite hermitian we can use the cholesky decomp

$$ A = R^{*}R$$ $$ det(A) = det(R^{*}R) = det(R^{*})det(R)$$ $$ det(A) = \prod_{i=1}^{n} r_{ii}^{*} \prod_{i=1}^{n} r_{ii}$$

There is also an algorithm called the Bareiss algorithm which has $\mathcal{O}(n^{2})$ time complexity for Toeplitz matrices.