The Determinant¶
The determinant of a square matrix \(A\) is a number, written \(\det(A)\), that is important in theory and application. For instance, \(A\) is invertible if and only if \(\det(A) \neq 0\).
The determinant of a \(1 \times 1\) matrix is the only entry of that matrix: \(\det([a]) = a\).
The determinant of a \(2 \times 2\) matrix is
The determinant of an \(n \times n\) matrix can be defined recursively from the determinants of smaller matrices. For an \(n \times n\) matrix \(A\) with entries \(a_{ij}\), let \(A_{1j}\) denote the \((n - 1) \times (n - 1)\) submatrix obtained by deleting row \(1\) and column \(j\) of \(A\). The determinant of \(A\) is defined recursively by expanding along the top row:
The signs alternate \(+, -, +, \ldots\) across the top row. Each submatrix \(A_{1j}\) is one size smaller than \(A\), so the recursion eventually reaches the \(2 \times 2\) case. For example,
Computing \(A_{1j}\) with NumPy requires removing a row and a column from an array.
The function np.delete(A, i, axis) returns a copy of A with row i removed (axis=0) or column i removed (axis=1), leaving A unchanged.
import numpy as np
A = np.array([
[1, 2, 3],
[4, 5, 6],
[7, 8, 10],
])
print(np.delete(A, 0, axis=0)) # Delete the first row.
print(np.delete(A, 1, axis=1)) # Delete the second column.
print(A) # A is unchanged.
[[ 4 5 6]
[ 7 8 10]]
[[ 1 3]
[ 4 6]
[ 7 10]]
[[ 1 2 3]
[ 4 5 6]
[ 7 8 10]]
Problem 5
Write a function named det() that accepts an \(n \times n\) matrix \(A\). Compute \(\det(A)\) recursively using the formula
where \(A_{ij}\) is the \((n - 1) \times (n - 1)\) matrix obtained by removing row \(i\) and column \(j\) from \(A\).
Test Cases
# 1 x 1 matrix.
A = np.array([
[18],
])
print(det(A))
# 2 x 2 matrix.
A = np.array([
[3, 1],
[4, 2],
])
print(det(A))
# 3 x 3 matrix.
A = np.array([
[1, 2, 3],
[4, 5, 6],
[7, 8, 10],
])
print(det(A))
# 4 x 4 matrix.
A = np.array([
[2, 0, 1, 3],
[1, 4, -1, 0],
[0, 2, 5, 1],
[3, 1, 0, 2],
])
print(det(A))
18
2
-3
-82
Determinants in Practice
Cofactor expansion of an \(n \times n\) matrix makes \(n\) recursive calls on matrices of size \(n - 1\), so its operation count grows on the order of \(n!\). For a \(20 \times 20\) matrix, this is \(20! \approx 2.4 \times 10^{18}\).
Instead of this approach, numerical software typically uses PLU decomposition: if \(PA = LU\), then \(\det(A) = \pm u_{11} u_{22} \cdots u_{nn}\), and the decomposition takes on the order of \(n^3\) operations.
This is the strategy that scipy.linalg.det() uses.