What is the best algorithm to find a determinant of a matrix?
Can anyone tell me which is the best algorithm开发者_JAVA百科 to find the value of determinant of a matrix of size N x N
?
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.
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
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.
If B is a matrix obtained by swapping two rows of A, then
det(B) = -det(A)
- If you swap rows, flip the sign.
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
If you did an initial research, you've probably found that with N>=4, calculation of a matrix determinant becomes quite complex. Regarding algorithms, I would point you to Wikipedia article on Matrix determinants, specifically the "Algorithmic Implementation" section.
From my own experience, you can easily find a LU or QR decomposition algorithm in existing matrix libraries such as Alglib. The algorithm itself is not quite simple though.
I am not too familiar with LU factorization, but I know that in order to get either L or U, you need to make the initial matrix triangular (either upper triangular for U or lower triangular for L). However, once you get the matrix in triangular form for some nxn matrix A and assuming the only operation your code uses is Rb - k*Ra, you can just solve det(A) = Π T(i,i) from i=0 to n (i.e. det(A) = T(0,0) x T(1,1) x ... x T(n,n)) for the triangular matrix T. Check this link to see what I'm talking about. http://matrix.reshish.com/determinant.php
精彩评论