# Math 1600A Lecture 8, Section 002

## Announcements:

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.

## Partial review of last lecture:

### Section 1.4: Applications: Code Vectors

For a simple error detecting code, you choose $m$ (which determines the allowed digits), $n$ (the number of digits in a code word), and a check vector $\vc \in \Z_m^n$. Then the valid words $\vv$ are those with $\vc \cdot \vv = 0$.

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

### Section 2.1: Systems of Linear Equations

Definition: A system of linear equations is a finite set of linear equations, each with the same variables. A solution to the system is a vector that satisfies all of the equations.

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.

### Solving a system

Example: Here is a system, along with its augmented matrix: \begin{aligned} \ph x - \ph y - \ph z &= 2 \\ 3 x - 3 y + 2 z &= 16 \\ 2 x - \ph y + \ph z &= 9 \end{aligned} \qquad\qquad \bmat{rrr|r} 1 & -1 & -1 & 2 \\ 3 & -3 & 2 & 16 \\ 2 & -1 & 1 & 9 \emat Geometrically, solving it corresponds to finding the points where three planes in $\R^3$ intersect.

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!

## New material: Section 2.2: Direct Methods for Solving Linear Systems

In general, we won't always get our system into triangular form. What we aim for is:

Definition: A matrix is in row echelon form if it satisfies:

1. Any rows that are entirely zero are at the bottom.
2. 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.

### Row reduction: getting a matrix into row echelon form

Here are operations on an augmented matrix that don't change the solution set. There are called the elementary row operations.
1. Exchange two rows.
2. Multiply a row by a nonzero constant.
3. Add a multiple of one row to another.
We can always use these operations to get a matrix into row echelon form.

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.