Computing determinants from matrix decompositions

| categories: linear algebra | tags: | View Comments

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.

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)
24.0
24.0

According to the numpy documentation, a method similar to this is used to compute the determinant.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

blog comments powered by Disqus