More texts, solutions manuals and packages
**have arrived**!

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

**Quiz 2** is this week, and will cover the material until the end of
Section 1.4.

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

**Office hour:** today, 12:30-1:30, MC103B.
Also, if you can't make it to my office hours, feel free to attend Hugo Bacard's
office hours, listed on the course home
page.

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

**Example 1.40 (UPC Codes):**
The Univeral Product Code on a product is a vector in $\Z_{10}^{12}$.
The last digit is chosen so that $\vc \cdot \vu = 0 \pmod{10}$, where
$$ \vc = [ 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1] $$
is the **check vector**.

For example, we can compute the check digit for $$ \vu = [ 1, 2, 1, 3, 4, 2, 1, 9, 1, 1, 1, d] $$ to be $d = 6$ (on whiteboard).

And we can tell that $$ \vv = [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ] $$ is not a valid code word, since $\vc \cdot \vv = 4(6) = 24 = 4 \pmod{10}$.

**Example:**
$$
\begin{aligned}
x + y &= 2\\
-x + y &= 4
\end{aligned}
$$
$[1, 1]$ is not a solution, but $[-1, 3]$ is.
Geometrically, this corresponds to finding the intersection of two
lines in $\R^2$.

A system is **consistent** if it has one or more solutions,
and **inconsistent** if it has no solutions.
We'll see later that a consistent system always has either one
solution or infinitely many.

We solved it by doing **row operations**, such as replacing row 2
with row 2 - 3(row 1) or exchanging rows 2 and 3 until we got it
to the form:
$$
\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
$$
This system is easy to solve, because of its **triangular** structure.
The method is called **back substitution**:
$$
\begin{aligned}
z &= 2\\
y &= 5 - 3z = 5 - 6 = -1\\
x &= 2 + y + z = 2 - 1 + 2 = 3.
\end{aligned}
$$
So the unique solution is $[3, -1, 2]$.
We can **check this** in the original system to see that it works!

**Definition:** A matrix is in **row echelon form** 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.

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

**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
$$
This terminology makes sense for any matrix, but we will usually apply
it to the augmented matrix of a linear system. The conditions apply
to the entries to the right of the line as well.

**Question:** For a $2 \times 3$ matrix, in what ways can the leading entries
be arranged?

Just as for triangular systems, we can solve systems in row echelon form using back substitution.

**Example:** Solve the system whose augmented matrix is:
$$
\bmat{rrr|r}
\red{3} & 2 & 2 & 0\\
0 & 0 & \red{-1} & 2\\
0 & 0 & 0 & 0
\emat
$$
How many variables? How many equations? Solution on whiteboard.

**Example:** Solve the system whose augmented matrix is:
$$
\bmat{rr|r}
\red{3} & 2 & 0\\
0 & \red{-1} & 2\\
0 & 0 & \red{4}
\emat
$$
How many variables? How many equations?

The last row of the matrix corresponds to the equation
$0 x + 0 y = 4$, i.e. $0 = 4$, which is never true.
So there are **no** solutions to this system.

**Note:**This is the general pattern for an augmented matrix in row echelon form:

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

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

**Example on whiteboard:** Reduce the given matrix to row echelon form:
$$
\bmat{rrr}
-2 & 6 & -7 \\
3 & -9 & 10 \\
1 & -3 & 3
\emat
$$
Note that there are many ways to proceed, and the row echelon form is not unique.

**Example:** Here's another example:
$$
\begin{aligned}
\bmat{rrrr}
0 & 4 & 2 & 3 \\
2 & 4 & -2 & 1 \\
-3 & 2 & 2 & 1/2 \\
0 & 0 & 10 & 8
\emat
\xrightarrow{R_1 \leftrightarrow R_2}
&\bmat{rrrr}
\red 2 & \red 4 & \red{-2} & \red 1 \\
\red 0 & \red 4 & \red 2 & \red 3 \\
-3 & 2 & 2 & 1/2 \\
0 & 0 & 10 & 8
\emat \\
\lra{\frac{1}{2}R_1}
&\bmat{rrrr}
\red 1 & \red 2 & \red{-1} & \red{1/2} \\
0 & 4 & 2 & 3 \\
-3 & 2 & 2 & 1/2 \\
0 & 0 & 10 & 8
\emat \\
\lra{R_3 + 3R_1}
&\bmat{rrrr}
1 & 2 & -1 & 1/2 \\
0 & 4 & 2 & 3 \\
\red 0 & \red 8 & \red{-1} & \red 2 \\
0 & 0 & 10 & 8
\emat \\
\lra{R_3 - 2R_2}
&\bmat{rrrr}
1 & 2 & -1 & 1/2 \\
0 & 4 & 2 & 3 \\
0 & \red 0 & \red{-5} & \red{-4} \\
0 & 0 & 10 & 8
\emat \\
\lra{R_4 + 2R_3}
&\bmat{rrrr}
1 & 2 & -1 & 1/2 \\
0 & 4 & 2 & 3 \\
0 & 0 & -5 & -4 \\
0 & 0 & \red 0 & \red 0
\emat \\
\end{aligned}
$$

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

Note that for a random matrix, row reduction will often lead to many awkward fractions.