-4
$\begingroup$

Are there efficient algorithms for calculating determinants of matrices?

$\endgroup$

closed as off-topic by Shailesh, Namaste, Delta-u, José Carlos Santos, Strants Jul 20 '18 at 14:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Shailesh, Namaste, Delta-u, Strants
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ LU decomposition. $\endgroup$ – copper.hat Jul 20 '18 at 2:11
  • 2
    $\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$ – воитель 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$
1
$\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.