Today we finish Section 3.5 and start modular arithmetic and Section 8.1. Continue reading Section 8.1 (e-book only; or 1.4 in 3rd edition) and start Section 3.6. Work through suggested exercises.
Homework 7 is on WeBWorK and is due on today at 11:55pm. No homework next week.
Math Help Centre: M-F 12:30-5:30 in PAB48/49 and online 6pm-8pm.
My next office hour is today 2:30-3:20 in MC130.
The midterm is on Saturday, November 9, 2-4pm. It will cover until the end of Section 3.5. Old midterms are on OWL.
Midterm Review sessions: Nov 6 and 7, 4:30-5:30pm, UCC146. Bring questions.
Theorem 3.23: Let $S$ be a subspace of $\R^n$. Then any two bases for $S$ have the same number of vectors.
Definition: The number of vectors in a basis for a subspace $S$ is called the dimension of $S$, denoted $\dim S$.
We say that the dimension of the zero subspace $\{ \vec 0 \}$ is $0$.
We call the dimension of the null space the nullity of $A$ and write $\nullity(A) = \dim \null(A)$. This is what we called the "number of free variables" in Chapter 2.
Theorems 3.24 and 3.26: Let $A$ be an $m \times n$ matrix. Then $$ \dim \row(A) = \dim \col(A) = \rank(A) $$ and $$ \rank(A) + \nullity(A) = n . $$
Theorem 3.27:
Let $A$ be an $n \times n$ matrix. The following are equivalent:
a. $A$ is invertible.
b. $A \vx = \vb$ has a unique solution for every $\vb \in \R^n$.
c. $A \vx = \vec 0$ has only the trivial (zero) solution.
d. The reduced row echelon form of $A$ is $I_n$.
e. $A$ is a product of elementary matrices.
f. $\rank(A) = n$
g. $\nullity(A) = 0$
h. The columns of $A$ are linearly independent.
i. The columns of $A$ span $\R^n$.
j. The columns of $A$ are a basis for $\R^n$.
(d) $\iff$ (f): the only $n \times n$ matrix in row echelon form with $n$ nonzero rows is $I_n$.
(f) $\iff$ (g): follows from $\rank(A) + \nullity(A) = n$.
(c) $\iff$ (h): easy.
(i) $\implies$ (f) $\implies$ (d) $\implies$ (b) $\implies$ (i): Explain.
(h) and (i) $\iff$ (j): Clear.
In fact, since $\rank(A) = \rank(A^T)$, all of the statements are also equivalent to the statements with $A$ replaced by $A^T$. In particular, we can add the following:
k. The rows of $A$ are linearly independent.
l. The rows of $A$ span $\R^n$.
m. The rows of $A$ are a basis for $\R^n$.
Example 3.52: Show that the vectors $\colll 1 2 3$, $\colll {-1} 0 1$ and $\colll 4 9 7$ form a basis for $\R^3$.
Solution: By parts (j) and (f), it's enough to show that the matrix \[ A = \bmat{rrr} 1 & -1 & 4 \\ 2 & 0 & 9 \\ 3 & 1 & \phantom{-}7 \emat \] has rank 3. It row reduces to \[ R = \bmat{rrr} 1 & -1 & 4 \\ 0 & 2 & 1 \\ 0 & 0 & -9 \emat \] which is in row echelon form, so $A$ has rank 3.
Note: We are not covering Theorem 3.28.
Theorem 3.29: For every vector $v$ in $S$, there is exactly one way to write $v$ as a linear combination of the vectors in $\cB$: $$ \vv = c_1 \vv_1 + \cdots + c_k \vv_k $$
Proof: Try to work it out yourself! It's a good exercise.$\quad\Box$
We call the coefficients $c_1, c_2, \ldots, c_k$ the coordinates of $\vv$ with respect to $\cB$, and write $$ [\vv]_{\cB} = \ccollll {c_1} {c_2} {\vdots} {c_k} $$ We write the coordinates in the same order as the vectors in the basis.
We already intuitively understood this theorem in the case where $S$ is a plane through the origin in $\R^3$. Here's an example of this case:
Example: Let $S$ be the plane through the origin in $\R^3$ spanned by $\vv_1 = \colll 1 2 3$ and $\vv_2 = \colll 4 5 6$, so $\cB = \{ \vv_1, \vv_2 \}$ is a basis for $S$. Let $\vv = \colll 6 9 {12}$. Then $\vv = 2 \vv_1 + 1 \vv_2,$ so $[\vv]_{\cB} = \coll 2 1 .$ Note that while $\vv$ is a vector in $\R^3$, it only has two coordinates with respect to $\cB$.
We already know how to find the coordinates. For this example, we would solve the system $$ \bmat{rr} 1 & 4 \\ 2 & 5 \\ 3 & 6 \\ \emat \, \coll {c_1} {c_2} = \ccolll 6 9 {12} $$
Example: Let $\cB = \{ \ve_1, \ve_2, \ve_3 \}$ be the standard basis for $\R^3$, and consider $\vv = \colll 6 9 {12}$. Then $$ \vv = 6 \ve_1 + 9 \ve_2 + 12\ve_3 \qqtext{so} [\vv]_{\cB} = \colll 6 9 {12} $$ We've implicitly been using the standard basis everywhere, but often in applications it is better to use a basis suited to the problem.
Example: $[0, 1, 1, 0, 1] \in \Z_2^5$.
Question: $[0,1,1] + [1,1,0] = \query{[1,0,1]}$ in $\Z_2^3$.
Question: There are $\query{2^n}$ vectors in $\Z_2^n$.
Example: $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}$.
Question: $[0,1,2] + [1,2,2] = \query{[1,0,1]}$ in $\Z_3^3$.
Example: $2 [0, 1, 2] = [0, 2, 1]$ in $\Z_3^3$.
Question: There are $\query{3^n}$ vectors in $\Z_3^n$.
Example: In $\Z_{10}$, $\,8 \cdot 8 = 64 = 4 \pmod{10}$.
Example: $[4, 6, 8] + [6, 6, 6] = [0, 2, 4]$ and $3[4,6,8] = [2, 8, 4]$ in $\Z_{10}^3$.
Note: 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$, $\,-2 = \query{3.}$
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.}$
Most of this course will concern vectors with real components. Vectors in $\Z_m^n$ will just be used to study code vectors.
Example 8.1: Suppose we want to send the four commands "forward", "back", "left" and "right" as a sequence of 0s and 1s. We could use the following code: $$ \small\kern-8ex \textrm{forward} = [0,0], \quad \textrm{back} = [0,1], \quad \textrm{left} = [1,0], \quad \textrm{right} = [1,1]. $$ But if there is an error in our transmission, the Mars rover will get the wrong message and will drive off of a cliff, wasting billions of dollars of taxpayer money (but making for some good NASA jokes).
Here's a more clever code: $$ \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. Note that it is formed by adding a bit to the end of each of the original code vectors so that the total number of 1s is even.
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, 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 8.3 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.
Example 8.4 (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 8.5 (ISBN Codes): ISBN codes use vectors in $\Z_{11}^{10}$, with "X" used to represent the "digit" 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.