Math 1600 Lecture 8, Section 2, 22 Sep 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{\svec}[1]{\,\vec{#1}} \newcommand{\query}[1]{\toggle{\text{?}\vphantom{#1}}{#1}\endtoggle} \newcommand{\smallquery}[1]{\toggle{\text{?}}{#1}\endtoggle} \newcommand{\bv}{\mathbf{v}} %\require{AMScd} $

Announcements:

Continue reading Section 2.2 for next class. Work through recommended homework questions.

Quiz 2 is this week, and will cover the material until the end of today's lecture, focusing on the material since the last quiz: Sections 1.3, 2.1 and part of 2.2.

Next office hour: today, 3:00-3:30.

Help Centers: Monday-Friday 2:30-6:30 in MC 106.

Partial review of last lecture:

Section 2.1: Systems of Linear Equations

Definition: A system of linear equations is a finite set of linear equations, each with the same variables. A solution to the system is a vector that satisfies all of the equations.

Example: $ \begin{aligned} x + y\ &= 2\\ -x + y\ &= 4 \end{aligned} $

$[1, 1]$ is not a solution, but $[-1, 3]$ is. Geometrically, this corresponds to finding the intersection of two lines in $\R^2$.

A system is consistent if it has one or more solutions, and inconsistent if it has no solutions. We'll see later that a consistent system always has either one solution or infinitely many.

Solving a system

Example: Here is a system, along with its augmented matrix: $$ \kern-6ex \begin{aligned} \ph x - \ph y - \ph z\ &= 2 \\ 3 x - 3 y + 2 z\ &= 16 \\ 2 x - \ph y + \ph z\ &= 9 \end{aligned} \qquad\qquad \bmat{rrr|r} 1 & -1 & -1 & 2 \\ 3 & -3 & 2 & 16 \\ 2 & -1 & 1 & 9 \emat $$ Geometrically, solving it corresponds to finding the points where three planes in $\R^3$ intersect.

We solved it by doing row operations, such as replacing $R_2$ with $R_2 - 3 R_1$ or exchanging rows 2 and 3 until we got it to the form: $$ \kern-6ex \begin{aligned} \ph x - \ph y - \ph z\ &= 2 \\ y + 3 z\ &= 5 \\ 5 z\ &= 10 \end{aligned} \qquad\qquad \bmat{rrr|r} 1 & -1 & -1 & 2 \\ 0 & 1 & 3 & 5 \\ 0 & 0 & 5 & 10 \\ \emat $$ This system is easy to solve, because of its triangular structure. The method is called back substitution: $$ \begin{aligned} z\ &= 2\\ y\ &= 5 - 3z = 5 - 6 = -1\\ x\ &= 2 + y + z = 2 - 1 + 2 = 3. \end{aligned} $$ So the unique solution is $[3, -1, 2]$. We can check this in the original system to see that it works!

Question: Solve the system $$ \begin{aligned} 2 x + 3 y\ &= 2 \\ x + 2 y\ &= 2 \end{aligned} $$ geometrically and algebraically.

New material

Question: How many solutions does the system $$ \begin{aligned} 2 x + 3 y\ &= 2 \\ x + 2 y\ &= 2 \\ x + 4 y\ &= 2 \end{aligned} $$ have?

Section 2.2: Direct Methods for Solving Linear Systems

In general, we won't always get our system into triangular form. What we aim for is:

Definition: A matrix is in row echelon form if it satisfies:
  1. Any rows that are entirely zero are at the bottom.
  2. In each nonzero row, the first nonzero entry (called the leading entry) is further to the right than any leading entries above it.

Example: These matrices are in row echelon form: $$ \kern-6ex \bmat{rrr} \red{3} & 2 & 0\\ 0 & \red{-1} & 2\\ 0 & 0 & 0 \emat \qquad \bmat{rrr} \red{3} & 2 & 0\\ 0 & \red{-1} & 2\\ 0 & 0 & \red{4} \emat \qquad \bmat{rrrrr} 0 & \red{3} & 2 & 0 & 4 \\ 0 & 0 & 0 & \red{-1} & 2\\ 0 & 0 & 0 & 0 & \red{4} \emat $$

Example: These matrices are not in row echelon form: $$ \kern-6ex \bmat{rrr} {\bf 0} & {\bf 0} & {\bf 0} \\ \red{3} & 2 & 0\\ 0 & \red{-1} & 2\\ \emat \qquad \bmat{rrr} \red{3} & 2 & 0\\ 0 & \red{-1} & 2\\ 0 & {\bf 2} & 4 \emat \qquad \bmat{rrrrr} 0 & \red{3} & 2 & 0 & 4 \\ 0 & 0 & 0 & \red{-1} & 2\\ 0 & 0 & {\bf 2} & 0 & 4 \emat $$ This terminology makes sense for any matrix, but we will usually apply it to the augmented matrix of a linear system. The conditions apply to the entries to the right of the line as well.

Question: For a $2 \times 3$ matrix, in what ways can the leading entries be arranged?

Just as for triangular systems, we can solve systems in row echelon form using back substitution.

Example: Solve the system whose augmented matrix is: $$ \bmat{rrr|r} \red{3} & 2 & 2 & 0\\ 0 & 0 & \red{-1} & 2\\ 0 & 0 & 0 & 0 \emat $$ How many variables? How many equations? Solution on board.

Example: Solve the system whose augmented matrix is: $$ \bmat{rr|r} \red{3} & 2 & 0\\ 0 & \red{-1} & 2\\ 0 & 0 & \red{4} \emat $$ How many variables? How many equations?

Note: This is the general pattern for an augmented matrix in row echelon form:

  1. If one of the rows is zero except for the last entry, then the system is inconsistent.
  2. If this doesn't happen, then the system is consistent.

Row reduction: getting a matrix into row echelon form

Here are operations on an augmented matrix that don't change the solution set. There are called the elementary row operations.
  1. Exchange two rows.
  2. Multiply a row by a nonzero constant.
  3. Add a multiple of one row to another.
We can always use these operations to get a matrix into row echelon form.

Example on board: Reduce the given matrix to row echelon form: $$ \bmat{rrr} -2 & 6 & -7 \\ 3 & -9 & 10 \\ 1 & -3 & 3 \emat $$ Note that there are many ways to proceed, and the row echelon form is not unique.

Row reduction steps: (This technique is crucial for the whole course.)
  1. Find the leftmost column that is not all zeros.
  2. If the top entry is zero, exchange rows to make it nonzero.
  3. (Optional) It may be convenient to scale this row to make the leading entry into a 1, or to exchange rows to get a 1 here.
  4. Use the leading entry to create zeros below it.
  5. Cover up the row containing the leading entry, and repeat starting from step (a).

Note that for a random matrix, row reduction will often lead to many awkward fractions. Sometimes, by choosing the appropriate operations, one can avoid some fractions, but sometimes they are inevitable.

Example: Here's another example: $$ \begin{aligned} \bmat{rrrr} 0 & 4 & 2 & 3 \\ 2 & 4 & -2 & 1 \\ -3 & 2 & 2 & 1/2 \\ 0 & 0 & 10 & 8 \emat \xrightarrow{R_1 \leftrightarrow R_2} &\bmat{rrrr} \red 2 & \red 4 & \red{-2} & \red 1 \\ \red 0 & \red 4 & \red 2 & \red 3 \\ -3 & 2 & 2 & 1/2 \\ 0 & 0 & 10 & 8 \emat \\ \lra{\frac{1}{2}R_1} \bmat{rrrr} \red 1 & \red 2 & \red{-1} & \red{1/2} \\ 0 & 4 & 2 & 3 \\ -3 & 2 & 2 & 1/2 \\ 0 & 0 & 10 & 8 \emat \lra{R_3 + 3R_1} &\bmat{rrrr} \phm 1 & 2 & -1 & 1/2 \\ 0 & 4 & 2 & 3 \\ \red 0 & \red 8 & \red{-1} & \red 2 \\ 0 & 0 & 10 & 8 \emat \\ \lra{R_3 - 2R_2} \bmat{rrrr} \phm 1 & 2 & -1 & 1/2 \\ 0 & 4 & 2 & 3 \\ 0 & \red 0 & \red{-5} & \red{-4} \\ 0 & 0 & 10 & 8 \emat \lra{R_4 + 2R_3} &\bmat{rrrr} \phm 1 & 2 & -1 & 1/2 \\ 0 & 4 & 2 & 3 \\ 0 & 0 & -5 & -4 \\ 0 & 0 & \red 0 & \red 0 \emat \\ \end{aligned} $$

Example on board, if time: $\bmat{rrr} 2 & 4 & 6 \\ 1 & 2 & 4 \\ -3 & -6 & 4 \emat$

Gaussian elimination: This means to do row reduction on the augmented matrix of a linear system until you get to row echelon form, and then use back substitution to find the solutions.

Example 2.11 on board: Solve the system $$ \begin{aligned} \ph w - \ph x - y + 2 z \ &= \phm 1 \\ 2 w - 2 x - y + 3 z \ &= \phm 3 \\ - w + \ph x - y \phantom{{} + 3 z}\ &= -3 \end{aligned} $$ We call the variables corresponding to a column with a leading entry the leading variables, and the remaining variables the free variables. We solve for the leading variables in terms of the free variables, and assign parameters to the free variables.