What is the best algorithm to find a determinant of a matrix?

Question

Can anyone tell me which is the best algorithm to find the value of determinant of a matrix of size N x N?

Answer 1

Row Reduction

The simplest way (and not a bad way, really) to find the determinant of an nxn matrix is by row reduction. By keeping in mind a few simple rules about determinants, we can solve in the form:

det(A) = α * det(R), where R is the row echelon form of the original matrix A, and α is some coefficient.

Finding the determinant of a matrix in row echelon form is really easy; you just find the product of the diagonal. Solving the determinant of the original matrix A then just boils down to calculating α as you find the row echelon form R.

What You Need to Know

What is row echelon form?

See this [link](http://stattrek.com/matrix-algebra/echelon-form.aspx) for a simple definition
**Note:** Not all definitions require 1s for the leading entries, and it is unnecessary for this algorithm.

You Can Find R Using Elementary Row Operations

Swapping rows, adding multiples of another row, etc.

You Derive α from Properties of Row Operations for Determinants

1. If B is a matrix obtained by multiplying a row of A by some non-zero constant ß, then

   det(B) = ß * det(A)

   • In other words, you can essentially 'factor out' a constant from a row by just pulling it out front of the determinant.

2. If B is a matrix obtained by swapping two rows of A, then

   det(B) = -det(A)

   • If you swap rows, flip the sign.

3. If B is a matrix obtained by adding a multiple of one row to another row in A, then

   det(B) = det(A)

   • The determinant doesn't change.

Note that you can find the determinant, in most cases, with only Rule 3 (when the diagonal of A has no zeros, I believe), and in all cases with only Rules 2 and 3. Rule 1 is helpful for humans doing math on paper, trying to avoid fractions.

Example

(I do unnecessary steps to demonstrate each rule more clearly)

   | 2  3  3  1 | A=| 0  4  3 -3 |   | 2 -1 -1 -3 |   | 0 -4 -3  2 | R2  R3, -α -> α (Rule 2)   | 2  3  3  1 |  -| 2 -1 -1 -3 |   | 0  4  3 -3 |   | 0 -4 -3  2 | R2 - R1 -> R2 (Rule 3)   | 2  3  3  1 |  -| 0 -4 -4 -4 |   | 0  4  3 -3 |   | 0 -4 -3  2 | R2/(-4) -> R2, -4α -> α (Rule 1)   | 2  3  3  1 |  4| 0  1  1  1 |   | 0  4  3 -3 |   | 0 -4 -3  2 | R3 - 4R2 -> R3, R4 + 4R2 -> R4 (Rule 3, applied twice)   | 2  3  3  1 |  4| 0  1  1  1 |   | 0  0 -1 -7 |   | 0  0  1  6 | R4 + R3 -> R3   | 2  3  3  1 |  4| 0  1  1  1 | = 4 ( 2 * 1 * -1 * -1 ) = 8   | 0  0 -1 -7 |   | 0  0  0 -1 | 

def echelon_form(A, size):     for i in range(size - 1):         for j in range(size - 1, i, -1):             if A[j][i] == 0:                 continue             else:                 try:                     req_ratio = A[j][i] / A[j - 1][i]                     # A[j] = A[j] - req_ratio*A[j-1]                 except ZeroDivisionError:                     # A[j], A[j-1] = A[j-1], A[j]                     for x in range(size):                         temp = A[j][x]                         A[j][x] = A[j-1][x]                         A[j-1][x] = temp                     continue                 for k in range(size):                     A[j][k] = A[j][k] - req_ratio * A[j - 1][k]     return A 

Answer 2

Here is an extensive discussion.

There are a lot of algorithms.

A simple one is to take the LU decomposition. Then, since

 det M = det LU = det L * det U 

and both L and U are triangular, the determinant is a product of the diagonal elements of L and U. That is O(n^3). There exist more efficient algorithms.