Math 1600 Lecture 25, Section 2, 5 Nov 2014

$ \newcommand{\bdmat}[1]{\left|\begin{array}{#1}} \newcommand{\edmat}{\end{array}\right|} \newcommand{\bmat}[1]{\left[\begin{array}{#1}} \newcommand{\emat}{\end{array}\right]} \newcommand{\coll}[2]{\bmat{r} #1 \\ #2 \emat} \newcommand{\ccoll}[2]{\bmat{c} #1 \\ #2 \emat} \newcommand{\colll}[3]{\bmat{r} #1 \\ #2 \\ #3 \emat} \newcommand{\ccolll}[3]{\bmat{c} #1 \\ #2 \\ #3 \emat} \newcommand{\collll}[4]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\ccollll}[4]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\colllll}[5]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\ccolllll}[5]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\red}[1]{{\color{red}#1}} \newcommand{\lra}[1]{\mbox{$\xrightarrow{#1}$}} \newcommand{\rank}{\textrm{rank}} \newcommand{\row}{\textrm{row}} \newcommand{\col}{\textrm{col}} \newcommand{\null}{\textrm{null}} \newcommand{\nullity}{\textrm{nullity}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \renewcommand{\Arg}{\operatorname{Arg}} \renewcommand{\arg}{\operatorname{arg}} \newcommand{\adj}{\textrm{adj}} \newcommand{\mystack}[2]{\genfrac{}{}{0}{0}{#1}{#2}} \newcommand{\mystackthree}[3]{\mystack{\mystack{#1}{#2}}{#3}} \newcommand{\qimplies}{\quad\implies\quad} \newcommand{\qtext}[1]{\quad\text{#1}\quad} \newcommand{\qqtext}[1]{\qquad\text{#1}\qquad} \newcommand{\smalltext}[1]{{\small\text{#1}}} \newcommand{\svec}[1]{\,\vec{#1}} \newcommand{\querytext}[1]{\toggle{\text{?}\vphantom{\text{#1}}}{\text{#1}}\endtoggle} \newcommand{\query}[1]{\toggle{\text{?}\vphantom{#1}}{#1}\endtoggle} \newcommand{\smallquery}[1]{\toggle{\text{?}}{#1}\endtoggle} \newcommand{\bv}{\mathbf{v}} %\require{AMScd} $

Announcements:

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.

Summary of Section 4.2: Determinants

For an $n \times n$ matrix $A$, write $A_{ij}$ for the matrix obtained from $A$ by deleting the $i$th row and the $j$th column. Then $\det A_{ij}$ is called the $(i,j)$-minor of $A$, and $$ C_{ij} = (-1)^{i+j} \det A_{ij} . $$ is called the $(i,j)$-cofactor of $A$.

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.

Better methods

Laplace Expansion is convenient when there are appropriately placed zeros in the matrix, but it is not good in general. It produces $n!$ different terms, which is waaaaay too slow for large matrices.

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.

New material: Section 4.2: Determinants (cont)

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.

Determinants and Invertibility

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?

Determinants and Matrix Operations

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.

Cramer's Rule

Cramer's Rule is a formula for solving a system of $n$ equations in $n$ unknowns. It is not efficient computationally, but is useful theoretically.

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.

Matrix Inverse using the Adjoint

The matrix $$ \kern-5ex \adj A := [C_{ji}] = [C_{ij}]^T = \bmat{cccc} C_{11} & C_{21} & \cdots & C_{n1} \\ C_{12} & C_{22} & \cdots & C_{n2} \\ \vdots & \vdots & \ddots & \vdots \\ C_{1n} & C_{2n} & \cdots & C_{nn} \emat $$ is called the adjoint of $A$.

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.