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

\[\begin{split} \det\left[\begin{array}{cc} a & b \\ c & d \end{array}\right] = ad - bc. \end{split}\]

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:

\[\begin{split} \begin{aligned} \det(A) &= \sum_{j=1}^{n} (-1)^{1+j} a_{1j} \det(A_{1j}) \\ &= a_{11}\det(A_{11}) - a_{12}\det(A_{12}) + \cdots + (-1)^{1+n} a_{1n}\det(A_{1n}). \end{aligned} \end{split}\]

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,

\[\begin{split} \begin{aligned} \det\left[\begin{array}{rrr} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{array}\right] &= 1 \det\left[\begin{array}{rr} 5 & 6 \\ 8 & 10 \end{array}\right] - 2 \det\left[\begin{array}{rr} 4 & 6 \\ 7 & 10 \end{array}\right] + 3 \det\left[\begin{array}{rr} 4 & 5 \\ 7 & 8 \end{array}\right] \\ &= 1(50 - 48) - 2(40 - 42) + 3(32 - 35) \\ &= 2 + 4 - 9 = -3. \end{aligned} \end{split}\]

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

\[\begin{split} \begin{aligned} \det(A) &= \sum_{j=1}^{n} (-1)^{1+j} a_{1j} \det(A_{1j}) \\ &= a_{11}\det(A_{11}) - a_{12}\det(A_{12}) + \cdots + (-1)^{1+n} a_{1n}\det(A_{1n}), \end{aligned} \end{split}\]

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.