Information security is vitally important to individuals, companies and governments. Malicious use of private information has become the third largest economy after the U.S. and China. The U.S. Cybersecurity & Infrastructure Security Agency estimates in the 26-Oct-2020 report "Cost of a Cyber Incident: Systematic Review and Cross-Validation", the annual cost, per company in the U.S. due to security and infrastructure losses quadrupled from 2018 to 2019.
Figure 1 - Cyber Incident Summary¶
One of the primary means of protecting electronic information is encryption. Encryption is the transformation of plain text or readable information into a non-readable form or cypher text. A cryptogram or cypher text is a message derived from plain text information that has been encrypted (transformed) by using a mathematical algorithm. The plain text in this case is a computer readable version of our information, however the relationship between human characters and the computer characters is a part of a public specification. This is not considered encrypted so much as encoded. Encoded information is simply represented in a new form. We can think of this as translating our characters into a machine readable format.
The American Standard Code for Information Interchange or ASCII is a common machine readable form of English text used in most simple text documents. However ASCII is a 7-bit encoding so the number of characters it may represent (128 characters) is very limited.
The Unicode Standard is a representation capable of expressing most of the current world's writing systems, emoji, and non-visual formatting codes. Unicode defines three encodings, UTF-8, UTF-16, and UTF-32. UTF-32 uses 32 bits, which allows over a million code points.
Table 1 - ASCII Character Table¶
| ASCII Code | Symbol | ASCII Code | Symbol | ASCII Code | Symbol | ASCII Code | Symbol |
|---|---|---|---|---|---|---|---|
| 32 | "space" | ||||||
| 65 | A | 97 | a | 78 | N | 110 | n |
| 66 | B | 98 | b | 79 | O | 111 | o |
| 67 | C | 99 | c | 80 | P | 112 | p |
| 68 | D | 100 | d | 81 | Q | 113 | q |
| 69 | E | 101 | e | 82 | R | 114 | r |
| 70 | F | 102 | f | 83 | S | 115 | s |
| 71 | G | 103 | g | 84 | T | 116 | t |
| 72 | H | 104 | h | 85 | U | 117 | u |
| 73 | I | 105 | i | 86 | V | 118 | v |
| 74 | J | 106 | j | 87 | W | 119 | w |
| 75 | K | 107 | k | 88 | X | 120 | x |
| 76 | L | 108 | l | 89 | Y | 121 | y |
| 77 | M | 109 | m | 90 | Z | 122 | z |
Table 2 - Encode a Message¶
For example, to encode the plain text "Meet me Monday" in ASCII would be
| M | e | e | t | m | e | M | o | n | d | a | y | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 77 | 101 | 101 | 116 | 32 | 109 | 101 | 32 | 77 | 111 | 110 | 100 | 97 | 121 |
Table 3 - Format Message¶
We need groups of 8 characters so we might use
| M | e | e | t | m | e | ||
|---|---|---|---|---|---|---|---|
| 77 | 101 | 101 | 116 | 32 | 109 | 101 | 32 |
| M | o | n | d | a | y | ||
|---|---|---|---|---|---|---|---|
| 77 | 111 | 110 | 100 | 97 | 121 | 32 | 32 |
We can write this "text" as a $2\times 8$ matrix,
$$ \begin{bmatrix} 077 & 101 & 101 & 116 & 032 & 109 & 101 & 032 \\ 077 & 111 & 110 & 100 & 097 & 121 & 032 & 032 \end{bmatrix} $$
This requires an $8\times 8$ matrix to encode our plain text strings.
$$ \begin{bmatrix} \ 13\ &\ 19\ & -3\ &\ \ 7\ & -9\ & -3\ &\ \ 9\ &\ 19\ \\ \ 17\ &\ 19\ &\ 17\ &\ 11\ & -19\ & -5\ &\ 10\ & -7\ \\ -15\ & -14\ &\ 12\ &\ 10\ & -17\ &\ 11\ & -9\ &\ \ 3\ \\ \ 17\ &\ 19\ &\ 19\ & -4\ &\ 13\ &\ 12\ &\ \ 7\ & -11\ \\ \ \ 5\ &\ 19\ &\ \ 6\ &\ \ 6\ &\ \ 8\ & -13\ &\ \ 6\ &\ 10\ \\ -17\ & -1\ & -19\ & -13\ & -7\ &\ \ 0\ & -14\ & -10\ \\ -9\ &\ 12\ &\ 14\ &\ \ 8\ &\ 18\ & -2\ & -16\ &\ \ 0\ \\ \ \ 2\ & -15\ &\ 18\ & -19\ & -19\ &\ \ 6\ &\ \ 0\ &\ \ 8\ \end{bmatrix} $$
Now you can encrypt your plain text matrix into cyphertext using matrix multiplication.
$$ \begin{align*} \text{cyphertext} &= \text{message} \cdot A \\ \\ \text{cyphertext} &= \begin{bmatrix}\ 637\ & 5403\ & 5013\ & 1171\ & -2118\ & 1341\ & -1344\ & -731\ \\ 1142\ & 5558\ & 4183\ & 1117\ & -3475\ &\ 491\ & -111\ & -68\ \end{bmatrix} \end{align*} $$
Now you can send matrix cyphertext to your recipient securely. To decrypt the matrices, your recipient multiplies both sides of the equation above by $A^{-1}$ to obtain the readable plain text,
$$ \begin{align*} \text{message} &= \text{cyphertext} \cdot A^{-1} \\ \\ \text{message} &= \begin{bmatrix} 077 & 101 & 101 & 116 & 032 & 109 & 101 & 032 \\ 077 & 111 & 110 & 100 & 097 & 121 & 032 & 032 \end{bmatrix} \end{align*} $$
Table 4 - Linear Data¶
| $x_i$ | $y_i$ |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 4 |
| 5 | 6 |
Figure 2 - Linear Data Plot¶
We can plot these points on the plane and attempt to find a line that is closest to these points in the least squared sense. In other words, so that the total sum of the distance from each point to the line is as small as possible. The points are non co-linear. Since the Euclidean distance formula includes a square root, we square each distance and minimize the sum of squares. Methods for computing the best possible line are discussed in differential calculus and statistics courses.
The methods used by calculus and statistics are cumbersome and do not shed any light on how the line is produced. We will study the geometry of computing the least squared line or regression line in chapter 5. However for now we should look at how to set up the problem and solve it using methods from this chapter.
The equation of our line in slope-intercept form is given by
$$ y = mx + b $$
This yields five equations and two unknowns, an over determined linear system.
$$ \begin{align*} 1m + b &= 1 \\ 2m + b &= 2 \\ 3m + b &= 4 \\ 4m + b &= 4 \\ 5m + b &= 6 \end{align*} $$
Indeed since we already know that the points are not co-linear we conclude that this over-determined linear system has no solution. We must determine a closest solution for the slope and intercept for the regression line. In matrix form we have
$$ \begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1 \\ 5 & 1 \end{bmatrix}\begin{bmatrix} m \\ b \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 4 \\ 4 \\ 6 \end{bmatrix} $$
In section 5.4 we will discuss the geometry that results in our method of solution. We have the equation
$$ A\begin{bmatrix} m \\ b \end{bmatrix} = \mathbf{b} $$
We multiply both sides of the equation by $A^T$ to obtain the normal equation.
$$ \begin{align*} A\mathbf{x} &= \mathbf{b} \\ A^TA\mathbf{x} &= A^T\mathbf{b} \\ \\ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \\ 2 & 1 \\ 3 & 1 \\ 4 & 1 \\ 5 & 1 \end{bmatrix}\begin{bmatrix} m \\ b \end{bmatrix} &= \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 1 & 1 & 1 \end{bmatrix}\begin{bmatrix} 1 \\ 2 \\ 4 \\ 4 \\ 6 \end{bmatrix} \\ \\ \begin{bmatrix} 55 & 15 \\ 15 & 5 \end{bmatrix}\begin{bmatrix} m \\ b \end{bmatrix} &= \begin{bmatrix} 63 \\ 17 \end{bmatrix} \end{align*} $$
Now we can use Gauss-Jordan Elimination to reduce the augmented matrix.
$$ \begin{align*} \begin{bmatrix} 55 & 15 & | & 63 \\ 15 & 5 & | & 17 \end{bmatrix}\begin{array}{c} R_1-3R_2 \\ \ \end{array} &\rightarrow \begin{bmatrix} 10 & 0 & | & 12 \\ 15 & 5 & | & 17 \end{bmatrix}\begin{array}{c} \ \\ R_2 - R_1 \end{array} \rightarrow \begin{bmatrix} 10 & 0 & | & 12 \\ 5 & 5 & | & 5 \end{bmatrix}\begin{array}{c} \frac{R_1}{10} \\ \frac{R_2}{5} \end{array} \\ \\ &\rightarrow \begin{bmatrix} 1 & 0 & | & 1.2 \\ 1 & 1 & | & 1 \end{bmatrix}\begin{array}{c} \ \\ R_2 - R_1 \end{array}\rightarrow \begin{bmatrix} 1 & 0 & | & 1.2 \\ 0 & 1 & | & -0.2 \end{bmatrix} \end{align*} $$
Our regression line has the equation
$$ y = 1.2x - 0.2 $$
Figure 3 - Regression Line¶
A layer of a neural network takes an input vector $\mathbf{x}$, multiplies by a weight matrix $W$, and adds a bias vector $\mathbf{b}$. This linear combination is an input into an activation function $\sigma$ that produces the output. Hence $\mathbf{y} = \sigma(W\mathbf{x} + \mathbf{b})$. A two-layer network feeds the output of layer 1 into layer 2. A typical activation function is $\textrm{ReLU}$. A common $\textrm{ReLU}$ activation function is defined by
$$ \textrm{ReLU}(\mathbf{z}) = \left[ \max\left(0, z_i\right) \right] $$
Each element of the output vector $\textrm{ReLU}(W\mathbf{x} + \mathbf{b})$ equals $\left\{\begin{array}{ccc} 0 & \text{ if } & z_i<0 \\ z_i & \text{ if } & z_i \ge 0 \end{array} \right. $.
Exercise 3 - Compute the Output¶
Given input vector $\mathbf{x} = \begin{bmatrix}\ 1\ \\ \ 2\ \end{bmatrix}$ and
Layer 1: $W_1 = \begin{bmatrix}\ 1\ &\ 0\ \\ \ 0\ &\ 1\ \\ \ 1\ &\ 1\ \end{bmatrix},\ \mathbf{b}_1 = \begin{bmatrix}\ \ 1\ \\ -3\ \\ \ \ 0\ \end{bmatrix}$
Layer 2: $W_2 = \begin{bmatrix}\ \ 2\ & -1\ &\ \ 0\ \\ \ \ 1\ &\ \ 0\ &\ \ 1\ \end{bmatrix},\ \mathbf{b}_2 = \begin{bmatrix}\ 0\ \\ \ 1\ \end{bmatrix}$
(a) Compute the hidden vector $\mathbf{h} = \sigma(W_1\mathbf{x} + \mathbf{b}_1)$.
(b) Compute the output $\mathbf{y} = \sigma(W_2\mathbf{h} + \mathbf{b}_2)$.
View Solution
(a) Using $W_1$, $\mathbf{b}_1$ and $\textrm{ReLU}$, $$ \begin{align*} \mathbf{h} &= \sigma\left( W_1\mathbf{x} + \mathbf{b}_1 \right) \\ &= \sigma\left( \begin{bmatrix}\ 1\ &\ 0\ \\ \ 0\ &\ 1\ \\ \ 1\ &\ 1\ \end{bmatrix} \begin{bmatrix}\ 1\ \\ \ 2\ \end{bmatrix} + \begin{bmatrix}\ \ 1\ \\ -3\ \\ \ \ 0\ \end{bmatrix} \right) \\ &= \sigma\left( \begin{bmatrix}\ \ 1\ \\ \ \ 2\ \\ \ \ 3\ \end{bmatrix} + \begin{bmatrix}\ \ 1\ \\ -3\ \\ \ \ 0\ \end{bmatrix} \right) \\ &= \sigma\left( \begin{bmatrix}\ \ 2\ \\ -1\ \\ \ \ 3\ \end{bmatrix} \right) = \begin{bmatrix}\ \ 2\ \\ \ \ 0\ \\ \ \ 3\ \end{bmatrix} \end{align*} $$ (b) computing the output using the hidden vector $$ \begin{align*} \mathbf{y} &= \sigma\left( W_2\mathbf{h} + \mathbf{b}_2 \right) \\ &= \sigma\left( \begin{bmatrix}\ \ 2\ & -1\ &\ \ 0\ \\ \ \ 1\ &\ \ 0\ &\ \ 1\ \end{bmatrix} \begin{bmatrix}\ \ 2\ \\ \ \ 0\ \\ \ \ 3\ \end{bmatrix} + \begin{bmatrix}\ 0\ \\ \ 1\ \end{bmatrix} \right) \\ &= \sigma\left( \begin{bmatrix}\ \ 4\ \\ \ \ 5\ \end{bmatrix} + \begin{bmatrix}\ 0\ \\ \ 1\ \end{bmatrix} \right) \\ &= \sigma\left( \begin{bmatrix}\ \ 4\ \\ \ \ 6\ \end{bmatrix} \right) = \begin{bmatrix}\ \ 4\ \\ \ \ 6\ \end{bmatrix} \end{align*} $$An economy is divided into sectors that consume one another's output. If $a_{ij}$ is the dollar value of sector $i$'s output needed to produce one dollar of sector $j$'s output, then the consumption matrix $A$ collects these amounts. A production vector $\mathbf{x}$ must cover both the demand from other sectors and the external (final) demand $\mathbf{d}$,
$$ \mathbf{x} = A\mathbf{x} + \mathbf{d} $$
Equivalently this is
$$ (I - A)\,\mathbf{x} = \mathbf{d}. $$
When $(I-A)$ is invertible the production levels are $\mathbf{x} = (I-A)^{-1}\mathbf{d}$.
Exercise 4 - Leontief Model¶
Consider a two-sector economy of agriculture and manufacturing (all amounts in millions of dollars), with consumption matrix and external demand
$$ A = \begin{bmatrix}\ 0.20\ &\ 0.25\ \\ \ 0.40\ &\ 0.10\ \end{bmatrix}, \qquad \mathbf{d} = \begin{bmatrix}\ 60\ \\ \ 32\ \end{bmatrix}. $$
- Form the matrix $I - A$ and write out the linear system $(I-A)\mathbf{x} = \mathbf{d}$.
- Solve the system by Gauss-Jordan elimination for the production vector $\mathbf{x}$.
- Verify your answer satisfies $\mathbf{x} = A\mathbf{x} + \mathbf{d}$, and state in words how much each sector must produce to meet the external demand.
View Solution
1. The linear system $(I - A)\mathbf{x} = \mathbf{d}$ is given by $$ \begin{align*} \left( \begin{bmatrix}\ 1\ &\ 0\ \\ \ 0\ &\ 1\ \end{bmatrix} - \begin{bmatrix}\ 0.20\ &\ 0.25\ \\ \ 0.40\ &\ 0.10\ \end{bmatrix} \right)\mathbf{x} &= \begin{bmatrix}\ 60\ \\ \ 32\ \end{bmatrix} \\ \\ \begin{bmatrix}\ \ 0.80 & -0.25\ \\ -0.40\ &\ \ 0.90\ \end{bmatrix}\mathbf{x} &= \begin{bmatrix}\ 60\ \\ \ 32\ \end{bmatrix} \\ \\ 0.80x_1 - 0.25x_2 &= 60 \\ -0.40x_1 + 0.90x_2 &= 32 \end{align*} $$ 2. Solving the linear system using Gauss-Jordan elimination yields $$ \begin{align*} \left[ \begin{array}{cc|c}\ \ 0.80\ & -0.25\ &\ 60\ \\ -0.40\ &\ \ 0.90\ &\ 32\ \end{array} \right] \begin{array}{l} -100R_2 \\ 100R_1 \end{array} &\rightarrow \left[ \begin{array}{cc|c}\ \ 40\ & -90\ & -3200\ \\ \ \ 80\ & -25\ &\ \ 6000\ \end{array} \right] \begin{array}{l} \\ R_2-2R_1 \end{array} \rightarrow \left[ \begin{array}{cc|c}\ \ 40\ & -90\ & -3200\ \\ \ \ 0\ &\ \ 155\ &\ 12400\ \end{array} \right] \begin{array}{l} \\ R_2/155 \end{array} \rightarrow \\ \\ \left[ \begin{array}{cc|c}\ \ 40\ & -90\ & -3200\ \\ \ \ 0\ &\ \ 1\ &\ \ 80\ \end{array} \right] \begin{array}{l} R_1+90R_2 \\ \\ \end{array} &\rightarrow \left[ \begin{array}{cc|c}\ \ 40\ &\ \ 0\ &\ 4000\ \\ \ \ 0\ &\ \ 1\ &\ 80\ \end{array} \right] \begin{array}{l} R_1/40 \\ \\ \end{array} \rightarrow \left[ \begin{array}{cc|c}\ \ 1\ &\ \ 0\ &\ 100\ \\ \ \ 0\ &\ \ 1\ &\ 80\ \end{array} \right] \end{align*} $$ 3. $A\mathbf{x} + \mathbf{d} = \begin{bmatrix}\ 0.20\ &\ 0.25\ \\ \ 0.40\ &\ 0.10\ \end{bmatrix} \begin{bmatrix}\ 100\ \\ \ 80\ \end{bmatrix} + \begin{bmatrix}\ 60\ \\ \ 32\ \end{bmatrix} = \begin{bmatrix}\ 40\ \\ \ 48\ \end{bmatrix} + \begin{bmatrix}\ 60\ \\ \ 32\ \end{bmatrix} = \begin{bmatrix}\ 100\ \\ \ 80\ \end{bmatrix}\ {\color{green}\Large{\checkmark}}$Both columns of $I-A$ are pivot columns so $I-A$ is invertible. Agriculture must produce $\$100\,$M and manufacturing must produce $\$80\,$M in order to meet the external demand.
To rank $n$ teams in a league, the Colley method solves $C\mathbf{r} = \mathbf{b}$ for the rating vector $\mathbf{r}$, where
$$ \begin{align*} C_{ii} &= 2 + (\text{games team $i$ played}), \\ C_{ij} &= -(\text{games between $i$ and $j$}), \\ \\ \mathbf{b}_i &= 1 + (w_i - l_i)/2. \end{align*} $$
Exercise 5 - Round Robin Tournament¶
Three teams play a round robin (each pair once): A beat B, A beat C, B beat C.
Build the $3\times3$ Colley matrix $C$ and the vector $\mathbf{b}$.
Solve $C\mathbf{r} = \mathbf{b}$ using Gauss-Jordan elimination for the ratings, and rank the teams.
Check that the ratings sum to $\frac{n}{2} = 1.5$.
View Solution
1. A has 2 wins and 0 losses, B has 1 win and 1 loss, and C has 2 losses. $$ \begin{align*} C &= \begin{bmatrix}\ 2+2\ & -1\ & -1\ \\ -1\ &\ 2+2\ &- 1\ \\ -1\ & -1\ &\ 2+2\ \end{bmatrix} = \begin{bmatrix}\ \ 4\ & -1\ & -1\ \\ -1\ &\ \ 4\ & -1\ \\ -1\ & -1\ &\ \ 4\ \end{bmatrix} \\ \\ \mathbf{b} &= \begin{bmatrix} 1 + \frac{2}{2} \\ 1 + \frac{0}{2} \\ 1 - \frac{2}{2} \end{bmatrix} = \begin{bmatrix}\ 2\ \\ \ 1\ \\ \ 0\ \end{bmatrix} \end{align*} $$ 2. Using elimination $$ \begin{align*} \left[ \begin{array}{ccc|c}\ \ 4\ & -1\ & -1 &\ 2\ \\ -1\ &\ \ 4\ & -1\ &\ 1\ \\ -1\ & -1\ &\ \ 4\ &\ 0\ \end{array} \right] \begin{array}{l} -R_2 \\ R_1 \\ R_3 \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 1\ & -1\ \\ \ \ 4\ & -1\ & -1 &\ 2\ \\ -1\ & -1\ &\ \ 4\ &\ 0\ \end{array} \right] \begin{array}{l} \\ R_2-4R_1 \\ R_3+R_1 \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 1\ & -1\ \\ \ \ 0\ &\ 15\ & -5 &\ 6\ \\ \ 0\ & -5\ &\ \ 5\ & -1\ \end{array} \right] \begin{array}{l} \\ R_2+3R_3 \\ \\ \end{array} \rightarrow \\ \\ \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ 10 &\ 3\ \\ \ 0\ & -5\ &\ \ 5\ & -1\ \end{array} \right] \begin{array}{l} \\ R_3 \\ R_2 \end{array} &\rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 1\ & -1\ \\ \ 0\ & -5\ &\ \ 5\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ 10\ &\ 3\ \end{array} \right] \begin{array}{l} \\ -R_2/5 \\ R_3/10 \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 1\ & -1\ \\ \ \ 0\ &\ \ 1\ & -1\ &\ 0.2\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ 0.3\ \end{array} \right] \begin{array}{l} R_1-R_3 \\ R_2+R_3 \\ \\ \end{array} \\ \\ &\rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ & -4\ &\ \ 0\ & -1.3\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ 0.5\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ 0.3\ \end{array} \right] \begin{array}{l} R_1+4R_2 \\ \\ \\ \end{array} \rightarrow \left[ \begin{array}{ccc|c}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ 0.7\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ 0.5\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ 0.3\ \end{array} \right] \\ \mathbf{r} &= \begin{bmatrix}\ 0.7\ \\ \ 0.5\ \\ \ 0.3\ \end{bmatrix} \end{align*} $$ The team ranking is $1.$ A, $2.$ B, $3.$ C.3. $0.7 + 0.5 + 0.3 = 1.5\ {\color{green}\Large{\checkmark}}$
Online stores suggest products using a co-occurrence matrix. Record purchases in a users $\times$ items matrix $R$ where $R_{ui} = 1$ if user $u$ bought item $i$, and $0$ otherwise. The matrix product $R^\mathsf{T} R$ then summarizes buying patterns:
its diagonal entry $(i,i)$ counts how many users bought item $i$, and
its off-diagonal entry $(i,j)$ counts how many users bought both item $i$ and item $j$.
Exercise 6 - Recommendations from Co-occurrence¶
Suppose four users buy from a catalog of three items as recorded below.
Table 5 - Purchase Record¶
| User | item 1 | item 2 | item 3 |
|---|---|---|---|
| $u_1$ | 1 | 1 | 0 |
| $u_2$ | 1 | 1 | 0 |
| $u_3$ | 1 | 0 | 1 |
| $u_4$ | 1 | 1 | 1 |
In matrix form,
$$ R = \begin{bmatrix}\ 1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 0\ &\ 1\ \\ \ 1\ &\ 1\ &\ 1\ \end{bmatrix}. $$
- Compute the co-occurrence matrix $R^\mathsf{T} R$.
- Use the diagonal entries to determine which item is the most popular.
- A customer has just purchased item 1. Using the off-diagonal entries in the row (or column) for item 1, decide which remaining item you should recommend, and explain why.
View Solution
1. The co-occurrence matrix $R^\mathsf{T}R = $ $$ \begin{bmatrix}\ 1\ &\ 1\ &\ 1\ &\ 1\ \\ \ 1\ &\ 1\ &\ 0\ &\ 1\ \\ \ 0\ &\ 0\ &\ 1\ &\ 1\ \end{bmatrix} \begin{bmatrix}\ 1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 1\ &\ 0\ \\ \ 1\ &\ 0\ &\ 1\ \\ \ 1\ &\ 1\ &\ 1\ \end{bmatrix} = \begin{bmatrix}\ 4\ &\ 3\ &\ 2\ \\ \ 3\ &\ 3\ &\ 1 \\ \ 2\ &\ 1\ &\ 2\ \end{bmatrix} $$ 2. Looking at the diagonal of $R^\mathsf{T}R$, item 1 is the most popular with 4 buyers.3. For buyers of item 1, recommend item 2, since its co-purchase count with item 1 is 3 versus 2 for item 3.
In computer graphics a point $\mathbf{v} = \begin{bmatrix} x \\ y \end{bmatrix}$ is moved by multiplying it by a $2\times 2$ matrix. Three basic transformations are
$$ \underbrace{S = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix}}_{\text{scaling}} \qquad \underbrace{H = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}}_{\text{horizontal shear}} \qquad \underbrace{R = \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}}_{\text{rotation }90^\circ\text{ CCW}}. $$
Applying one transformation and then another corresponds to multiplying their matrices, and a transformation is undone by the inverse matrix.
We can create a bitmap image of the letter F:
Figure 4 - Bitmap F¶
We represent this letter with a $2\times11$ matrix of pixel coordinates to fill.
$$ F = \begin{bmatrix}\ 0\ &\ 0\ &\ 0\ &\ 0\ &\ 0\ &\ 0\ &\ 1\ &\ 1\ &\ 2\ &\ 2\ &\ 3\ \\ \ 0\ &\ 1\ &\ 2\ &\ 3\ &\ 4\ &\ 5\ &\ 3\ &\ 5\ &\ 3\ &\ 5\ &\ 5\ \end{bmatrix} $$
Each column of matrix $F$ indicates the lower left-hand corner of a pixel to fill.
Exercise 7 - Graphics Transformations¶
- Compute $SF$, $HF$, and $RF$, and describe in words what each transformation did to the letter.
- To shear the letter and then scale the result, form the product $SH$; to scale first and then shear, form $HS$. Compute both matrices and apply each to $F$. Are the results the same? What does this say about the order of matrix multiplication?
- A point has been rotated $90^\circ$ counter-clockwise. Find $R^{-1}$ and use it to recover the original point. Verify that $R^{-1} = R^{\mathsf{T}}$.
View Solution
1. $S$ stretches the letter; $2\times$ as wide and $3\times$ as tall. $H$ slants the letter, and $R$ tips the letter $90^{\circ}$ counter-clockwise into the second quadrant.Figure 5 - Basic Transformations of Bitmap F
2. $SH$ first slants the letter and then scales it. However, $HS$ first scales the letter and applies the shear.
Figure 6 - Transformation Order
3. Compute $R^{-1}$ using Gauss-Jordan elimination. $$ \begin{align*} \left[ \begin{array}{cc|cc}\ \ 0\ & -1\ &\ \ 1\ &\ \ 0\ \\ \ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \end{array} \right] \begin{array}{l} R_2 \\ R_1 \end{array} &\rightarrow \left[ \begin{array}{cc|cc}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ & -1\ &\ \ 1\ &\ \ 0\ \end{array} \right] \begin{array}{l} \\ -R_2 \end{array} \rightarrow \left[ \begin{array}{cc|cc}\ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ & -1\ &\ \ 0\ \end{array} \right] \\ \\ R^{-1} &= \begin{bmatrix}\ \ 0\ &\ \ 1\ \\ -1\ &\ \ 0\ \end{bmatrix} = R^\mathsf{T} \end{align*} $$
Figure 7 - Transformation Inverse
The inverse matrix returns the letter to its original position.
