Today we mostly finish 4.2. Read Section 4.3 and Appendix D
(polynomials) for next class.
Work through recommended homework questions.
Tutorials: Quiz 7 will cover 3.7 (just Markov chains), 4.1, and 4.2 up to and including Example 4.13.
Office hour: Monday, 1:30-2:30 and Wednesday, 10:30-11:15, MC103B.
Help Centers: Monday-Friday 2:30-6:30 in MC 106.
Definition: Let $A = [a_{ij}]$ be an $n \times n$ matrix. Then the determinant of $A$ is the scalar $$ \begin{aligned} \det A = |A| &= a_{11} C_{11} + a_{12} C_{12} + \cdots + a_{1n} C_{1n} \\ &= \sum_{j=1}^{n} a_{1j} C_{1j} = \sum_{j=1}^{n} (-1)^{1+j} \, a_{1j} \det A_{1j} . \end{aligned} $$ We define the determinant of a $1 \times 1$ matrix $[a]$ to be $a$.
This is a recursive definition!
For $n = 2$: $$ \kern-6ex \begin{aligned} \det A = |A| &= \bdmat{rr} a_{11} & a_{12} \\ a_{21} & a_{22} \edmat \\ &= a_{11} |a_{22}| - a_{12} |a_{21}| = a_{11} a_{22} - a_{12} a_{21} , \end{aligned} $$ as we defined earlier.
For a $3 \times 3$ matrix $A$, we have $$ \kern-9ex \begin{aligned} \det A = \bdmat{rrr} \red{a_{11}} & \red{a_{12}} & \red{a_{13}} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \edmat &= \red{a_{11}} C_{11} + \red{a_{12}} C_{12} + \red{a_{13}} C_{13} \\ &= \red{a_{11}} \bdmat{rr} a_{22} & a_{23} \\ a_{32} & a_{33} \edmat - \red{a_{12}} \bdmat{rr} a_{21} & a_{23} \\ a_{31} & a_{33} \edmat + \red{a_{13}} \bdmat{rr} a_{21} & a_{22} \\ a_{31} & a_{32} \edmat \end{aligned} $$
The computation can be very long if there aren't many zeros! We'll learn some better methods.
The above is called the cofactor expansion along the first row. It turns out that any row or column works!
Theorem 4.1 (The Laplace Expansion Theorem): Let $A$ be any $n \times n$ matrix. Then for each $i$ we have $$ \kern-6ex \det A = a_{i1} C_{i1} + a_{i2} C_{i2} + \cdots + a_{in} C_{in} = \sum_{j=1}^{n} \, a_{ij} C_{ij} $$ (cofactor expansion along the $i$th row). And for each $j$ we have $$ \kern-6ex \det A = a_{1j} C_{1j} + a_{2j} C_{2j} + \cdots + a_{nj} C_{nj} = \sum_{i=1}^{n} \, a_{ij} C_{ij} $$ (cofactor expansion along the $j$th column).
The book proves this result at the end of this section, but we won't cover the proof.
The signs in the cofactor expansion form a checkerboard pattern: $$ \bmat{ccccc} + & - & + & - & \cdots \\ - & + & - & + & \cdots \\ + & - & + & - & \cdots \\ - & + & - & + & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \emat $$
A triangular matrix is a square matrix that is all zero below the diagonal or above the diagonal.
Theorem 4.2: If $A$ is triangular, then $\det A$ is the product of the diagonal entries.
So how do we do better? Like always, we turn to row reduction! These properties will be what we need:
Theorem 4.3: Let $A$ be a square matrix.
a. If $A$ has a zero row, the $\det A = 0$.
b. If $B$ is obtained from $A$ by interchanging two rows,
then $\det B = - \det A$.
c. If $A$ has two identical rows, then $\det A = 0$.
d. If $B$ is obtained from $A$ by multiplying a row of $A$ by $k$,
then $\det B = k \det A$.
e. If $A$, $B$ and $C$ are identical in all rows except the $i$th row,
and the $i$th row of $C$ is the sum of the $i$th rows of $A$ and $B$,
then $\det C = \det A + \det B$.
f. If $B$ is obtained from $A$ by adding a multiple of one row to another,
then $\det B = \det A$.
All of the above statements are true with rows replaced by columns.
The bold statements are the ones that are useful for understanding how row operations change the determinant.
Example: Use row operations to compute $\det A$ by reducing to triangular form, where $A = \bmat{rrrr} 2 & 4 & 6 & 8 \\ 1 & 2 & 1 & 2 \\ 2 & 2 & 12 & 8 \\ 1 & 2 & 3 & 9 \emat$. On board.
Example: Same for $A = \bmat{rrr} 2 & 3 & -1 \\ -4 & -6 & 2 \\ 2 & 5 & 3 \emat$.
Note that you can even mix and match row and column operations, if it simplifies the work.
Row reduction of an $n \times n$ matrix requires roughly $n^3$ operations in general, which is much less than $n$ factorial. E.g. 3 hours vs. 1 year to do a $10 \times 10$ matrix by hand? On the other hand, if the matrix contains variables like $\lambda$, row reduction is quite awkward, and Laplace expansion tends to be better.
Theorem 4.6: A square matrix $A$ is invertible if and only if $\det A \neq 0$.
The book proves this using elementary matrices, which we aren't covering, but here is a simpler proof.
Proof: If $A$ is invertible, then by the Fundamental Theorem, the reduced row echelon form of $A$ is $I$. Each elementary row operation either leaves the determinant the same or multiplies by a non-zero number. Since $\det I = 1 \neq 0$, we must also have $\det A \neq 0$.
On the other hand, if $A$ is not invertible, then the reduced row echelon form $R$ has a zero row, so $\det R = 0$. Again, $\det A = k \det R$ for some $k$, so $\det A = 0$ too. $\quad\Box$
Example: The $4 \times 4$ matrix above is invertible, but the $3 \times 3$ is not. The computations illustrate the proof of the theorem.
Question: Is the matrix $\bmat{rrr} 1 & 0 & 0 & 0 \\ 2 & 5 & 0 & 0 \\ 3 & 6 & 0 & 0 \\ 4 & 7 & 8 & 9 \\ \emat$ invertible?
Theorems 4.7 to 4.10: Let $A$ be an $n \times n$ matrix. Then:
4.7: $\det(k A) = \query{k^n \det A}$
4.8: $\det(A B) = \query{(\det A) (\det B)}$
4.9: $\det(A^{-1}) = \query{\frac{1}{\det A}}$, if $A$ is invertible.
4.10: $\det(A^T) = \query{\det A}$
Note: There is no formula for $\det(A+B)$.
Proofs:
4.7: Follows from Theorem 4.3(d), since each row is multiplied by $k$.
4.8: The book uses elementary matrices to prove this, which we haven't covered,
so there is no easy way for us to prove this. I'll do an example below.
4.9: This follows from 4.8. Since $\det(A A^{-1}) = \det(I) = 1$
we have $(\det A)(\det A^{-1}) = 1$, so $\det A^{-1} = 1/\det A$.
4.10: Computing $\det A$ using expansion along the first row
produces the same thing as computing $\det (A^T)$ by expanding along
the first column. (Proof by induction on the size of the matrix.)
$\quad\Box$
Example: Illustrate all four statements with $2 \times 2$ matrices, on board.
True/false: If $A$ and $B$ are invertible, then so is $A + B$.
True/false: If $A$ is not invertible, then $AB$ is not invertible.
Notation: If $A$ is an $n \times n$ matrix and $\vb \in \R^n$, we write $A_i(\vb)$ for the matrix obtained from $A$ by replacing the $i$th column with the vector $\vb$: $$ A_i(\vb) = [ \va_1 \cdots \va_{i-1} \, \vb \,\, \va_{i+1} \cdots \va_n \,] $$
Theorem: Let $A$ be an invertible $n \times n$ matrix and let $\vb$ be in $\R^n$. Then the unique solution $\vx$ of the system $A \vx = \vb$ has components $$ x_i = \frac{\det(A_i(\vb))}{\det A},\quad \text{for } i = 1, \ldots, n $$
Example 4.16: On board: Use Cramer's rule to solve $$ \begin{aligned} x_1 + 2 x_2 &= 2 \\ -x_1 + 4 x_2 &= 1 \end{aligned} $$
Proof: Suppose $A \vx = \vb$. Consider $I_i(\vx) = [ \ve_1 \cdots \vx \cdots \ve_n\,]$. Then $$ \kern-6ex \begin{aligned} A\, I_i(\vx) &= A \, [ \ve_1 \cdots \vx \cdots \ve_n\,] = [ A \ve_1 \cdots A \vx \cdots A \ve_n\,]\\ &= [ \va_1 \cdots \vb \cdots \va_n\,] = A_i(\vb) . \end{aligned} $$ So $$ \kern-6ex (\det A)(\det I_i(\vx)) = \det (A \, I_i(\vx)) = \det(A_i(\vb)). $$ But $$ \det I_i(\vx) = \bdmat{ccccc} 1 & \cdots & x_1 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & x_i & \cdots & 0 \\ \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & x_1 & \cdots & 1 \\ \edmat = x_i $$ by expanding along $i$th row. So the claim follows.$\quad\Box$
Note: This is not an efficient method. For an $n \times n$ system, you have to compute $n+1$ determinants. But the work in computing $1$ determinant is enough to solve the system by our usual method.
Theorem: If $A$ is an invertible matrix, then $$ A^{-1} = \frac{1}{\det A} \adj A $$
On board: explain the $2 \times 2$ special case.
I will explain the general case next lecture.