** Computing determinants from matrix decompositions
:PROPERTIES:
:categories: linear algebra
:date: 2013/04/01 19:57:29
:updated: 2013/04/02 08:18:25
:END:
[[index:LU decomposition,determinant]]
There are a few properties of a matrix that can make it easy to compute determinants.
1. The determinant of a triangular matrix is the product of the elements on the diagonal.
2. The determinant of a permutation matrix is (-1)**n where n is the number of permutations. Recall a permutation matrix is a matrix with a one in each row, and column, and zeros everywhere else.
3. The determinant of a product of matrices is equal to the product of the determinant of the matrices.
The LU decomposition computes three matrices such that $A = P L U$. Thus, $\det A = \det P \det L \det U$. $L$ and $U$ are triangular, so we just need to compute the product of the diagonals. $P$ is not triangular, but if the elements of the diagonal are not 1, they will be zero, and then there has been a swap. So we simply subtract the sum of the diagonal from the length of the diagonal and then subtract 1 to get the number of swaps.
#+BEGIN_SRC python
import numpy as np
from scipy.linalg import lu
A = np.array([[6, 2, 3],
[1, 1, 1],
[0, 4, 9]])
P, L, U = lu(A)
nswaps = len(np.diag(P)) - np.sum(np.diag(P)) - 1
detP = (-1)**nswaps
detL = np.prod(np.diag(L))
detU = np.prod(np.diag(U))
print detP * detL * detU
print np.linalg.det(A)
#+END_SRC
#+RESULTS:
: 24.0
: 24.0
According to the numpy documentation, a method similar to this is used to compute the determinant.