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

**Midterm 1** is next Thursday (Oct 3), 7-8:30pm.
If you have a **conflict**, you should have already let me know!
Tell me after class if you haven't already.
See the missed exam section of
the course web page for policies, including for illness.
A **practice exam** is available from the course home page.
Last name A-Q must write in **NS1**, R-Z in **NS7**.

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

- Any rows that are entirely zero are at the bottom.
- 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:
$$
\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:
$$
\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
$$

- Exchange two rows.
- Multiply a row by a
**nonzero**constant. - Add a multiple of one row to another.

**Row reduction steps:**
(This technique is *crucial* for the whole course.)

(a) Find the leftmost column that is not all zeros.

(b) If the top entry is zero, exchange rows to make it nonzero.

(b') It may be convenient to scale this row to make the leading entry into a 1.

(c) Use the leading entry to create zeros below it.

(d) Cover up the row containing the leading entry, and repeat starting from step (a).

**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 (from text) on whiteboard:** Solve the system
$$
\begin{aligned}
\ph w - \ph x - y + 2 z &= \ph \, 1 \\
2 w - 2 x - y + 3 z &= \ph \, 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: $$ \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:

- If one of the rows is zero except for the last entry, then the system is **inconsistent**.

- If this doesn't happen, then the system is **consistent**, and Theorem 2.2 applies.

**Question:** What are the possible ranks of a $2 \times 3$ matrix?

- It is in row echelon form.
- The leading entry in each nonzero row is a 1 (called a
**leading 1**). - Each column containing a leading 1 is zero everywhere else.

**Row reduction to RREF:**
(This technique is *crucial* for the whole course.)

(a) Find the leftmost column that is not all zeros.

(b) If the top entry is zero, exchange rows to make it nonzero.

(b') **Scale this row to make the leading entry into a 1.**

(c) Use the leading entry to create zeros below it **and above it**.

(d) 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 whiteboard: 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 whiteboard:
%\qquad
%\toggle{\text{Solution}}{\text{Solution: } x = 1, y = 2, z = 2}\endtoggle
$$
Solution:
$$
\begin{aligned}
\bmat{rrr|r}
1 & 1 & 1 & 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{\mystackthree{R_1 + R_2}{-R_2}{R_3 - 2R_2}}
&\bmat{rrr|r}
1 & 0 & -2 & -3 \\
0 & 1 & 3 & 8 \\
0 & 0 & 6 & 12
\emat \\
\lra{\displaystyle\frac{1}{6}R_3}
&\bmat{rrr|r}
1 & 0 & -2 & -3 \\
0 & 1 & 3 & 8 \\
0 & 0 & 1 & 2
\emat \\
\lra{\mystack{R_1 + 2R_3}{R_2-3R_3}}
&\bmat{rrr|r}
1 & 0 & 0 & 1 \\
0 & 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.)

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

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

Look at Examples 2.14 and 2.15 in text for geometrical applications.

Here is an applet for practicing row reduction.

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