Exercise
Find all real numbers \(k\) for which the matrix \(\begin{bmatrix} 1 & 0 & 3 \\ -2 & k & 1 \\ 5 & -1 & 1 \end{bmatrix}\) is not invertible. (This was on your Homework 5, but try doing it with determinants!)
Exercise
Suppose that \(A\) is an \(n \times n\) matrix. What is the relationship between \(\det(2A)\) and \(\det(A)\)?
Answer: It's not \(\det(2A) = 2 \det(A),\) as you may expect. Instead, we have \(\det(2A) = 2^n \det(A) \) because each of the \(n\) rows of \(A\) is being multiplied by 2. (In general, \(\det(cA) = c^n \det(A).\))
Today we'll continue discussing the determinant. We'll prove that \(A\) is invertible if and only if \(\det(A) \neq 0\), and then we'll examine two ways to compute the determinant: a method using row reduction, and a recursive method called cofactor expansion.
Now that we have a bevy of facts about the determinant at our disposal, we are in a position to prove the main theorem about the determinant:
Theorem (determinant and invertibility)
An \(n \times n\) matrix \(A\) is invertible if and only if \(\det(A) \neq 0.\)
To prove this, consider starting with \(A\) and performing row operations to get to echelon form: \[A \longrightarrow \dotsm \longrightarrow B.\] By our determinant facts, each kind of row operation multiplies the determinant by a nonzero number:
It follows that \(\det(A) \neq 0\) if and only if \(\det(B) \neq 0\): row operations can never change the determinant from zero to nonzero, or vice versa.
If \(A\) is invertible, then \(B\) will have a pivot in every row and column. Because \(B\) is square, this means that the pivots must go along the main diagonal. Therefore, \(B\) will be upper triangular, and its diagonal entries will be nonzero. Then, one of our determinant facts tells us that \(\det(B) \neq 0\). Therefore, \(\det(A)\) must be nonzero too.
On the other hand, suppose that \(A\) is not invertible. Then \(B\) will not have a pivot in every row, so there will be a row of all zeros at the bottom. By one of our determinant facts, \(\det(B) = 0.\) Therefore, \(\det(A)\) must be zero too. This proves the theorem!
This also gives us a way to calculate the determinant of a matrix \(A\). Specifically, we can perform row operations to put \(A\) into echelon form, while keeping track of which row operations we used and how they affect the determinant:
Once \(A\) is in echelon form, it will either be in triangular form, in which case we know the determinant is the product of the diagonal entries, or it will have fewer than \(n\) pivots and therefore be non-invertible, with determinant \(0.\)
(If you don't want to have to keep track of the constants when scaling rows, it's possible to put \(A\) into echelon form without having to multiply or divide rows by constants, although it may be messier than otherwise.)
Example
Let's compute the determinant of the matrix \(A = \begin{bmatrix} 2 & 4 & 6 \\ 1 & 2 & 2 \\ 0 & 3 & -2 \end{bmatrix}\) by row reduction: \[\begin{aligned} \begin{bmatrix} 2 & 4 & 6 \\ 1 & 2 & 2 \\ 0 & 3 & -2 \end{bmatrix}
\quad \stackrel{\frac{1}{2}R_1 \to R_1}{\longrightarrow} \quad \begin{bmatrix} 1 & 2 & 3 \\ 1 & 2 & 2 \\ 0 & 3 & -2 \end{bmatrix}
\quad \stackrel{-R_1 + R_2 \to R_2}{\longrightarrow} \quad \begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & -1 \\ 0 & 3 & -2 \end{bmatrix}
\quad \stackrel{R_2 \leftrightarrow R_3}{\longrightarrow} \quad \begin{bmatrix} 1 & 2 & 3 \\ 0 & 3 & -2 \\ 0 & 0 & -1 \end{bmatrix}. \end{aligned}\] We ended up with a matrix in triangular form, and its determinant is therefore \((1)(3)(-1) = -3.\) In getting there, we multiplied a row by \(\frac{1}{2}\) and switched rows once, so we need to divide our answer by \(\frac{1}{2}\) (that is, multiply it by \(2\)) and then negate it. Therefore, the determinant of the original matrix is \[\det(A) = (-3)(2)(-1) = 6.\] (You can check this answer using the shortcut method for \(3 \times 3\) determinants.)
For a general matrix, this row reduction method is much faster for computing the determinant than using the "pattern" definition. The pattern definition involves adding \(n!\) terms, each of which can be very large, while it can be shown that row reduction takes approximately \(\frac{2}{3} n^3\) arithmetic operations. (This may seem like a lot, but \(n!\) is far larger; compare \(\frac{2}{3} \cdot 10^3 \approx 670\) with \(10! \approx 3,\!600,\!000.\))
Let's now look at a recursive method for computing the determinant that breaks an \(n \times n\) determinant down into several \( (n-1) \times (n-1) \) determinants, either signed positively or negatively. This method is referred to as cofactor expansion because each of the (signed) smaller determinants is called a cofactor of the original matrix. It is also known as Laplace expansion after the 18th-century mathematician Pierre-Simon Laplace. (This is a French name, pronounced like "luh-ploss." You may know the name from the Laplace transform if you've taken or are taking Math 207.)
Definition (submatrix and minor)
Let \(A\) be an \(n \times n\) matrix. The \((i,j)\)-submatrix of \(A\) is the \((n-1) \times (n-1)\) matrix formed from \(A\) by deleting the \(i\)th row and \(j\)th column. The \((i,j)\)-minor of \(A,\) denoted \(M_{i,j},\) is the determinant of the \((i,j)\)-submatrix.
For example, if \(A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix},\) then the \((1,2)\)-submatrix of \(A\) is \(\begin{bmatrix} 4 & 6 \\ 7 & 9 \end{bmatrix},\) and so \[M_{1,2} = (4)(9) - (7)(6) = 36 - 42 = -6.\] Cofactor expansion is a formula that writes \(\det(A)\) as a sum of signed minors along any row or column of \(A.\) Those signed minors are called cofactors:
Definition (cofactor)
The \((i,j)\)-cofactor of \(A\) is defined by \[C_{i,j} = (-1)^{i+j} M_{i,j}.\]
For example, for the matrix above, we have \[C_{1,2} = (-1)^{1+2} M_{1,2} = -(-6) = 6.\] We can now state the formula for cofactor expansion:
Theorem (cofactor expansion)
Let \(A\) be an \(n \times n\) matrix. Then for any \(i,\) the determinant of \(A\) is the sum of the cofactors along the \(i\)th row of \(A,\) multiplied by the corresponding entries from \(A\): \[ \det(A) = a_{i,1} \cdot C_{i,1} + a_{i,2} \cdot C_{i,2} + \dotsm + a_{i,n} \cdot C_{i,n}. \] It is also, for any \(j,\) the sum of the cofactors along the \(j\)th column of \(A,\) multiplied by the corresponding entries from \(A\): \[ \det(A) = a_{i,j} \cdot C_{1,j} + a_{2,j} \cdot C_{2,j} + \dotsm + a_{n,j} \cdot C_{n,j}. \]
This theorem is probably rather opaque, so let's see some examples of using it.
Example (cofactor expansion #1)
Let's again take \(A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}.\) When doing cofactor expansion, we can use any row or column; we say that we are expanding along that row or column. Let's try expanding along the first row; the formula tells us that \[\det(A) = a_{1,1} \cdot C_{1,1} + a_{1,2} \cdot C_{1,2} + a_{1,3} \cdot C_{1,3}.\] Writing this out in terms of the corresponding entries and determinants, we get \[ \det(A) = \left| \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} \right| = 1 \left| \begin{matrix} 5 & 6 \\ 8 & 9 \end{matrix} \right| - 2 \left| \begin{matrix} 4 & 6 \\ 7 & 9 \end{matrix} \right| + 3 \left| \begin{matrix} 4 & 5 \\ 7 & 8 \end{matrix} \right|.\] We can now evaluate these \(2 \times 2\) determinants, and therefore compute \(\det(A)\): \[\begin{aligned} \left| \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} \right| &= 1 (5 \cdot 9 - 6 \cdot 8) - 2 (4 \cdot 9 - 6 \cdot 7) + 3 (4 \cdot 8 - 5 \cdot 7) \\ &= 1 (-3) - 2(-6) + 3(-3) \\ &= -3 + 12 - 9 = 0. \end{aligned}\] (Note: It makes sense that \(\det(A) = 0,\) because the second column of \(A\) is the average of the first and third columns. This is a nontrivial linear relation between the columns, so \(A\) is not invertible.)
We could also expand any other row or column and get the same result. For example, expanding along the second column, we get \[\begin{aligned} \det(A) = \left| \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} \right| &= a_{1,2} \cdot C_{1,2} + a_{2,2} \cdot C_{2,2} + a_{3,2} \cdot C_{3,2} \\ &= -2 \left| \begin{matrix} 4 & 6 \\ 7 & 9 \end{matrix} \right| + 5 \left| \begin{matrix} 1 & 3 \\ 7 & 9 \end{matrix} \right| - 8 \left| \begin{matrix} 1 & 3 \\ 4 & 6 \end{matrix} \right| \\ &= -2(-6) + 5(-12) - 8(-6) \\ &= 0. \end{aligned}\]
The hardest part of doing cofactor expansion is probably getting the signs correct on the cofactors. A good way to remember them is to imagine an "infinite matrix" labeled with \(+\) and \(-\) signs in a checkerboard pattern, with \(+\) in the top-left: \[\begin{bmatrix} + & - & + & \dotsm \\ - & + & - & \dotsm \\ + & - & + & \dotsm \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}.\] This matrix tells you the sign attached to each cofactor: namely, the \((i,j)\)-cofactor has sign \((-1)^{i+j}.\) Along any row and column, these signs will alternate, but they may start with either \(+\) or \(-.\)
We won't get into a full proof of the formula for cofactor expansion. However, the reason it works comes from the original definition of \(\det(A)\) in terms of patterns. Recall that \(\det(A)\) is defined to be a signed sum of terms, each of which is the product of entries in a pattern: \[\det(A) = \sum_{\text{patterns in } A} (-1)^{\# \text{ inversions}} \; (\text{product of entries in pattern}).\] Suppose we consider some fixed row or column in \(A\); every pattern, by definition, will contain one entry in that row or column. Then, cofactor expansion basically involves splitting up the patterns of \(A\) into \(n\) groups, based on which entry from that row or column they contain. For instance, expanding along the first row, we would get something like \[\begin{aligned} \det(A) = \sum_{\text{patterns w/ } a_{1,1} } (-1)^{\# \text{ invs}} \; \left(\begin{matrix} \text{product of} \\ \text{entries} \end{matrix}\right) + \sum_{\text{patterns w/ } a_{1,2} } (-1)^{\# \text{ invs}} \; \left(\begin{matrix} \text{product of} \\ \text{entries} \end{matrix}\right) + \dotsm + \sum_{\text{patterns w/ } a_{1,n} } (-1)^{\# \text{ invs}} \; \left(\begin{matrix} \text{product of} \\ \text{entries} \end{matrix}\right). \end{aligned}\] Now, notice that in the first summation, every pattern contains \(a_{1,1},\) so we can factor out \(a_{1,1}\) from every term in that summation. We can do the same with every summation in this formula. Then, the final step is to interpret each of the remaining pieces as a cofactor of \(A.\) The key idea here is that, if a pattern contains \(a_{1,1},\) then the other entries form a pattern for the \((1,1)\)-submatrix of \(A.\)
We won't get further into the details, but this is how the proof would go. Essentially, cofactor expansion is a way of keeping track of all the patterns in a matrix without having to manually compute the number of inversions for each pattern.
Because cofactor expansion is based on the pattern definition rather than row reduction, it is still a very slow method for computing the determinant of a general matrix. However, cofactor expansion can be very useful for matrices with many zeros. In particular, if a row or column of a matrix has many zeros, then expanding along that row or column is usually a good idea. Because each term in the formula involves multiplying by an entry in that row or column, many of the terms will just equal zero, and it'll be relatively easy to take care of the rest.
Example (cofactor expansion #2)
Suppose we want to compute the determinant of the \(4 \times 4\) matrix \[A = \begin{bmatrix} 1 & 0 & 2 & 0 \\ 0 & 3 & 4 & 0 \\ 5 & 6 & 0 & 7 \\ 0 & 8 & 9 & 0 \end{bmatrix}.\] An easy way to do so is to notice that the last column of \(A\) only has one nonzero entry, namely the \(7.\) Therefore, if we expand along the last column, we'll get \[\det A = \left|\begin{matrix} 1 & 0 & 2 & 0 \\ 0 & 3 & 4 & 0 \\ 5 & 6 & 0 & 7 \\ 0 & 8 & 9 & 0 \end{matrix}\right| = -7 \left|\begin{matrix} 1 & 0 & 2 \\ 0 & 3 & 4 \\ 0 & 8 & 9 \end{matrix}\right|. \] We could compute the determinant of the resulting \(3 \times 3\) matrix by using the formula / shortcut method. Alternatively, we could use cofactor expansion again, noting that the first column of this matrix only has one nonzero entry: \[ \left|\begin{matrix} 1 & 0 & 2 \\ 0 & 3 & 4 \\ 0 & 8 & 9 \end{matrix}\right| = +1 \left| \begin{matrix} 3 & 4 \\ 8 & 9 \end{matrix} \right| = -5.\] Therefore, the final answer is \[ \det A = -7(-5) = 35.\]