Today we mostly finish 4.2. **Read** Section 4.3 and Appendix D
(polynomials) for next class.
Work through recommended homework questions.

**Drop date:** Wednesday, November 5 (today!)

**Tutorials:** Quiz this week covers 3.6, 3.7 (Markov chains) and 4.1.
Midterms returned in tutorials.
Solutions available.
Average: 47.5/70 = 68%.

**Office hour:** Wednesday, 11:30-noon, MC103B.

**Help Centers:** Monday-Friday 2:30-6:30 in MC106.

**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, then $\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^\strut$.

**Solution:**
$$
\kern-8ex
\begin{aligned}
\bmat{rrrr} 2 & \phm 4 & \phm 6 & \phm 8 \\ 1 & 2 & 1 & 2 \\ 2 & 2 & 12 & 8 \\ 1 & 2 & 3 & 9 \emat
&\lra{(1/2)R_1}
\bmat{rrrr} 1 & \phm 2 & \phm 3 & \phm 4 \\ 1 & 2 & 1 & 2 \\ 2 & 2 & 12 & 8 \\ 1 & 2 & 3 & 9 \emat \\
\lra{\mystackthree{\scriptstyle R_2 - R_1}{\scriptstyle R_3 - 2R_1}{\scriptstyle R_4 - R_1}}
\bmat{rrrr} 1 & 2 & 3 & 4 \\ 0 & 0 & -2 & -2 \\ 0 & -2 & 6 & 0 \\ 0 & 0 & 0 & 5 \emat
&\lra{\,R_2 \leftrightarrow R_3\,}
\bmat{rrrr} 1 & \phm 2 & 3 & 4 \\ 0 & -2 & 6 & 0 \\ 0 & 0 & -2 & -2 \\ 0 & 0 & 0 & 5 \emat
\end{aligned}
$$
The determinant of the last matrix is $(1)(-2)(-2)(5) = 20$, so
the determinant of the original matrix is $\query{-40}$

**Example:** Same for $A = \bmat{rrr} 2 & 3 & -1 \\ -4 & -6 & 2 \\ 2 & 5 & 3 \emat$.
On board.

Note that you can even mix and match row and column operations, if it simplifies the work.

**Question:**
What happens if you do something like "replace $R_3$ with $R_1 + 3 R_3$"?

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?

Use **Laplace expansion** for matrices
with lots of zeros, or matrices with variables like $\lambda$.
Use **row reduction** for $4 \times 4$ or larger matrices with not many zeros.
For a $3 \times 3$ matrix, which is better depends on the matrix.

**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_n & \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.