Math 1600 Lecture 5, Section 2, 15 Sep 2014

$ \newcommand{\bdmat}[1]{\left|\begin{array}{#1}} \newcommand{\edmat}{\end{array}\right|} \newcommand{\bmat}[1]{\left[\begin{array}{#1}} \newcommand{\emat}{\end{array}\right]} \newcommand{\coll}[2]{\bmat{r} #1 \\ #2 \emat} \newcommand{\ccoll}[2]{\bmat{c} #1 \\ #2 \emat} \newcommand{\colll}[3]{\bmat{r} #1 \\ #2 \\ #3 \emat} \newcommand{\ccolll}[3]{\bmat{c} #1 \\ #2 \\ #3 \emat} \newcommand{\collll}[4]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\ccollll}[4]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \emat} \newcommand{\colllll}[5]{\bmat{r} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\ccolllll}[5]{\bmat{c} #1 \\ #2 \\ #3 \\ #4 \\ #5 \emat} \newcommand{\red}[1]{{\color{red}#1}} \newcommand{\lra}[1]{\mbox{$\xrightarrow{#1}$}} \newcommand{\rank}{\textrm{rank}} \newcommand{\row}{\textrm{row}} \newcommand{\col}{\textrm{col}} \newcommand{\null}{\textrm{null}} \newcommand{\nullity}{\textrm{nullity}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \renewcommand{\Arg}{\operatorname{Arg}} \renewcommand{\arg}{\operatorname{arg}} \newcommand{\adj}{\textrm{adj}} \newcommand{\mystack}[2]{\genfrac{}{}{0}{0}{#1}{#2}} \newcommand{\mystackthree}[3]{\mystack{\mystack{#1}{#2}}{#3}} \newcommand{\qimplies}{\quad\implies\quad} \newcommand{\qtext}[1]{\quad\text{#1}\quad} \newcommand{\qqtext}[1]{\qquad\text{#1}\qquad} \newcommand{\svec}[1]{\,\vec{#1}} \newcommand{\query}[1]{\toggle{\text{?}\vphantom{#1}}{#1}\endtoggle} \newcommand{\smallquery}[1]{\toggle{\text{?}}{#1}\endtoggle} \newcommand{\bv}{\mathbf{v}} %\require{AMScd} $

Announcements:

Continue reading Section 1.3 and also the Exploration on cross products for next class. Work through recommended homework questions.

Quiz 1 this week in tutorials. Quiz 1 will cover Sections 1.1, 1.2 and the code vectors part of 1.4. It does not cover the Exploration after Section 1.2. See last lecture for how they run.

Office hours: Monday, 3:00-3:30 and Wednesday, 11:30-noon, MC103B.

Help Centers: Monday-Friday 2:30-6:30 in MC 106 starting Wednesday, September 17. Extra Help Centers: Today and tomorrow (Sept 15 and 16), 4-5pm, MC106.

Review: Section 1.4: Applications: Code Vectors

Example 1.37: A code for rover commands: $$ \small\kern-8ex \textrm{forward} = [0,0,0], \quad \textrm{back} = [0,1,1], \quad \textrm{left} = [1,0,1], \quad \textrm{right} = [1,1,0]. $$ If any single bit (binary digit, a 0 or a 1) is flipped during transmission, the Mars rover will notice the error, since all of the code vectors have an even number of 1s. It could then ask for retransmission of the command.

This is called an error-detecting code.

In vector notation, we replace a vector $\vb = [v_1, v_2, \ldots, v_n]$ with the vector $\vv = [v_1, v_2, \ldots, v_n, \red{d}]$ such that $\vec 1 \cdot \vv = 0 \pmod{2}$, where $\vec 1 = [1, 1, \ldots, 1]$.

Exactly the same idea works for vectors in $\Z_3^n$; see Example 1.39 in the text.

Note: One problem with the above scheme is that transposition errors are not detected: if we want to send $[0, 1, 1]$ but the first two bits are exchanged, the rover receives $[1, 0, 1]$, which is also a valid command. We'll see codes that can detect transpositions.

New material

Example 1.40 (UPC Codes): The Univeral Product Code (bar code) on a product is a vector in $\Z_{10}^{12}$, such as $$\vu = [6,7,1,8,6,0,0,1,3,6,2,4].$$ Instead of using $\vec 1$ as the check vector, UPC uses $$ \vc = [ 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1] .$$ The last digit is chosen so that $\vc \cdot \vu = 0 \pmod{10}$.

For example, if we didn't know the last digit of $\vu$, we could compute $$ \vc \cdot [6,7,1,8,6,0,0,1,3,6,2,d] = \cdots = 6 + d \pmod{10} $$ and so we would find that we need to take $d = 4$, since $6 + 4 = 0 \pmod{10}$.

This detects any single error. The pattern in $\vc$ was chosen so that it detects many transpositions, but it doesn't detect when digits whose difference is 5 are transposed. For example, $3 \cdot 5 + 1 \cdot 0 = 15$ and $3 \cdot 0 + 1 \cdot 5 = 5$, and these are the same modulo $10$.

Example 1.41 (ISBN Codes): ISBN codes use vectors in $\Z_{11}^{10}$. The check vector is $\vc = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]$. Because 11 is a prime number, this code detects all single errors and all single transposition errors. See text for a worked example.

Summary: To create a 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$. If $\vc$ ends in a $1$, then you can always choose the last digit of $\vv$ to make it valid.

Note: This kind of code can only reliably detect one error, but more sophisticated codes can detect multiple errors. There are even error-correcting codes, which can correct multiple errors in a transmission without needing it to be resent. In fact, you can drill small holes in a CD, and it will still play the entire content perfectly.

Question: The Dan code uses vectors in $\Z_4^3$ with check vector $\vc = [3,2,1]$. Find the check digit $d$ in the code word $\vv = [2, 2, d]$.

Solution: We compute $$ \kern-4ex \begin{aligned} \vc \cdot \vv = [3,2,1]\cdot [2,2,d] &= 3 \cdot 2 + 2 \cdot 2 + 1 \cdot d \\ &= 10 + d = 2 + d \pmod{4} \end{aligned} $$ To make $\vc \cdot \vv = 0 \pmod{4}$, we choose $d = 2$.

This is the end of the material for quiz 1. (We aren't covering force vectors.)

Section 1.3: Lines and planes in $\R^2$ and $\R^3$

[These notes are a summary of the material, which will be supplemented by some diagrams on the board.]

We study lines and planes because they come up directly in applications, but also because the solutions to many other types of problems can be expressed using the language of lines and planes.

Lines in $\R^2$ and $\R^3$

Given a line $\ell$, we want to find equations that tell us whether a point $(x,y)$ or $(x,y,z)$ is on the line. We'll write $\vx = [x, y]$ or $\vx = [x, y, z]$ for the position vector of the point, so we can use vector notation.

The vector form of the equation for $\ell$ is: $$ \vx = \vp + t \vd $$ where $\vp$ is the position vector of a point on the line, $\vd$ is a vector parallel to the line, and $t \in \R$. This is concise and works in $\R^2$ and $\R^3$.

If we expand the vector form into components, we get the parametric form of the equations for $\ell$: $$ \begin{aligned} x\ &= p_1 + t d_1\\ y\ &= p_2 + t d_2\\ ( z\ &= p_3 + t d_3 \quad \text{if we are in $\R^3$}) \end{aligned} $$

Lines in $\R^2$

There are additional ways to describe a line in $\R^2$.

The normal form of the equation for $\ell$ is: $$ \vn \cdot (\vx - \vp) = 0 \quad\text{or}\quad \vn \cdot \vx = \vn \cdot \vp , $$ where $\vn$ is a vector that is normal = perpendicular to $\ell$.

If we write this out in components, with $\vn = [a, b]$, we get the general form of the equation for $\ell$: $$ a x + b y = c, $$ where $c = \vn \cdot \vp$. When $b \neq 0$, this can be rewritten as $y = m x + k$, where $m = -a/b$ and $k=c/b$.

Note: All of these simplify when the line goes through the origin, as then you can take $\vp = \vec 0$.

Example: Find all four forms of the equations for the line in $\R^2$ going through $A = [1,1]$ and $B = [3,2]$.

Note: None of these equations is unique, as $\vp$, $\vd$ and $\vn$ can all change. The general form is closest to being unique: it is unique up to an overall scale factor.

Lines in $\R^3$

Most of the time, one uses the vector and parametric forms above. But there is also a version of the normal and general forms. To specify the direction of a line in $\R^3$, it is necessary to specify two non-parallel normal vectors $\vn_1$ and $\vn_2$. Then the normal form is $$ \kern-6ex \begin{aligned} \vn_1 \cdot \vx\ &= \vn_1 \cdot \vp \qquad{\small\text{typo in book in Table 1.3:}}\\ \vn_2 \cdot \vx\ &= \vn_2 \cdot \vp \qquad{\small\text{there should be no subscripts on $\vp$}} \end{aligned} $$ When expanded into components, this gives the general form: $$ \begin{aligned} a_1 x + b_1 y + c_1 z\ &= d_1,\\ a_2 x + b_2 y + c_2 z\ &= d_2. \end{aligned} $$ Since both equations must be satisfied, this can be interpreted as the intersection of two planes. (We'll discuss planes in a second.)

Question: What are the pros and cons of the different ways of describing a line?

Planes in $\R^3$

Normal form: $$ \vn \cdot (\vx - \vp) = 0 \quad\text{or}\quad \vn \cdot \vx = \vn \cdot \vp . $$ This is exactly like the normal form for the equation for a line in $\R^2$.
When expanded into components, it gives the general form: $$ a x + b y + c z = d, $$ where $\vn = [a, b, c]$ and $d = \vn \cdot \vp$.