Cofactors and LU Decomposition
The determinant
of a 2\times 2 matrix is easy. For bigger matrices you need a system —
and the two classic tools point in opposite directions. Cofactor expansion is the
elegant, recursive definition of the determinant; LU decomposition is the
fast, practical way a computer actually solves linear systems. This page teaches both, and when to
reach for each.
Cofactor expansion
To find a determinant, pick any row (or column) and expand along it. For each entry
a_{ij}, delete its row and column to get a smaller minor
M_{ij}, attach the checkerboard sign, and add up:
\det A = \sum_{j} a_{ij}\,C_{ij}, \qquad C_{ij} = (-1)^{i+j} M_{ij}.
The signs (-1)^{i+j} form a checkerboard
\begin{smallmatrix}+&-&+\\-&+&-\\+&-&+\end{smallmatrix}.
Expanding the 3\times 3 matrix along its top row:
\det\begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 1 & 0 & 6 \end{bmatrix} = 1\begin{vmatrix}4&5\\0&6\end{vmatrix} - 2\begin{vmatrix}0&5\\1&6\end{vmatrix} + 3\begin{vmatrix}0&4\\1&0\end{vmatrix} = 1(24) - 2(-5) + 3(-4) = 22.
It is exact and wonderful for proofs — but expanding an n\times n
determinant this way costs about n! multiplications. For a
20\times 20 matrix that's astronomically slow. So we compute
determinants a different way in practice: by elimination.
LU decomposition
Gaussian elimination turns a matrix into an upper-triangular U by
subtracting multiples of one row from those below. If you record those multipliers in a
lower-triangular L (with 1s on its diagonal),
you have factored the matrix as
A = L\,U, \qquad L \text{ lower-triangular}, \quad U \text{ upper-triangular}.
Watch the elimination build L and U — press Run:
type Matrix = number[][];
function lu(A: Matrix): { L: Matrix; U: Matrix } {
const n = A.length;
const U: Matrix = A.map((row) => [...row]); // copy; becomes upper-triangular
const L: Matrix = A.map((_, i) => A.map((_, j) => (i === j ? 1 : 0))); // identity
for (let k = 0; k < n; k++) {
for (let i = k + 1; i < n; i++) {
const m = U[i][k] / U[k][k]; // the multiplier to zero out U[i][k]
L[i][k] = m; // remember it in L
for (let j = k; j < n; j++) U[i][j] -= m * U[k][j];
}
}
return { L, U };
}
const A: Matrix = [
[2, 1, 1],
[4, 3, 3],
[8, 7, 9],
];
const { L, U } = lu(A);
console.log("L =", JSON.stringify(L));
console.log("U =", JSON.stringify(U));
// The determinant falls out for free: product of U's diagonal.
const det = U[0][0] * U[1][1] * U[2][2];
console.log("det A =", det);
Once you have A = LU, solving A\mathbf{x} = \mathbf{b}
is two easy triangular solves: forward-substitute
L\mathbf{y} = \mathbf{b}, then back-substitute
U\mathbf{x} = \mathbf{y}. And the determinant is just the product of
U's diagonal — because the determinant of a triangular matrix is the
product of its diagonal, and \det L = 1.
- Cofactor expansion:
\det A = \sum_j a_{ij}(-1)^{i+j}M_{ij} — exact, but
O(n!).
- LU decomposition: A = LU via elimination — solve
systems and get \det A in O(n^3).
- The determinant of a triangular matrix is the product of its diagonal.
You rarely want A^{-1} itself — you want to solve
A\mathbf{x} = \mathbf{b}, often for many different
\mathbf{b}. Computing the inverse and multiplying is slower and less
numerically stable than doing the elimination once as A = LU and reusing
that factorisation for every right-hand side with cheap triangular solves. It's why "never invert
the matrix" is a mantra in numerical computing — factor it instead.
-
Plain LU breaks if a pivot U[k][k] is zero (you'd
divide by zero). Real implementations swap rows first — partial pivoting —
giving PA = LU. It's also essential for numerical accuracy.
-
Don't use cofactor expansion for big determinants — its n! cost is
hopeless past small sizes. Use it for theory and 2\times2 /
3\times3 by hand; use elimination for everything else.