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.

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

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

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

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.

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

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

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

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.