Determinant Formulas and Cofactors

From three properties to a 2×2 formula

This is the second of three lectures on determinants — “a fascinating, small topic inside linear algebra.” Determinants used to be the big thing and linear algebra the little thing; that situation has reversed. The goal today is a formula for the determinant. It will be a messy formula — that’s exactly why the course started with the three properties instead.

Everybody knows the 2×2 answer, but Strang wants to derive it from the properties, because the derivation is the method that will scale to $n \times n$. Property 1 gives $\det I = 1$; property 2 (a row exchange flips the sign) gives $\det \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = -1$. Now use property 3 — linearity in one row at a time, the other row held fixed. Split the first row of $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$ as $(a, b) = (a, 0) + (0, b)$, then split the second row of each piece:

$$\begin{vmatrix} a & b \\ c & d \end{vmatrix} = \begin{vmatrix} a & 0 \\ c & d \end{vmatrix} + \begin{vmatrix} 0 & b \\ c & d \end{vmatrix} = \begin{vmatrix} a & 0 \\ c & 0 \end{vmatrix} + \begin{vmatrix} a & 0 \\ 0 & d \end{vmatrix} + \begin{vmatrix} 0 & b \\ c & 0 \end{vmatrix} + \begin{vmatrix} 0 & b \\ 0 & d \end{vmatrix}$$

Four easy determinants, and two die instantly: the first and last each have a column of zeros — a singular matrix, determinant zero “for, like, forty-eight different reasons.” The survivors: the diagonal piece gives $ad$, and the anti-diagonal piece gives $-bc$ (one row exchange to reach diagonal form, then factor out $b$ and $c$). So $\det = ad - bc$, the answer we knew — but now we own the method.

Three by three: the survivors

Run the same splitting on a 3×3. Each of the three rows breaks into three pieces, so the count goes $3 \to 9 \to 27$ — three cubed pieces. “Yes, oh God.” But most are zero. A piece survives only when no column is left empty, and that forces the rule:

Each surviving piece has one entry from each row and each column. It looks like a permutation matrix with the ones replaced by entries $a_{ij}$. Factor the entries out and what remains is the determinant of a permutation matrix — $+1$ or $-1$ according to whether an even or odd number of row exchanges brings it back to the identity.

For 3×3 there are six survivors. Column numbers in order $(1,2,3)$ gives $+a_{11}a_{22}a_{33}$; order $(1,3,2)$ is one exchange away from the identity, so $-a_{11}a_{23}a_{32}$; and so on through all six permutations:

$$\det A = a_{11}a_{22}a_{33} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31}$$

The plus terms are the ones that “go down this way” (parallel to the main diagonal, wrapping around) and the minuses go the other way — down toward Miami and down toward LA. Strang refuses to make that arrows-on-the-board rule precise, for two reasons: it would clutter the board, and it’s wrong for 4×4. Check it: a 4×4 matrix with ones on the anti-diagonal has determinant $+1$, not $-1$, because exchanging rows one and four and then rows two and three — two exchanges — produces the identity. The Miami–LA trick is three-by-three only.

The big formula

Now the jump from 3×3 to $n \times n$.

Where does $n!$ come from? This is the moment to listen: the entry from the first row can be chosen $n$ ways; that uses up a column, so the entry from the second row can be chosen $n - 1$ ways; the third, $n - 2$ ways — down to no choice at all in the last row. So $n \cdot (n-1) \cdots 1 = n!$ terms: 2, 6, 24, 120, 720, and whatever comes after that.

Sanity check: if $A = I$, almost every term is zero because almost every entry is zero. The only survivor is the identity permutation, $a_{11}a_{22}\cdots a_{nn} = 1$, with a plus sign — so $\det I = 1$, and property 1 comes back out of the formula. In principle everything comes back out, even $\det AB = (\det A)(\det B)$ — “but like next week we would still be working on it,” so that proof won’t be repeated in 18.06.

Cofactors: the formula, one size smaller

Cofactors break the big formula up differently: they connect an $n \times n$ determinant to determinants of size $n - 1$. Take the 3×3 big formula and group it by the first-row entry:

$$\det A = a_{11}\,(a_{22}a_{33} - a_{23}a_{32}) + a_{12}\,(-a_{21}a_{33} + a_{23}a_{31}) + a_{13}\,(a_{21}a_{32} - a_{22}a_{31})$$

Look at the factor multiplying $a_{11}$: it is exactly the determinant of the 2×2 matrix left when row 1 and column 1 are erased. Of course it is — once $a_{11}$ is used, the remaining factors must use the other $n-1$ rows and $n-1$ columns, one of each, and that’s precisely the big formula for the smaller determinant. The factor multiplying $a_{12}$ is minus the determinant of its smaller matrix — the sign gets built in.

The world’s smallest example: for $\begin{bmatrix} a & b \\ c & d \end{bmatrix}$, expand along row one. The cofactor of $a$ is $d$ (strike row 1, column 1). The cofactor of $b$ is $-c$ — the $1 + 2$ position is odd. So $\det = ad + b(-c)$. It worked. Of course it worked.

Tridiagonal ones: a determinant with period six

The reward for cofactors is a genuinely non-trivial family. Let $A_n$ be the $n \times n$ tridiagonal matrix of ones — ones on the diagonal and on the two neighboring diagonals, zeros elsewhere. For $n = 4$:

$$A_4 = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}$$

Start small. $\det A_1 = 1$. $\det A_2 = \begin{vmatrix} 1 & 1 \\ 1 & 1 \end{vmatrix} = 0$. For $A_3$ the answer is $-1$ — by the big formula, only the diagonal term $+1$ and the two anti-diagonal-direction terms $-1, -1$ survive. (Or subtract row three from row two to create zeros first, then expand — determinants reward a little elimination before cofactors.)

Now $A_4$ by cofactors along the first row. The $1$ in the corner multiplies the determinant of what’s left when its row and column are struck out — and that leftover matrix is $A_3$. The second entry, a $1$ in the $(1,2)$ position, carries a minus sign; strike out its row and column and expand the resulting 3×3 down its first column (only one nonzero entry there — Strang skips the entries multiplied by zero, “no use wasting time”), and what emerges is $-\det A_2$. The pattern is general:

$$\det A_n = \det A_{n-1} - \det A_{n-2}$$

So $\det A_4 = -1 - 0 = -1$, $\det A_5 = -1 - (-1) = 0$, $\det A_6 = 0 - (-1) = 1$, $\det A_7 = 1 - 0 = 1$. The sequence of determinants is

$$1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ \ldots$$

and it repeats: these determinants have period six. “It’s pretty fantastic.” So $\det A_{61} = \det A_1 = 1$, instantly. A non-trivial tridiagonal determinant, done entirely by cofactors.

Problems

Work these with the big formula and cofactors — choose whichever puts the mess where you can handle it.

Problem 19.1 Big formula, all six terms

Use the big formula (all six permutation terms, with their signs) to compute

$$\det \begin{bmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{bmatrix}$$

Show solution

The six terms $\pm\, a_{1\alpha}a_{2\beta}a_{3\gamma}$, ordered by permutation of the columns:

• $(1,2,3)$, even: $+\,(2)(2)(2) = 8$
• $(1,3,2)$, odd: $-\,(2)(1)(1) = -2$
• $(2,1,3)$, odd: $-\,(1)(1)(2) = -2$
• $(2,3,1)$, even: $+\,(1)(1)(0) = 0$
• $(3,1,2)$, even: $+\,(0)(1)(1) = 0$
• $(3,2,1)$, odd: $-\,(0)(2)(0) = 0$

Sum: $8 - 2 - 2 = 4$. So the determinant is $4$.

Problem 19.2 Survivors and signs

Find the determinant of

$$A = \begin{bmatrix} 0 & 2 & 0 & 0 \\ 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 0 & 5 & 0 \end{bmatrix}$$

by identifying every nonzero term of the big formula and its sign.

Show solution

A term survives only if it takes one nonzero entry from each row and column. Row 1 forces column 2, which forces row 2 to use column 1; row 3 forces column 4, which forces row 4 to use column 3. So there is exactly one survivor:

$$a_{12}\, a_{21}\, a_{34}\, a_{43} = (2)(3)(4)(5) = 120$$

Its column order is $(2, 1, 4, 3)$. Two exchanges (swap 2 and 1, swap 4 and 3) reach the identity, so the permutation is even: sign $+$.

$$\det A = +120$$

Problem 19.3 Cofactor expansion

Expand along the first row to compute

$$\det \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10 \end{bmatrix}$$

writing out each cofactor $C_{11}, C_{12}, C_{13}$ with its sign.

Show solution

The cofactors (strike out row 1 and the entry’s column; sign $(-1)^{1+j}$):

$$C_{11} = +\begin{vmatrix} 5 & 6 \\ 8 & 10 \end{vmatrix} = 50 - 48 = 2, \qquad C_{12} = -\begin{vmatrix} 4 & 6 \\ 7 & 10 \end{vmatrix} = -(40 - 42) = 2, \qquad C_{13} = +\begin{vmatrix} 4 & 5 \\ 7 & 8 \end{vmatrix} = 32 - 35 = -3$$

Then

$$\det A = a_{11}C_{11} + a_{12}C_{12} + a_{13}C_{13} = (1)(2) + (2)(2) + (3)(-3) = 2 + 4 - 9 = -3$$

Problem 19.4 Period six in action

Let $A_n$ be the $n \times n$ tridiagonal matrix of ones from the lecture. Using the recurrence $\det A_n = \det A_{n-1} - \det A_{n-2}$, find $\det A_{100}$.

Show solution

The recurrence with $\det A_1 = 1$, $\det A_2 = 0$ generates

$$1,\ 0,\ -1,\ -1,\ 0,\ 1,\ 1,\ 0,\ -1,\ -1,\ 0,\ 1,\ \ldots$$

which repeats with period six: $\det A_{n+6} = \det A_n$.

Since $100 = 6 \cdot 16 + 4$, we have $\det A_{100} = \det A_4 = -1$.

Problem 19.5 Zeros make it fast

Compute

$$\det \begin{bmatrix} 2 & 0 & 0 & 1 \\ 0 & 3 & 0 & 0 \\ 0 & 4 & 1 & 0 \\ 5 & 0 & 0 & 1 \end{bmatrix}$$

choosing the row or column of your cofactor expansion to minimize work, and skipping any cofactor that gets multiplied by zero.

Show solution

Column 3 has only one nonzero entry, $a_{33} = 1$, in a $+$ position ($3 + 3$ even). So

$$\det A = 1 \cdot \begin{vmatrix} 2 & 0 & 1 \\ 0 & 3 & 0 \\ 5 & 0 & 1 \end{vmatrix}$$

In the 3×3, expand along its middle row — again one nonzero entry, $3$, in a $+$ position ($2 + 2$ even):

$$\det A = 1 \cdot 3 \cdot \begin{vmatrix} 2 & 1 \\ 5 & 1 \end{vmatrix} = 3\,(2 - 5) = -9$$