Read Section 2.3 for next class. Lots of new concepts in 2.3, so read ahead! Work through recommended homework questions.
Quiz 2 is this week, and will cover the material until the end of Monday's lecture, focusing on the material since the last quiz: Sections 1.3, 2.1 and part of 2.2.
Next office hour: today, 11:30-noon, MC103B.
Help Centers: Monday-Friday 2:30-6:30 in MC106.
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 $$
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: 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 put this in matrix notation and did row reduction: \[ \kern-6ex \bmat{rrrr|r} 1 & -1 & -1 & 2 & 1 \\ 2 & -2 & -1 & 3 & 3 \\ -1 & 1 & -1 & 0 & -3 \emat \longrightarrow \bmat{rrrr|r} \red{1} & -1 & -1 & 2 & 1 \\ 0 & 0 & \red{1} & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 \emat \] We then converted back to equations: \[ \kern-6ex \begin{aligned} \red{w} -x -y + 2 z \ &= 1 \\ \red{y} - \ph z \ &= 1 \end{aligned} \] The variables $w$ and $y$ are called leading variables, since they correspond to columns with a leading entry, and the other variables $x$ and $z$ are called free variables. We use back substitution to solve for the leading variables in terms of the free variables, and find \[ \kern-6ex \begin{aligned} z \ &= s \\ y \ &= 1 + z = 1 + s \\ x \ &= t \\ w \ &= x + y - 2z + 1 = t + 1 + s - 2s + 1 = 2 - s + t \end{aligned} \] So the complete solution is \[ \kern-6ex \begin{aligned} w \ &= 2 - s + t \\ x \ &= t \\ y \ &= 1 + s \\ z \ &= s \end{aligned} \text{ In vector form:}\quad \vx = \collll 2 0 1 0 + s \collll {-1} 0 1 1 + t \collll 1 1 0 0 \]
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:
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?
Or one can first go to REF, and then do the additional steps in bold.
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.)
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: A homogeneous system $[ A \mid \vec 0 \, ]$ is always consistent. Moreover, if there are $m$ equations and $n$ variables and $m < n$, then the system has infinitely many solutions.
Proof: The system is consistent because it has the zero solution. If $m < n$, we have $$ \rank(A) \leq m < n $$ so $$ \text{number of free variables} = n - \rank(A) > 0 . $$
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 reduced 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.
Example 2.13, if time: Continue Example 2.11 on board: get the matrix to reduced row echelon form before doing back substitution.
Here is an applet for practicing row reduction.
We aren't covering linear systems over $\Z_p$.