bvd's blog

How to quickly calculate the determinant of a matrix?
By bvd, history, 8 years ago, In English

This is how I normally calculate the determinant of a matrix.

However, the complexity of this algorithm is O(n!).

How to calculate it in polynomial time?

P.S: Why I need to calculate the determinant of a matrix in polynomial time?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Your second link is one click away from an efficient algorithm, which is Gaussian elimination. See the bottom of determinant's properties.

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Gaussian elimination.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Please keep in mind that Gaussian is numerically unstable in general case. It is not a problem in Laplacian matrix, as it is diagonally dominant.

→ Reply