Math 1600B Lecture 2, Section 2, 8 Jan 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:

Read Section 1.2 for next class. Work through homework problems.

Lecture notes (this page) available from course web page. Also look for announcements there.

Office hour: today, 2:30-3:30, MC103B. Drop with any questions!

No tutorials this week. There is a quiz in tutorials next week.

Please read over syllabus, especially before e-mailing me with questions, as it covers all of the main points.

Let me know if the bookstore runs out of texts or combo packs.

Review of last lecture:

A vector can be represented by its list of components, e.g. $[1, 2, -1]$ is a vector in $\R^3$.
We write $\R^n$ for the set of all vectors with $n$ real components, e.g. $[1, 2, 3, 4, 5, 6, 7]$ is in $\R^7$.

We also often write vectors as column vectors, e.g. $\coll 1 2$.

Vector addition: $[u_1, \ldots, u_n] + [v_1, \ldots, v_n] := [u_1 + v_1, \ldots, u_n + v_n]$.
E.g. $[3, 2, 1] + [1, 0, -1] = [4, 2, 0]$.

Scalar multiplication: $c [u_1, \ldots, u_n] := [c u_1, \ldots, c u_n]$.

E.g. $2 [ 1 , 2, 3, 4, 5] = [2, 4, 6, 8, 10]$.

Zero vector: $\vec{0} := [0, 0, ..., 0]$.

Properties of vector operations: The parallelogram shows geometrically that vector addition is commutative: $\vec{u} + \vec{v} = \vec{v} + \vec{u}$.

Many other properties that hold for real numbers also hold for vectors: Theorem 1.1. But we'll see differences later.

New material:

An important real-world application:

Derive an equation for Inky's target on board.

Section 1.1, continued: Linear combinations

Definition: A vector $\vv$ is a linear combination of vectors $\vv_1, \vv_2, \ldots, \vv_k$ if there are scalars $c_1, c_2, \ldots, c_k$ so that \[ \vv = c_1 \vv_1 + \cdots + c_k \vv_k . \] The numbers $c_1, \ldots, c_k$ are called the coefficients. They are not necessarily unique.

Example: Is $\coll 1 {-1}$ a linear combination of $\coll 1 1$, $\coll 2 {-1}$ and $\coll 0 1$?

Yes, since \[ \coll 1 {-1} = 1 \coll 1 1 + 0 \coll 2 {-1} - 2 \coll 0 1 \qqtext{(Check!)} \]

Note: We also have \[ \coll 1 {-1} = -\frac{1}{3} \coll 1 1 + \frac{2}{3} \coll 2 {-1} + 0 \coll 0 1 \qqtext{(Check!)} \] and many more possibilities.

We will learn later how to find all solutions.

Example: Is $\coll 1 {-1}$ a linear combination of $\coll 1 0$ and $\coll 2 0$?

Example: Is $\coll 0 0$ a linear combination of $\coll 1 0$ and $\coll 2 0$?

Coordinates

Example: Express $\vw_1 = \coll 3 3$ as a linear combination of $\vu = \coll 2 1$ and $\vv = \coll {-1} 1$.

We can solve this by using $\vu$ and $\vv$ to make a new coordinate system in the plane. Use the board to show that $\vw_1 = 2 \vu + \vv$.

Similarly, show that $\vw_2 = \coll 4 {-1}$ can be expressed as $\vw_2 = \vu - 2 \vv$.

Note that in this case the coefficients are unique. In this situation, the coefficients are called the coordinates with respect to $\vu$ and $\vv$. So the coordinates of $\vw_1$ with respect to $\vu$ and $\vv$ are $2$ and $1$, and the coordinates of $\vw_2$ with respect to $\vu$ and $\vv$ are $1$ and $-2$.

Working in a different coordinate system is a powerful tool.

Binary vectors

$\Z_2 := \{ 0, 1 \}$

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

There are $\query{2^n}$ vectors in $\Z_2^n$.

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.