Matrix-vector product and linear maps

Section 1.3 Matrix-vector product and linear maps

Subsection Vectors as columns

A vector can be written as a row or as a column. When a matrix acts on a vector in this course, we usually write the vector as a column:

\begin{equation*} \mathbf{x}=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix}. \end{equation*}

🔗

From now on, when we write \(\mathbf{x}=(x_1,\ldots,x_n)\text{,}\) \(\mathbf{x}\) is interpreted as a column vector.

🔗

If \(A\) is an \(m\times n\) matrix, then \(A\) has \(n\) columns. We write

\begin{equation*} A=\begin{bmatrix}\mathbf{a}_1 \amp \mathbf{a}_2 \amp \cdots \amp \mathbf{a}_n\end{bmatrix} \end{equation*}

where each \(\mathbf{a}_j\) is a column vector in \(\mathbb R^m\text{.}\)

🔗

Subsection Matrix-vector product

Definition 1.3.1. Matrix-vector product.

Let \(A=\begin{bmatrix}\mathbf{a}_1 \amp \mathbf{a}_2 \amp \cdots \amp \mathbf{a}_n\end{bmatrix}\) be an \(m\times n\) matrix and let \(\mathbf{x}=(x_1,\ldots,x_n)\) be a column vector in \(\mathbb R^n\text{.}\) The matrix-vector product is

\begin{equation*} A\mathbf{x}=x_1\mathbf{a}_1+x_2\mathbf{a}_2+\cdots+x_n\mathbf{a}_n. \end{equation*}

🔗

Activity 1.3.1. Computing a matrix-vector product.

Compute \(A\mathbf{x}\) where

\begin{equation*} A=\begin{bmatrix}-1 \amp 4 \amp -5\\ 3 \amp 1 \amp -2\end{bmatrix}, \qquad \mathbf{x}=\begin{bmatrix}2\\-3\\4\end{bmatrix}. \end{equation*}

🔗

Solution.

Using columns,

\begin{align*} A\mathbf{x} \amp=2\begin{bmatrix}-1\\3\end{bmatrix}-3\begin{bmatrix}4\\1\end{bmatrix}+4\begin{bmatrix}-5\\-2\end{bmatrix}\\ \amp=\begin{bmatrix}-34\\-5\end{bmatrix}. \end{align*}

🔗

Theorem 1.3.2. Properties of matrix-vector products.

Let \(A\) and \(B\) be \(m\times n\) matrices, let \(\mathbf{x},\mathbf{y}\in\mathbb R^n\text{,}\) and let \(r\) be a scalar. Then

\(A(\mathbf{x}+\mathbf{y})=A\mathbf{x}+A\mathbf{y}\text{,}\)
🔗

🔗
\(A(r\mathbf{x})=r(A\mathbf{x})=(rA)\mathbf{x}\text{,}\)
🔗

🔗
\((A+B)\mathbf{x}=A\mathbf{x}+B\mathbf{x}\text{.}\)
🔗

🔗

🔗

Theorem 1.3.3. Row dot-product view.

If \(A\) is an \(m\times n\) matrix with rows \(\operatorname{row}_1(A),\ldots,\operatorname{row}_m(A)\text{,}\) then

\begin{equation*} A\mathbf{x}= \begin{bmatrix} \operatorname{row}_1(A)\cdot\mathbf{x}\\ \operatorname{row}_2(A)\cdot\mathbf{x}\\ \vdots\\ \operatorname{row}_m(A)\cdot\mathbf{x} \end{bmatrix}. \end{equation*}

🔗

Note 1.3.4. Rows measure; columns contribute.

A matrix-vector product has two complementary readings. In the row view, each row measures the input by taking a dot product with \(\mathbf{x}\text{.}\) In the column view,

\begin{equation*} A\mathbf{x}=x_1\mathbf{a}_1+\cdots+x_n\mathbf{a}_n, \end{equation*}

so the input coordinates tell how much each column contributes to the output.

🔗

Subsubsection Examples of matrix-vector products

The same product \(A\mathbf{x}\) can represent different operations, depending on what the rows and columns of \(A\) mean. The next activities show three common patterns: scoring, selecting, and measuring changes.

🔗

Activity 1.3.2. Scoring objects by features.

Let the rows of \(X\) represent three objects with two features:

\begin{equation*} X=\begin{bmatrix}3\amp 1\\1\amp 4\\2\amp 2\end{bmatrix}, \qquad \mathbf{w}=(2,-1). \end{equation*}

Compute \(X\mathbf{w}\text{.}\) Interpret the result.

🔗

Solution.

We have

\begin{equation*} X\mathbf{w}= \begin{bmatrix}3\amp 1\\1\amp 4\\2\amp 2\end{bmatrix} \begin{bmatrix}2\\-1\end{bmatrix} = \begin{bmatrix}5\\-2\\2\end{bmatrix}. \end{equation*}

Each output is a score:

\begin{equation*} 2(\text{first feature})-(\text{second feature}). \end{equation*}

🔗

Activity 1.3.3. A selector matrix.

Let

\begin{equation*} S=\begin{bmatrix}1\amp0\amp0\amp0\\0\amp0\amp1\amp0\end{bmatrix}, \qquad \mathbf{x}=\begin{bmatrix}5\\6\\7\\8\end{bmatrix}. \end{equation*}

Compute \(S\mathbf{x}\text{.}\) What does \(S\) do?

🔗

Solution.

We have

\begin{equation*} \begin{aligned} S\mathbf{x} \amp= \begin{bmatrix} 1\cdot 5+0\cdot 6+0\cdot 7+0\cdot 8\\ 0\cdot 5+0\cdot 6+1\cdot 7+0\cdot 8 \end{bmatrix}\\ \amp= \begin{bmatrix}5\\7\end{bmatrix}. \end{aligned} \end{equation*}

The matrix \(S\) selects the first and third entries of \(\mathbf{x}\text{.}\)

🔗

Activity 1.3.4. A difference matrix.

Let

\begin{equation*} D=\begin{bmatrix}-1\amp 1\amp 0\\0\amp -1\amp 1\end{bmatrix}, \qquad \mathbf{x}=\begin{bmatrix}2\\5\\9\end{bmatrix}. \end{equation*}

Compute \(D\mathbf{x}\text{.}\) What does \(D\) measure?

🔗

Solution.

We have

\begin{equation*} \begin{aligned} D\mathbf{x} \amp= \begin{bmatrix} -1\cdot 2+1\cdot 5+0\cdot 9\\ 0\cdot 2+(-1)\cdot 5+1\cdot 9 \end{bmatrix}\\ \amp= \begin{bmatrix}3\\4\end{bmatrix}. \end{aligned} \end{equation*}

The entries are consecutive differences:

\begin{equation*} 5-2=3,\qquad 9-5=4. \end{equation*}

Thus \(D\) measures changes in a short time series.

🔗

Activity 1.3.5. Document ranking in matrix code.

In Activity 1.1.6, we ranked documents by cosine similarity one score at a time. The following code repeats that ranking using a data matrix whose rows are the document vectors.

🔗

import numpy as np

doc_names = np.array(["D1", "D2", "D3"])

X = np.array([
    [2, 0, 2],
    [1, 1, 0],
    [0, 2, 0],
], dtype=float)

q = np.array([1, 0, 1], dtype=float)

scores = (X @ q) / (np.linalg.norm(X, axis=1) * np.linalg.norm(q))
ranking = doc_names[np.argsort(scores)[::-1]]

scores, ranking

Output:

🔗

(array([1. , 0.5, 0. ]),
 array(['D1', 'D2', 'D3'], dtype='<U2'))

Which row of X is the vector \(\mathbf{D}_2\text{?}\)
🔗

🔗
Which expression computes the three dot products \(\mathbf{D}_i\cdot\mathbf{q}\text{?}\)
🔗

🔗
What does np.argsort(scores)[::-1] do?
🔗

🔗
Why does the output agree with Activity 1.1.6?
🔗

🔗

Solution.

The rows of X are \(\mathbf{D}_1\text{,}\) \(\mathbf{D}_2\text{,}\) and \(\mathbf{D}_3\text{.}\) The product X @ q computes the three dot products with the query. The expression np.argsort(scores)[::-1] gives the indices of the scores from largest to smallest. The output agrees with Activity 1.1.6: \(1,\frac12,0\text{.}\)

🔗

Example 1.3.5. The attention activity in matrix form.

In Activity 1.1.8, we computed the scores

\begin{equation*} \mathbf{q}\cdot\mathbf{k}_{\mathrm{small}},\qquad \mathbf{q}\cdot\mathbf{k}_{\mathrm{red}},\qquad \mathbf{q}\cdot\mathbf{k}_{\mathrm{bird}} \end{equation*}

one at a time. Matrix-vector multiplication computes the same scores at once.

🔗

Put the key vectors as the rows of

\begin{equation*} K=\begin{bmatrix} \mathbf{k}_{\mathrm{small}}^T\\ \mathbf{k}_{\mathrm{red}}^T\\ \mathbf{k}_{\mathrm{bird}}^T \end{bmatrix}. \end{equation*}

Then

\begin{equation*} K\mathbf{q}= \begin{bmatrix} \mathbf{k}_{\mathrm{small}}\cdot\mathbf{q}\\ \mathbf{k}_{\mathrm{red}}\cdot\mathbf{q}\\ \mathbf{k}_{\mathrm{bird}}\cdot\mathbf{q} \end{bmatrix}. \end{equation*}

🔗

For the numbers in Activity 1.1.8,

\begin{equation*} K=\begin{bmatrix}1\amp0\\0\amp1\\1\amp1\end{bmatrix}, \qquad \mathbf{q}=\begin{bmatrix}1\\1\end{bmatrix}, \end{equation*}

\begin{equation*} K\mathbf{q}=\begin{bmatrix}1\\1\\2\end{bmatrix}. \end{equation*}

🔗

Activity 1.3.6. The same attention calculation in code.

The following code performs the calculation from the token attention activity.

🔗

import numpy as np

tokens = np.array(["small", "red", "bird"])

q = np.array([1.0, 1.0])

K = np.array([
    [1.0, 0.0],
    [0.0, 1.0],
    [1.0, 1.0],
])

V = np.array([
    [4.0, 0.0],
    [0.0, 4.0],
    [4.0, 4.0],
])

s = K @ q
alpha = s / s.sum()
out = alpha @ V

s, alpha, out

Output:

🔗

(array([1., 1., 2.]),
 array([0.25, 0.25, 0.5 ]),
 array([3., 3.]))

Which line computes the token scores?
🔗

🔗
Which token receives the largest weight?
🔗

🔗
Which line forms the weighted average?
🔗

🔗
Why do the entries of alpha add to \(1\text{?}\)
🔗

🔗

Solution.

The line s = K @ q computes the three dot products. The token “bird” receives the largest weight. The line out = alpha @ V forms the weighted average of the rows of V. The entries of alpha add to \(1\) because the scores were divided by their sum.

🔗

Subsection Geometric matrix actions in \(\mathbb R^2\)

Definition 1.3.6. Identity matrix.

The identity matrix \(I_n\) is the \(n\times n\) matrix with \(1\)s on the main diagonal and zeros elsewhere.

🔗

Fact 1.3.7.

For every column vector \(\mathbf{x}\in\mathbb R^n\text{,}\) \(I_n\mathbf{x}=\mathbf{x}\text{.}\)

🔗

Definition 1.3.8. Standard basis.

The \(j\)-th standard basis vector \(\mathbf{e}_j\) is the column vector with a \(1\) in position \(j\) and zeros elsewhere.

🔗

Fact 1.3.9.

If \(A=\begin{bmatrix}\mathbf{a}_1 \amp \cdots \amp \mathbf{a}_n\end{bmatrix}\text{,}\) then \(A\mathbf{e}_j=\mathbf{a}_j\text{.}\) Applying a matrix to a standard basis vector picks out a column.

🔗

In \(\mathbb R^2\text{,}\) a matrix \(A=\begin{bmatrix}\mathbf{a}_1 \amp \mathbf{a}_2\end{bmatrix}\) sends \(\mathbf{e}_1\) to \(\mathbf{a}_1\) and \(\mathbf{e}_2\) to \(\mathbf{a}_2\text{.}\) Since every vector \(\mathbf{x}=(x_1,x_2)\) can be written as \(x_1\mathbf{e}_1+x_2\mathbf{e}_2\text{,}\) we have

\begin{equation*} A\mathbf{x}=x_1\mathbf{a}_1+x_2\mathbf{a}_2. \end{equation*}

Thus a \(2\times 2\) matrix is geometrically determined by where it sends the two coordinate directions.

🔗

To understand a \(2\times 2\) matrix \(A\text{,}\) apply it to the four corners of the unit square. The image is usually a parallelogram. The two edges leaving the origin are the columns of \(A\text{.}\) We will refer to this as the unit-square visualization.

🔗

The unit-square visualization for a shear matrix. — Figure 1.3.10. A \(2\times 2\) matrix sends the unit square to the parallelogram determined by its two columns. This is the geometric version of columns contribute.
🔗

Table 1.3.11. Compact transformation gallery

🔗

Matrix	\(A\mathbf{e}_1\)	\(A\mathbf{e}_2\)	Name	Unit-square effect
\(\begin{bmatrix}2\amp0\\0\amp1\end{bmatrix}\)	\(\begin{bmatrix}2\\0\end{bmatrix}\)	\(\begin{bmatrix}0\\1\end{bmatrix}\)	horizontal stretch	The right edge moves farther right. 🔗
\(\begin{bmatrix}0\amp0\\0\amp1\end{bmatrix}\)	\(\begin{bmatrix}0\\0\end{bmatrix}\)	\(\begin{bmatrix}0\\1\end{bmatrix}\)	projection onto the \(y\)-axis	Horizontal information is forgotten. 🔗
\(\begin{bmatrix}-1\amp0\\0\amp1\end{bmatrix}\)	\(\begin{bmatrix}-1\\0\end{bmatrix}\)	\(\begin{bmatrix}0\\1\end{bmatrix}\)	reflection across the \(y\)-axis	The square flips left. 🔗
\(\begin{bmatrix}1\amp1\\0\amp1\end{bmatrix}\)	\(\begin{bmatrix}1\\0\end{bmatrix}\)	\(\begin{bmatrix}1\\1\end{bmatrix}\)	horizontal shear	The bottom edge stays fixed; the top edge shifts right. 🔗
\(\begin{bmatrix}0\amp-1\\1\amp0\end{bmatrix}\)	\(\begin{bmatrix}0\\1\end{bmatrix}\)	\(\begin{bmatrix}-1\\0\end{bmatrix}\)	\(90^\circ\) counterclockwise rotation	The square rotates around the origin. 🔗
\(\begin{bmatrix}1\amp0\\0\amp0\end{bmatrix}\)	\(\begin{bmatrix}1\\0\end{bmatrix}\)	\(\begin{bmatrix}0\\0\end{bmatrix}\)	projection onto the \(x\)-axis	Vertical information is forgotten. 🔗

For more illustrations of these transformations, see Lab U1: Vectors, Similarity, Attention, and Matrix Actions

sebroc.github.io/MATH345-Course-Materials/labs/#lab-u1

🔗

Example 1.3.12. Which column tells the story?

For each matrix in the compact transformation gallery, compare \(A\mathbf{e}_1\) and \(A\mathbf{e}_2\) with \(\mathbf{e}_1\) and \(\mathbf{e}_2\text{.}\) Which column changed most visibly from the identity matrix? What does that change do to the unit square?

🔗

Solution.

The columns \(A\mathbf{e}_1\) and \(A\mathbf{e}_2\) are the transformed coordinate directions. A stretch changes the length of a column. A reflection reverses the direction of a column. A shear changes one column by adding part of the other direction. A projection sends one column to zero, so one direction is forgotten.

🔗

Activity 1.3.7. Reflection across the \(y\)-axis.

Let \(A=\begin{bmatrix}-1\amp0\\0\amp1\end{bmatrix}\text{.}\) Compute \(A\mathbf{e}_1\text{,}\) \(A\mathbf{e}_2\text{,}\) \(A\mathbf{x}\text{,}\) and \(A\mathbf{y}\text{,}\) where \(\mathbf{x}=(1,1)\) and \(\mathbf{y}=(0,1)\text{.}\) Which coordinate changes?

🔗

Solution.

We get

\begin{equation*} A\mathbf{e}_1=\begin{bmatrix}-1\\0\end{bmatrix},\qquad A\mathbf{e}_2=\begin{bmatrix}0\\1\end{bmatrix},\qquad A\mathbf{x}=\begin{bmatrix}-1\\1\end{bmatrix},\qquad A\mathbf{y}=\begin{bmatrix}0\\1\end{bmatrix}. \end{equation*}

The first coordinate flips sign and the second coordinate is unchanged.

🔗

Activity 1.3.8. Horizontal shear.

Let \(A=\begin{bmatrix}1\amp1\\0\amp1\end{bmatrix}\text{.}\) Compute \(A\mathbf{e}_1\text{,}\) \(A\mathbf{e}_2\text{,}\) and \(A\mathbf{x}\text{,}\) where \(\mathbf{x}=(1,1)\text{.}\) Explain why the bottom edge stays fixed and the top edge shifts right.

🔗

Solution.

We have

\begin{equation*} A\mathbf{e}_1=\begin{bmatrix}1\\0\end{bmatrix},\qquad A\mathbf{e}_2=\begin{bmatrix}1\\1\end{bmatrix},\qquad A\mathbf{x}=\begin{bmatrix}2\\1\end{bmatrix}. \end{equation*}

The formula is \(A(x,y)=(x+y,y)\text{.}\) Points with \(y=0\) stay fixed, and points with \(y=1\) shift right by \(1\text{.}\)

🔗

Note 1.3.13.

For the shear matrix \(A=\begin{bmatrix}1\amp1\\0\amp1\end{bmatrix}\text{,}\) the row view gives

\begin{equation*} A\begin{bmatrix}x\\y\end{bmatrix} = \begin{bmatrix} (1,1)\cdot(x,y)\\ (0,1)\cdot(x,y) \end{bmatrix} = \begin{bmatrix}x+y\\y\end{bmatrix}. \end{equation*}

The first row measures horizontal plus vertical, while the second row measures vertical only. The column view gives

\begin{equation*} A\begin{bmatrix}x\\y\end{bmatrix} = x\begin{bmatrix}1\\0\end{bmatrix} + y\begin{bmatrix}1\\1\end{bmatrix}, \end{equation*}

so the \(y\)-coordinate contributes both upward and rightward motion.

🔗

Subsection Linear and affine maps

A function assigns one output to each input. In this course, many functions have vectors as inputs and vectors as outputs:

\begin{equation*} F:\mathbb R^n\to\mathbb R^m. \end{equation*}

A matrix gives one important source of such functions by the rule \(\mathbf{x}\mapsto A\mathbf{x}\text{.}\)

🔗

Definition 1.3.14. Matrix map.

Given an \(m\times n\) matrix \(A\text{,}\) the matrix map induced by \(A\) is the function \(T_A:\mathbb R^n\to\mathbb R^m\) defined by

\begin{equation*} T_A(\mathbf{x})=A\mathbf{x}. \end{equation*}

🔗

Definition 1.3.15. Linear map.

A function \(T:\mathbb R^n\to\mathbb R^m\) is linear if

\begin{align*} T(\mathbf{u}+\mathbf{v}) \amp= T(\mathbf{u})+T(\mathbf{v}),\\ T(c\mathbf{v}) \amp= cT(\mathbf{v}) \end{align*}

for all vectors \(\mathbf{u},\mathbf{v}\) and all scalars \(c\text{.}\)

🔗

Theorem 1.3.16. Matrix maps are linear.

If \(A\) is an \(m\times n\) matrix, then the function \(T_A:\mathbb R^n\to\mathbb R^m\) defined by \(T_A(\mathbf{x})=A\mathbf{x}\) is linear.

🔗

Why is this true?.

Matrix-vector multiplication distributes over vector addition and scalar multiplication:

\begin{equation*} A(\mathbf{u}+\mathbf{v})=A\mathbf{u}+A\mathbf{v},\qquad A(c\mathbf{v})=cA\mathbf{v}. \end{equation*}

These are exactly the two linearity rules.

🔗

Theorem 1.3.17. Every linear map has a matrix.

Every linear map \(T:\mathbb R^n\to\mathbb R^m\) is given by multiplication by a unique matrix. The columns of that matrix are \(T(\mathbf{e}_1),\ldots,T(\mathbf{e}_n)\text{.}\)

🔗

Activity 1.3.9. Images of basis vectors determine the matrix.

Suppose a linear map \(T:\mathbb R^2\to\mathbb R^2\) satisfies \(T(\mathbf{e}_1)=(2,1)\) and \(T(\mathbf{e}_2)=(-1,3)\text{.}\) Find the matrix \(A\) such that \(T(\mathbf{x})=A\mathbf{x}\text{.}\)

🔗

Solution.

The columns are the images of the standard basis vectors, so

\begin{equation*} A=\begin{bmatrix}2 \amp -1\\1 \amp 3\end{bmatrix}. \end{equation*}

🔗

Warning 1.3.18.

We use “linear map” and “linear transformation” interchangeably; “transformation” is often used when emphasizing geometry.

🔗

Definition 1.3.19. Affine map.

A function of the form

\begin{equation*} \mathbf{x}\mapsto A\mathbf{x}+\mathbf{b} \end{equation*}

is called affine. It is built from a linear map followed by a translation.

🔗

An affine map is linear only when \(\mathbf{b}=\mathbf{0}\text{.}\) A quick test is the zero vector: every linear map sends \(\mathbf{0}\) to \(\mathbf{0}\text{,}\) but

\begin{equation*} A\mathbf{0}+\mathbf{b}=\mathbf{b}. \end{equation*}

If \(\mathbf{b}\ne\mathbf{0}\text{,}\) the map is not linear.

🔗

Example 1.3.20. An affine layer.

A layer in a neural network can take the form

\begin{equation*} \mathbf{x}\mapsto W\mathbf{x}+\mathbf{b}. \end{equation*}

The matrix \(W\) mixes the input coordinates. The vector \(\mathbf{b}\) shifts the result. Since

\begin{equation*} W\mathbf{0}+\mathbf{b}=\mathbf{b}, \end{equation*}

this map is affine. It is linear exactly when \(\mathbf{b}=\mathbf{0}\text{.}\)

🔗

Prev Top Next