Math 1600A Lecture 26, Section 2, 11 Nov 2013

$ \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{\svec}[1]{\,\vec{#1}} \newcommand{\query}[1]{\toggle{\text{?}\vphantom{#1}}{#1}\endtoggle} \newcommand{\smallquery}[1]{\toggle{\text{?}}{#1}\endtoggle} $

Announcements:

Today we finish 4.2. Read Section 4.3 for Wednesday.
Work through recommended homework questions.

Tutorials: No quiz this week, just review.
Office hour: Monday, 1:30-2:30, MC103B.
Help Centers: Monday-Friday 2:30-6:30 in MC 106.

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 $\red{\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$. (Despite what I said in class, the above is correct.)

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-6ex \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, 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.

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 & 4 & 1 & 2 \\ 2 & 2 & 12 & 8 \\ 1 & 2 & 3 & 9 \emat$. On whiteboard.

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

Row reduction of an $n \times n$ matrix requires roughly $n^3$ operations in general, which is much less than $n$ factorial. Note that you can even mix and match row and column operations, if it simplifies the work.

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.

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 whiteboard.

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 whiteboard: 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.

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 $$

I will explain this next lecture.