-4
$\begingroup$

Are there efficient algorithms for calculating determinants of matrices?

$\endgroup$
  • $\begingroup$ LU decomposition. $\endgroup$ – copper.hat Jul 20 '18 at 2:11
  • 3
    $\begingroup$ @copper.hat Take into account that LU is not the algorithm, but the output, which could be obtained by many algorithms. Algorithm would be Gauss elimination. $\endgroup$ – user574889 Jul 20 '18 at 2:17
  • $\begingroup$ @cactus: I am aware of that, thank you; the original purpose was a brief suggestion of direction rather than a complete answer. $\endgroup$ – copper.hat Jul 20 '18 at 3:24
  • $\begingroup$ Gaussian elimination is the LU decomp. $\endgroup$ – user3417 Jul 20 '18 at 16:07
  • $\begingroup$ It would be nice if you could add some context to your question (e.g. "because I want my computer to go fast!"). It is an interesting question, but won't get reopened unless you provide some context. $\endgroup$ – user1729 Sep 3 '18 at 10:14
0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.