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

**Midterm 1** is on Thursday (Oct 3), 7-8:30pm.
It covers until the end of Section 2.2, except for
linear systems over $\Z_m$.
A **practice exam** is available from the course home page.
Last name A-Q must write in **NS1**, R-Z in **NS7**.
See the missed exam section of
the course web page for policies, including for illness.

**Tutorials:** No quiz, focused on review. Take advantage of it!

**Office hour:** today, 1:30-2:30, MC103B.

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

Performing the following **elementary row operations** on the
augmented matrix doesn't change the solution set:

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

**Definition:** A matrix is in **row echelon form (REF)** if it satisfies:

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

**Definition:** A matrix is in **reduced row echelon form (RREF)** if:

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

We can always use the elementary row operations to get a matrix into REF and RREF:

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

For RREF, it is almost always best to do this now.

(c) Use the leading entry to create zeros below it, and above it for RREF.

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

**Note:** Row echelon form is not unique, but reduced row echelon form is.

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

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

**Back substitution:**
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.

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

**Note:** The number of leading variables equals the rank of the coefficient matrix.

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

**Consistency:** You can 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.

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

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

**Example:** Is $\colll 4 8 6$ a linear combination of
$\colll 4 5 6$ and $\colll 2 1 3$?

That is, can we find scalars $x$ and $y$ such that $$x \colll 4 5 6 + y \colll 2 1 3 = \colll 4 8 6 ?$$

Expanding this into components, this becomes a linear system
$$
\begin{aligned}
4 x + 2 y &= 4 \\
5 x + \ph y &= 8 \\
6 x + 3 y &= 6
\end{aligned}
$$
and we **already know** how to determine whether this system is consistent:
use **row reduction**!

The augmented matrix is $$ \bmat{rr|r} 4 & 2 & 4 \\ 5 & 1 & 8 \\ 6 & 3 & 6 \emat \qquad \Leftarrow \small\text{Note that the vectors appear as the columns here.} $$ This has row echelon form (work omitted) $$ \bmat{rr|r} 1 & 1/2 & 1 \\ 0 & -3/2 & 3 \\ 0 & 0 & 0 \emat . $$ From this, we can already see that the system is consistent, so the answer is YES.

If we want to find $x$ and $y$, we can use back substitution (maybe first going to RREF), and we find that $x = 2$ and $y = -2$ is the unique solution. (Do this at home.)

**Example:** Is $\colll 4 8 8$ a linear combination of
$\colll 4 5 6$ and $\colll 2 1 3$?

**Solution:** The augmented matrix
$$
\bmat{rr|r}
4 & 2 & 4 \\
5 & 1 & 8 \\
6 & 3 & \red{8}
\emat
$$
has row echelon form
$$
\bmat{rr|r}
1 & 1/2 & 1 \\
0 & -3/2 & 3 \\
0 & 0 & \red{2}
\emat
$$
and so the system is inconsistent and the answer is NO.

**Theorem 2.4:** A system with augmented matrix $[A \mid \vb \,]$ is
consistent if and only if $\vb$ is a linear combination of the columns of $A$.

This gives a **different** geometrical way to understand the solutions to
a system. For example, consider the following system from Lecture 7:
$$
\begin{aligned}
\ph x + y &= 2\\
- x + y &= 4
\end{aligned}
$$
We already know that we can interpret this as finding the point of
intersection of two lines in $\R^2$, and so in this case we get a unique solution
($x = -1$, $y = 3$).

But we can also interpret this as writing $\coll 2 4$ as a linear combination of $\coll 1 {-1}$ and $\coll 1 1$, which has a different geometric interpretation. (Pictures on whiteboard.)

Consider also these systems (on whiteboard): $$ \begin{aligned} \ph x - \ph y &= 2\\ 2 x - 2 y &= 4 \end{aligned} \qquad\qquad \begin{aligned} x + 2 y &= 2\\ x + 2 y &= 3 \end{aligned} $$

If $\span(S) = \R^n$, then $S$ is called a

**Example:** The vectors $\ve_1 = \coll 1 0$ and $\ve_2 = \coll 0 1$ are a spanning
set for $\R^2$, since for any vector $\vx = \coll a b$ we have
$$
a \coll 1 0 + b \coll 0 1 = \coll a b .
$$
Another way to see this is that the augmented matrix associated to $\ve_1$, $\ve_2$
and $\vx$ is
$$
\bmat{rr|r}
1 & 0 & a \\
0 & 1 & b
\emat
$$
which is already in RREF and is consistent.

Similarly, the standard unit vectors in $\R^n$ are a spanning set for $\R^n$.

**Example:** Find the span of $\vu = \colll 1 2 3$ and $\vv = \colll 4 5 6$.

**Solution:** The span consists of every vector $\vx$ that can be written as
$$
\vx = s \vu + t \vv
$$
for some scalars $s$ and $t$.
Since $\vu$ and $\vv$ are not parallel, this is the plane through the origin in $\R^3$
with direction vectors $\vu$ and $\vv$.

**Example:** What is the span of $\coll 1 3$ and $\coll 2 4$?
Intuitively, they are not parallel, so their linear combinations should fill
out all of $\R^2$.
We'll show how to see this algebraically, by row reducing the
augmented matrix
$$
\bmat{rr|r}
1 & 2 & a \\
3 & 4 & b
\emat
$$