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