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

**Office hour:** Monday, 3:00-3:30, MC103B.

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

Here is an applet for practicing row reduction.

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

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:

- Find the leftmost column that is not all zeros.
- If the top entry is zero, exchange rows to make it nonzero.
- 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.
**For RREF, it is almost always best to do this now.** - Use the leading entry to create zeros below it, and
**above it for RREF**. - 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 $s$, $t$, etc. 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.

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

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

**Recall:** A vector $\vv$ is a **linear combination**
of vectors $\vv_1, \vv_2, \ldots, \vv_k$ if there exist scalars
$c_1, c_2, \ldots, c_k$ (called coefficients) such that
$$
c_1 \vv_1 + \cdots + c_k \vv_k = \vv .
$$

**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 $$ \kern-8ex \bmat{rr|r} 4 & 2 & 4 \\ 5 & 1 & 8 \\ 6 & 3 & 6 \emat \quad \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 & 6 \\ 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 & 6 \\
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:
$$
\href{javascript:divShow("system1");divHide("system2");divHide("system3")}{
\begin{aligned}
\phm 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.

$ \qquad\begin{aligned} \phm x + y\ &= 2\\ - x + y\ &= 4 \end{aligned} $

$\quad x \coll 1 {-1} + y \coll 1 1 = \coll 2 4$

$\quad \query{x = -1, \quad y = 3}$

If $\span(S) = \R^n$, then $S$ is called a **spanning set** for $\R^n$.

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

**Solution:** The span consists of every vector $\vx$ that can be
written as $\vx = s \vu$ for some scalar $s$. So it is the line through
the origin with direction vector $\vu$.

**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$?
They are not parallel, so intuitively 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
$$

**Note:** The word "span" is really just a fancy way of saying "all linear
combinations of these vectors".

**Question:** What is $\span(\coll 1 2)$? What is $\span(\coll 1 2, \coll 2 4)$?

**Question:** We saw that $\span(\coll 1 0, \coll 0 1) = \R^2$.
What is $\span(\coll 1 0, \coll 0 1, \coll 2 4)$?

**Question:** What vector is always in $\span(\vv_1, \vv_2, \ldots, \vv_k)$?

**Question:** Find some vectors that span
$\{ \collll x {2x} {3x} {4x} \mid x \in \R \}$.

**Question:** Find some vectors that span
$\{ \coll x y \mid y = x + 1 \}$.