Determinants by cofactor expansion

When you reach for it

Oriwa, Waimarie and Ruiha are in an engineering class sizing a small footbridge. Balancing the forces at the joints gives four equations in four unknown forces, and they want to know whether the system has exactly one solution. By What the determinant means the determinant is the factor by which a matrix scales volume, and nonzero means nothing is flattened and the system has exactly one solution; for 4 \times 4 that is stated below, proved later. They need a 4 \times 4 determinant.

Computing a determinant expanded 3 \times 3 determinants along a row: each entry times its minor M_{ij} (the determinant left after crossing out row i and column j), with the checkerboard sign (-1)^{i+j}. Here that move becomes the definition for every size, works along columns too, and meets its best uses and its limit.

The procedure

Day 1: the definition for any size

The cofactor of the entry in position (i, j) of an n \times n matrix A is its minor with the checkerboard sign attached:

The minor of an n \times n matrix is an (n - 1) \times (n - 1) determinant. For n = 4 the signs (-1)^{i+j} are

Every diagonal position is +, and the sign changes with each step along a row or down a column.

Definition. For a 1 \times 1 matrix, \det [a] = a. For n \geq 2,

This definition is recursive: an n \times n determinant is defined through (n-1) \times (n-1) ones, and so on down to 1 \times 1. It is not circular, because each step lowers the size. For n = 2 it gives a_{11}a_{22} - a_{12}a_{21}, and for n = 3 it is the row-1 expansion of Computing a determinant. That this number still measures signed volume, and is nonzero exactly when the matrix is invertible, is stated here and proved in Properties of determinants: row operations, products, transposes.

Theorem (expansion along any line). For every n \times n matrix A, every row i and every column j,

The proof for every row and column is long and is not given here (it is cleanest once Properties of determinants: row operations, products, transposes shows that a row swap changes the sign). Here is the proof for column 1 against row 1, by induction on n.

For n = 2 both give a_{11}a_{22} - a_{12}a_{21}. Suppose they agree for every (n-1) \times (n-1) matrix, n \geq 3. For i, j \geq 2 let D_{ij} be the determinant left when rows 1, i and columns 1, j are crossed out. Both expansions share a_{11}C_{11}. The other row-1 terms are (-1)^{1+j}a_{1j}M_{1j}, j \geq 2. The first column of the matrix behind M_{1j} holds a_{21}, \dots, a_{n1}, with a_{i1} in its row i - 1, so expanding down it (the induction hypothesis) gives M_{1j} = \sum_{i \geq 2} (-1)^{i} a_{i1} D_{ij}. The row-1 expansion is therefore

The other column-1 terms are (-1)^{i+1}a_{i1}M_{i1}, i \geq 2. The first row of the matrix behind M_{i1} holds a_{12}, \dots, a_{1n}, with a_{1j} in its column j - 1, and the definition expands along it: M_{i1} = \sum_{j \geq 2} (-1)^{j} a_{1j}D_{ij}. So the column-1 expansion is a_{11}C_{11} plus the same double sum with sign (-1)^{i+1+j}, the same sign.

In practice: pick the line with the most zeros. A zero entry contributes 0 \cdot C_{ij} = 0, so its cofactor is never needed. Inside each minor, choose afresh.

Day 2: triangular matrices, parameters and cost

A square matrix is upper triangular when every entry below the main diagonal is 0, and lower triangular when every entry above it is 0.

Theorem. The determinant of a triangular matrix is the product of its diagonal entries.

Proof. Take A upper triangular and expand down column 1. Its only possibly nonzero entry is a_{11}, in a + position, so \det A = a_{11}M_{11}. Crossing out row 1 and column 1 leaves an upper triangular matrix with diagonal a_{22}, \dots, a_{nn}. Expanding that one down its first column gives a_{22} times a smaller upper triangular determinant, and so on, until the last step leaves \det[a_{nn}] = a_{nn}. So \det A = a_{11}a_{22}\cdots a_{nn}. A lower triangular matrix is the same argument along row 1 each time. \square

So \det I_n = 1, and a 0 on the diagonal makes a triangular determinant 0.

A parameter. When some entries are a letter, expansion makes the determinant a polynomial in it, and its zeros are the values at which the matrix flattens space and the system stops having exactly one solution.

Cost. Expanding an n \times n matrix with no zeros gives n minors of size n - 1, each giving n - 1 of size n - 2, and so on: in the end a sum of n(n-1)\cdots 1 = n! products, each taking one entry from every row and every column. The factorial outgrows every power of n, so expansion suits small matrices, matrices with many zeros, and matrices holding a letter. For a large matrix of numbers, row reduction to triangular form needs roughly \tfrac{1}{3}n^3 multiplications; Properties of determinants: row operations, products, transposes explains why it works.

Worked examples

Boundaries

• Only a square matrix has a determinant, and expansion needs a whole row or a whole column, never the diagonal.
• The sign (-1)^{i+j} belongs to the position, and a minor of a minor uses positions in the smaller matrix.
• The triangular rule needs every entry on one side of the main diagonal to be 0. A matrix triangular about the other diagonal is not triangular; its determinant carries a sign that depends on n.
• The corner factoring of Example 6 needs a full block of zeros in one corner.
• Expansion is exact at any size, but costs n!.
• Stated without proof: the adjugate \operatorname{adj} A, whose (i, j) entry is C_{ji}, gives \displaystyle A^{-1} = \frac{1}{\det A}\operatorname{adj} A when \det A \neq 0. For n = 2 this is Inverse of a 2 by 2 matrix, and solving with it; for larger n it costs far more than Finding an inverse by row reducing A next to I.

Where this goes next

Properties of determinants: row operations, products, transposes uses this lesson to prove how row operations change a determinant and that \det(AB) = \det A \det B, then computes large determinants by reducing to triangular form. Expanding \det(A - \lambda I) gives the polynomial of The characteristic equation and finding eigenvalues, the parameter problems of Day 2 in their most important form. Cramer's rule writes the solution of a system in determinants.

Exercises

Day 1: cofactors and 4 by 4 determinants

1. For A = \begin{bmatrix} 2 & -1 & 0 & 3 \\ 4 & 1 & 2 & 0 \\ 0 & 5 & -2 & 1 \\ 1 & 0 & 3 & 2 \end{bmatrix}, find the cofactors C_{23} and C_{41}.
2. Give the sign (-1)^{i+j} of positions (3, 4), (5, 2) and (4, 4) in a 5 \times 5 matrix.
3. \begin{vmatrix} 1 & 0 & 2 & 0 \\ 3 & -1 & 0 & 4 \\ 0 & 0 & 5 & 0 \\ 2 & 1 & 0 & 3 \end{vmatrix}
4. \begin{vmatrix} 0 & 2 & 0 & 0 \\ 1 & 3 & -2 & 4 \\ 5 & 1 & 0 & 2 \\ 0 & -1 & 0 & 3 \end{vmatrix}
5. \begin{vmatrix} 2 & 1 & 0 & -1 \\ 0 & 3 & 0 & 2 \\ 1 & 0 & 4 & 0 \\ 3 & 2 & 0 & 1 \end{vmatrix}
6. Find \begin{vmatrix} 1 & 2 & 0 & 3 \\ 0 & 1 & 4 & 0 \\ 2 & 0 & 1 & 1 \\ 1 & 0 & 0 & 2 \end{vmatrix} twice: along row 4 and down column 2.
7. Does the system with coefficient matrix \begin{bmatrix} 1 & 2 & 0 & 1 \\ 0 & 1 & 3 & 0 \\ 2 & 0 & 1 & 0 \\ 1 & 1 & 0 & 2 \end{bmatrix} have exactly one solution?

Day 1: 5 by 5 determinants

8. \begin{vmatrix} 2 & 0 & 0 & 0 & 1 \\ 0 & 3 & 0 & 1 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 \\ 1 & 0 & 0 & 0 & 3 \end{vmatrix}
9. \begin{vmatrix} 0 & 0 & 3 & 0 & 0 \\ 1 & 2 & 0 & 0 & 4 \\ 0 & 1 & 0 & 2 & 0 \\ 3 & 0 & 1 & 0 & 1 \\ 0 & 2 & 0 & 1 & 0 \end{vmatrix}

Day 2: triangular matrices

10. \displaystyle \begin{vmatrix} 1 & 4 & 0 & -3 & 2 \\ 0 & -2 & 7 & 1 & 5 \\ 0 & 0 & 3 & 8 & -1 \\ 0 & 0 & 0 & \frac{1}{3} & 6 \\ 0 & 0 & 0 & 0 & 4 \end{vmatrix}
11. \begin{vmatrix} 5 & 0 & 0 & 0 \\ 2 & 3 & 0 & 0 \\ -4 & 1 & 0 & 0 \\ 7 & 6 & 9 & 8 \end{vmatrix}
12. \begin{vmatrix} 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 1 \\ 0 & -1 & 4 & 5 \\ 6 & 7 & 8 & 9 \end{vmatrix}

Day 2: parameters

13. Find every k with \begin{vmatrix} 1 & 0 & 2 & 0 \\ 0 & k & 0 & 3 \\ 2 & 0 & 5 & 0 \\ 0 & 3 & 0 & k \end{vmatrix} = 0.
14. Find every x with \begin{vmatrix} x & -1 & 0 & 0 \\ 0 & x & -1 & 0 \\ 0 & 0 & x & -1 \\ 0 & -6 & 11 & x - 6 \end{vmatrix} = 0.
15. A design value t enters a force system with coefficient matrix \begin{bmatrix} 2 & 1 & 0 & t \\ 1 & t & 0 & 1 \\ 0 & 3 & 1 & 0 \\ t & 0 & 0 & 2 \end{bmatrix}. For which t does it fail to have exactly one solution?
16. For A = \begin{bmatrix} 2 & 3 & 0 & 1 \\ 0 & -1 & 4 & 2 \\ 0 & 0 & 5 & -3 \\ 0 & 0 & 0 & 2 \end{bmatrix}, find every \lambda with \det(A - \lambda I) = 0.

Day 2: cost

17. Expanding a 6 \times 6 matrix with no zeros all the way down to 2 \times 2 determinants, how many 2 \times 2 determinants are there, and how many products in the final sum?
18. At 10^9 products per second, roughly how long does full cofactor expansion of a 15 \times 15 matrix with no zeros take?

Reasoning

19. Show that an n \times n matrix with a row of zeros, or a column of zeros, has determinant 0.
20. Prove by induction on n, expanding along row 1, that \det(cA) = c^n \det A for an n \times n matrix A.
21. Write out the proof that a lower triangular matrix has determinant equal to the product of its diagonal, expanding along row 1 each time.
22. Prove by induction that \det A^{T} = \det A, using the theorem that row 1 and column 1 give the same expansion.
23. Ruiha claims that a 4 \times 4 matrix with a 0 in every row must have determinant 0. Give a counterexample.
24. Show that the recursive definition, applied to a 2 \times 2 matrix with \det [a] = a, gives ad - bc, and explain why expanding along row 2 gives the same.