Math 1600B Lecture 9, Section 2, 24 Jan 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{\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:

Read Section 2.3 for next class. Work through recommended homework questions.

Next office hour: Monday, 1:30-2:30.

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

Partial review of last lecture:

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

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

Row reduction: getting a matrix into row echelon form

Here are operations on an augmented matrix that don't change the solution set. These 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:

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

New material

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.

Notation: The coefficient matrix $A$ of the system is the part of the augmented matrix excluding the right hand sides of the equations. We sometimes write $[ A \mid \vb \,]$ for the augmented matrix.

Note: The number of leading variables equals the number of nonzero rows in the row echelon form of the coefficient matrix, and from this we can calculate the number of free variables.

Definition: For any matrix $A$, the rank of $A$ is the number of nonzero rows in its row echelon form. It is written $\rank(A)$. (We'll see later that this is the same for all row echelon forms of $A$.)

We have observed:

Theorem 2.2: Let $A$ be the coefficient matrix of a linear system with $n$ variables. If the system is consistent, then $$ \text{number of free variables} = n - \rank(A) . $$ When there are 0 free variables, we have a unique solution.
When there are 1 or more free variables, we have infinitely many solutions.

Observe how this works in the above example and also in this example from last class: $$ \kern-4ex \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 $$ Here $\rank(A) = 3$ and $n = 3$, so there are $3 - 3 = 0$ free variables. That is, there is a unique solution.

Recall: Last time we saw how to tell whether the system is consistent or inconsistent from the row echelon form of the augmented matrix:

  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.

Question: What are the possible ranks of a $2 \times 3$ matrix $A$? If this matrix is the coefficient matrix of a linear system, how many solutions can there be?

Reduced row echelon form

Definition: A matrix is in reduced row echelon form if:
  1. It is in row echelon form.
  2. The leading entry in each nonzero row is a 1 (called a leading 1).
  3. Each column containing a leading 1 is zero everywhere else.
Example: Are the following systems in reduced row echelon form (RREF) and/or row echelon form (REF)? $$ \kern-9ex \small \mystack{ \bmat{rrr} 1 & 2 & 3 \\ 0 & 1 & 2 \emat }{ \querytext{REF} } \ \mystack{ \bmat{rrrr} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 2 \emat }{ \querytext{REF} } \ \mystack{ \bmat{rrrrrr} 0 & 1 & 3 & 0 & 4 & 0 \\ 0 & 0 & 0 & 1 & 5 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \emat }{ \querytext{REF $\red{\text{and}}$ RREF} } \ \mystack{ \bmat{rrrrr} 1 & 3 & 0 & 4 & 0 \\ 0 & 0 & 1 & 5 & 0 \\ 0 & 0 & 6 & 0 & 1 \emat }{ \querytext{neither} } $$ Facts: By performing row operators, you can always get a matrix into reduced row echelon form. What isn't so obvious is that the result is unique.

Row reduction to RREF: (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. Scale this row to make the leading entry into a 1.
  4. Use the leading entry to create zeros below it and above it.
  5. Cover up the row containing the leading entry, and repeat starting from step (a).

Or one can first go to REF, and then do the additional steps in bold.

Example 2.13: Continue Example 2.11 on board: get the matrix to reduced row echelon form before doing back substitution.

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

Example: Solve the system using Gauss-Jordan elimination: $$ \begin{aligned} \ph x + y + z &= 5 \\ 2 x + y - z &= 2 \\ x - y + z &= 1 \end{aligned} % Could delete solution below, and do it on board: %\qquad %\toggle{\text{Solution}}{\text{Solution: } x = 1, y = 2, z = 2}\endtoggle $$

Solution: $$ \kern-8ex \begin{aligned} \bmat{rrr|r} 1 & 1 & 1 & \phm 5 \\ 2 & 1 & -1 & 2 \\ 1 & -1 & 1 & 1 \emat &\lra{\mystack{R_2 - 2R_1}{R_3 - R_1}} \bmat{rrr|r} 1 & 1 & 1 & 5 \\ 0 & -1 & -3 & -8 \\ 0 & -2 & 0 & -4 \emat \\ \lra{\mystack{R_1 + R_2}{R_3 - 2R_2}} \bmat{rrr|r} 1 & 0 & -2 & -3 \\ 0 & -1 & -3 & -8 \\ 0 & 0 & 6 & 12 \emat &\lra{\quad \displaystyle -R_2 \quad\ \,} \bmat{rrr|r} 1 & 0 & -2 & -3 \\ 0 & \phm 1 & 3 & 8 \\ 0 & 0 & 6 & 12 \emat \\ \lra{\quad \displaystyle\frac{1}{6}R_3 \quad} \bmat{rrr|r} 1 & 0 & -2 & -3 \\ 0 & \phm 1 & 3 & 8 \\ 0 & 0 & 1 & 2 \emat &\lra{\mystack{R_1 + 2R_3}{R_2-3R_3}} \bmat{rrr|r} 1 & 0 & \phm 0 & \phm 1 \\ 0 & \phm 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \emat \\ \end{aligned} $$ So the new system is $$ \begin{aligned} x &= 1 \\ y &= 2 \\ z &= 2 \end{aligned} $$ which requires no further work. (Other systems will require parameters, or be inconsistent, of course.)

Homogeneous Systems

Definition: A system of linear equations is homogeneous if the constant term in each equation is zero.

Question: Is the following system consistent? $$ \begin{aligned} x + \ph y - \ph z = 0 \\ x - 2 y + \ph z = 0 \\ x + 4 y - 3 z = 0 \end{aligned} $$

Theorem 2.3:

Proof:

Note: If $m \geq n$ the system may have infinitely many solutions or it may have only the zero solution.

Example like 2.15: Let $\vp = \colll 1 0 0$, $\vq = \colll 0 3 2$, $\vu = \colll 1 1 2$ and $\vv = \colll 3 {-1} 2$. Determine whether the lines $\vx^{\strut} = \vp + t \vu$ and $\vx = \vq + t \vv$ intersect, and, if so, find their point of intersection.

Solution: We want to know whether there are parameters $\red{s}$ and $t$ so that $$ \vp + s \vu = \vq + t \vv $$ That is, $$ s \vu - t \vv = \vq - \vp $$ In components, this gives the system $$ \begin{aligned} s - 3 t &= -1 \\ s + \ph t &= \phm 3 \\ 2 s - 2 t &= \phm 2 \end{aligned} $$ Reduce to row echelon form: $$ \kern-8ex \begin{aligned} &\bmat{rr|r} 1 & -3 & -1 \\ 1 & 1 & 3 \\ 2 & -2 & 2 \emat \lra{\mystack{\scriptstyle R_2 - R_1}{\scriptstyle R_3 - 2 R_1}} \bmat{rr|r} 1 & -3 & -1 \\ 0 & 4 & 4 \\ 0 & 4 & 4 \emat \lra{R_3-R_2} \bmat{rr|r} 1 & -3 & -1 \\ 0 & 4 & 4 \\ 0 & 0 & 0 \emat \\ \lra{\frac{1}{4}R_3} &\bmat{rr|r} 1 & -3 & -1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \emat \lra{R_1 + 3 R_2\,} \bmat{rr|r} 1 & \phm 0 & \phm 2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \emat \end{aligned} $$ This gives $t = 1$ and $s = 2$.

Recall that $\vp = \colll 1 0 0$, $\vq = \colll 0 3 2$, $\vu = \colll 1 1 2$ and $\vv = \colll 3 {-1} 2$. Then $\vp + 2 \vu = \colll 3 2 4$ and $\vq + \vv = \colll 3 2 4$, so the lines intersect at that point.

Notes

Here is an applet for practicing row reduction.

We aren't covering linear systems over $\Z_p$.