Math 1600 Lecture 3, Section 2, 10 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.2 for next class, as well as the code vectors part of Section 1.4. (The rest of 1.4 will not be covered, and 1.3 will come after 1.4.) Work through recommended homework questions.

Tutorials start September 17, and include a quiz covering until next Monday's lecture. More details on Monday.

Tutorial sections are unbalanced. I encourage people in 003, 005 and 008 to switch to 009 (at the same time as 003). You can switch online today (Sep 10) and can switch via paper add/drop on Sep 11 and 12, 9:30-3:30, MC104.

003  W   9:30AM   KB-K103     42 !
009  W   9:30AM   UCC-65      12 *
008  W  11:30AM   UCC-60      44 !
006  W   3:30PM   UC-202      35
005  Th 11:30AM   SSC-3010    42 !
007  Th 12:30PM   MC-17       29
004  Th  2:30PM   UC-202      36

Lecture notes (this page) available from the course web page by clicking on the link. Answers to lots of administrative questions are available on the course web page as well.

Review of last lecture:

Many properties that hold for real numbers also hold for vectors in $\R^n$: Theorem 1.1. But we'll see differences later.

Definition: 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 $$ \vv = c_1 \vv_1 + \cdots + c_k \vv_k . $$ We also call the coefficients coordinates when we are thinking of the vectors $\vv_1, \vv_2, \ldots, \vv_k$ as defining a new coordinate system.

Binary vectors

$\Z_2 := \{ 0, 1 \}$, a set with two elements.

Multiplication is as usual.

Addition: $0 + 0 = 0$, $\ 0 + 1 = 1$, $\ 1 + 0 = 1$, $\ \red{1 + 1 = 0}$.

$\Z_2^n := $ vectors with $n$ components in $\Z_2$.

E.g. $[0, 1, 1, 0, 1] \in \Z_2^5$.

$[0,1,1] + [1,1,0] = \query{[1,0,1]}$ in $\Z_2^3$.

New material: Last bit of Section 1.1

Ternary vectors

$\Z_3 := \{ 0, 1, 2 \}$

To add and multiply, always take the remainder modulo $3$ at the end.

E.g. $2 + 2 = 4 = 1 \cdot 3 + \red{1}$, so $2 + 2 = 1 \pmod{3}$.

We write $\!\!\pmod{3}$ to indicate we are working in $\Z_3$.

Similarly, $1 + 2 = \query{0} \pmod{3}$ and $2 \cdot 2 = \query{1} \pmod{3}$.

$\Z_3^n := $ vectors with $n$ components in $\Z_3$.

$[0,1,2] + [1,2,2] = \query{[1,0,1]}$ in $\Z_3^3$.

There are $\query{3^n}$ vectors in $\Z_3^n$.

Vectors in $\Z_m^n$

$\Z_m := \{ 0, 1, 2, \ldots, m-1 \}$ with addition and multiplication modulo $m$.

E.g., in $\Z_{10}$, $\quad 8 \cdot 8 = 64 = 4 \pmod{10}$.

$\Z_m^n := $ vectors with $n$ components in $\Z_m$.

To find solutions to an equation such as $$ 6 x = 6 \pmod{8} $$ you can simply try all possible values of $x$. In this case, $1$ and $5$ both work, and no other value works.

Note that you can not in general divide in $\Z_m$, only add, subtract and multiply. For example, there is no solution to the following equation: $$ 2 x = 1 \pmod{4} $$ But there is a solution to $$ 2 x = 1 \pmod{5}, $$ namely $x = \query{3}$

Question: In $\Z_5$, what is $-2$?

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].$$ In Section 1.4, we will learn how error detection works for codes like this.

Most of this course will concern vectors with real components. Vectors in $\Z_m^n$ will just be used to study code vectors.

Section 1.2: Length and Angle: The Dot Product

Definition: The dot product of vectors $\vu$ and $\vv$ in $\R^n$ is the real number defined by $$ \vu \cdot \vv := u_1 v_1 + \cdots + u_n v_n . $$ Since $\vu \cdot \vv$ is a scalar, the dot product is sometimes called the scalar product, not to be confused with scalar multiplication $c \vv$.

The dot product will be used to define length, distance and angles in $\R^n$.

Example: For $\vu = [1, 0, 3]$ and $\vv = [2, 5, -1]$, we have $$ \vu \cdot \vv = 1 \cdot 2 + 0 \cdot 5 + 3 \cdot (-1) = 2 + 0 - 3 = -1 . $$

We can also take the dot product of vectors in $\Z_m^n$, by reducing the answer modulo $m$.

Example: For $\vu = [1, 2, 3]$ and $\vv = [2, 3, 4]$ in $\Z_5^3$, we have $$ \vu \cdot \vv = 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 = 2 + 6 + 12 = 20 = 0 \pmod{5}. $$ In $\Z_6^3$, the answer would be $\query{2.}$

Theorem 1.2: For vectors $\vu, \vv, \vw$ in $\R^n$ and $c$ in $\R$:
(a) $\ \vu \cdot \vv = \vv \cdot \vu$
(b) $\ \vu \cdot (\vv + \vw) = \vu \cdot \vv + \vu \cdot \vw$
(c) $\ (c \vu) \cdot \vv = c(\vu \cdot \vv) = \vu \cdot (c \vv)$
(d) $\ \vu \cdot \vu \geq 0$
(e) $\ \vu \cdot \vu = 0$ if and only if $\vu = \vec 0$

Again, very similar to how multiplication and addition of numbers works.

Explain (b) and (d) on board. (a) and (c) are explained in text.

Length from dot product

The length of a vector $\vv = [v_1, v_2]$ in $\R^2$ is $\sqrt{v_1^2 + v_2^2}$, using the Pythagorean theorem. (Sketch.) Notice that this is equal to $\sqrt{\vv \cdot \vv}$. This motivates the following definition:

Definition: The length or norm of a vector $\vv$ in $\R^n$ is the scalar $\|\vv\|$ defined by $$ \|\vv\| := \sqrt{\vv \cdot \vv} = \sqrt{v_1^2 + \cdots + v_n^2} . $$

Example: The length of $[1, 2, 3, 4]$ is $\sqrt{1^2 + 2^2 + 3^2 + 4^2} = \sqrt{30}$.

Note: $\|c \vv\| = |c| \|\vv\|$. (Explain on board.)

Definition: A vector of length 1 is called a unit vector.

The unit vectors in $\R^2$ form a circle. (Sketch.) Examples are $[ 1, 0 ]$, $[0, 1]$, $[\frac{-1}{\sqrt{2}}, \frac{1}{\sqrt{2}}]$, and lots more. The first two are denoted $\ve_1$ and $\ve_2$ and are called the standard unit vectors in $\R^2$.

The unit vectors in $\R^3$ form a sphere. The standard unit vectors in $\R^3$ are $\ve_1 = [1, 0, 0]$, $\ve_2 = [0, 1, 0]$ and $\ve_3 = [0, 0, 1]$.

More generally, the standard unit vectors in $\R^n$ are $\ve_1, \ldots, \ve_n$, where $\ve_i$ has a $1$ as its $i$th component and a $0$ for all other components.

Given any non-zero vector $\vv$, there is a unit vector in the same direction as $\vv$, namely $$ \frac{1}{\|\vv\|} \svv $$ This has length $1$ using the previous Note. (Sketch and example on board.) This is called normalizing a vector.

Theorem 1.5: The Triangle Inequality: For all $\vu$ and $\vv$ in $\R^n$, $$ \| \vu + \vv \| \leq \| \vu \| + \| \vv \| . $$

Theorem 1.5 is geometrically plausible, at least in $\R^2$ and $\R^3$. The book proves that it is true in $\R^n$ using Theorem 1.4, which we will discuss below.

Example: Let $\vu = [1,0]$ and $\vv = [3,4]$ in $\R^2$. Then $\vu + \vv = [1,0] + [3,4] = [4,4]$ and $$ \kern-4ex \| \vu + \vv \| = \| [4,4] \| = \sqrt{4^2 + 4^2} = \sqrt{32} \simeq 5.657 $$ and $$ \kern-4ex \| \vu \| + \| \vv \| = \sqrt{1^2 + 0^2} + \sqrt{3^2 + 4^2} = \sqrt{1} + \sqrt{25} = 1 + 5 = 6 $$

Distance from length

Thinking of vectors $\vu$ and $\vv$ as starting from the origin, we define the distance between them by the formula $$ \kern-9ex d(\vu, \vv) := \| \vu - \vv \| = \sqrt{(u_1 - v_1)^2 + \cdots + (u_n - v_n)^2}, $$ generalizing the formula for the distance between points in the plane.

Example: The distance between $\vu = [10, 10, 10, 10]$ and $\vv = [11, 11, 11, 11]$ is $$\sqrt{(-1)^2 + (-1)^2 + (-1)^2 + (-1)^2} = \sqrt{4} = 2 .$$

Angles from dot product

The unit vector in $\R^2$ at angle $\theta$ from the $x$-axis is $\vu = [\cos \theta, \sin \theta]$. Notice that $$ \kern-4ex \vu \cdot \vec e_1 = [\cos \theta, \sin \theta] \cdot [1, 0] = 1 \cdot \cos \theta + 0 \cdot \sin \theta = \cos \theta . $$ More generally, given vectors $\vu$ and $\vv$ in $\R^2$, one can show using the law of cosines that $$ \vu \cdot \vv = \| \vu \| \, \| \vv \| \, \cos \theta , $$ where $\theta$ is the angle between them (when drawn starting at the same point).

In particular, $|\vu \cdot \vv| \leq \| \vu \| \, \| \vv \|$, since $|\cos \theta| \leq 1$.

This holds in $\R^n$ as well, but we won't give the proof:

Theorem 1.4: The Cauchy-Schwarz Inequality: For all $\vu$ and $\vv$ in $\R^n$, $$ | \vu \cdot \vv | \leq \| \vu \| \, \| \vv \| . $$

We can therefore use the dot product to define the angle between two vectors $\vu$ and $\vv$ in $\R^n$ by the formula $$ \cos \theta := \frac{\vu \cdot \vv}{\| \vu \| \, \| \vv \|}, \quad \text{i.e.,} \quad \theta := \arccos \left( \frac{\vu \cdot \vv}{\| \vu \| \, \| \vv \|} \right), $$ where we choose $0 \leq \theta \leq 180^\circ$. This makes sense because the fraction is between -1 and 1.

To help remember the formula for $\cos \theta$, note that the denominator normalizes the two vectors to be unit vectors.