Matrices as maps, span, basis and the views of matrix multiplication

Before this lesson: nothing from this track; this is the first lesson. You need vectors in $\mathbb{R}^n$ (lists of $n$ real numbers), vector addition and multiplication by a number. Time: about 50 minutes, plus the notebook.

---

Why this matters #

A linear layer computes $y = Wx$. Every output is a combination of the columns of $W$, so all outputs live in the span of those columns. Independence and basis answer "how many directions are really there?": how many features carry new information, and whether coordinates are unique. The views of matrix multiplication are tools for every later lesson: the column view gives rank bounds, and the outer-product view is the language of low rank (SVD, PCA, LoRA, attention).

1. Predict first #

2. The picture #

Start in the plane. Write $e_1 = (1, 0)$ and $e_2 = (0, 1)$ for the standard basis vectors. Every $x = (x_1, x_2)$ equals $x_1 e_1 + x_2 e_2$. A $2 \times 2$ matrix $A$ with columns $a_1, a_2$ gives

So $Ae_1 = a_1$ and $Ae_2 = a_2$: the columns are where the basis vectors land. The unit square (spanned by $e_1, e_2$) goes to the parallelogram spanned by $a_1, a_2$. The grid lines go to parallel, evenly spaced lines, and the origin stays fixed. This is what "linear" looks like.

Interactive figure: loading…

To read a $2 \times 2$ matrix, draw its two columns:

Matrix	$Ae_1$, $Ae_2$	What it does to the plane
$\begin{pmatrix} 2 & 0 \\ 0 & 1/2 \end{pmatrix}$	$(2, 0)$, $(0, 1/2)$	stretch along $x$ by 2, squeeze along $y$ by 1/2
$\begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}$	$e_1$, $e_2$ turned by $\theta$	rotate by the angle $\theta$, counter-clockwise
$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$	$(1, 0)$, $(1, 1)$	shear: $(x, y) \mapsto (x + y, y)$
$\begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$	$(1, 0)$, $(0, -1)$	reflect across the $x$-axis
$\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$	$(1, 2)$, $(2, 4)$	flatten the plane onto the line through $(1, 2)$

The last row is the warning sign: parallel columns flatten. Every output $x_1(1, 2) + x_2(2, 4) = (x_1 + 2x_2)(1, 2)$ lies on one line, and the input direction $(2, -1)$ goes to zero.

Span, independence and basis, as pictures. The span of some vectors is everything their combinations reach: one nonzero vector spans a line through 0, two non-parallel vectors in $\mathbb{R}^3$ span a plane through 0. A third vector inside that plane adds no new direction: the three are dependent. A basis has enough vectors to reach everything and no extra ones; its size is the dimension.

Interactive figure: loading…

3. Definitions and main results #

Linear maps and their matrices #

A map $T: \mathbb{R}^n \to \mathbb{R}^m$ is linear if $T(\alpha x + \beta y) = \alpha T(x) + \beta T(y)$ for all vectors $x, y$ and all numbers $\alpha, \beta$. With $\alpha = \beta = 0$ this gives $T(0) = 0$. So a shift $x \mapsto x + b$ with $b \ne 0$ is not linear; it is affine.

Theorem (a linear map is fixed by the images of the basis vectors). Let $T$ be linear, and let $A$ be the $m \times n$ matrix whose column $j$ is $T(e_j)$. Then $T(x) = Ax$ for every $x$.

Proof.

1. Write $x = x_1 e_1 + \dots + x_n e_n$: the entries of $x$ are its coordinates in the standard basis.
2. Linearity gives $T(x) = x_1 T(e_1) + \dots + x_n T(e_n)$.
3. The product is defined by $(Ax)_i = \sum_j A_{ij} x_j$. Read column by column, this says $Ax = x_1 a_1 + \dots + x_n a_n$, where $a_j$ is column $j$ of $A$.
4. With $a_j = T(e_j)$, steps 2 and 3 give the same vector. $\blacksquare$

So once the basis is fixed, "matrix" and "linear map" are the same thing. The $n$ vectors $T(e_1), \dots, T(e_n)$ store everything about $T$.

Span, subspace, independence, basis, dimension #

Let $v_1, \dots, v_k \in \mathbb{R}^m$, and let $V = [v_1 \; \cdots \; v_k]$ be the $m \times k$ matrix with these columns.

• A linear combination is $c_1 v_1 + \dots + c_k v_k = Vc$, with $c = (c_1, \dots, c_k)$.
• The span is the set of all linear combinations: $\operatorname{span}(v_1, \dots, v_k) = \{Vc : c \in \mathbb{R}^k\} = C(V)$, the column space of $V$.
• A subspace is a set that contains 0 and is closed under addition and scaling. Every span is a subspace.
• $v_1, \dots, v_k$ are linearly independent if $c_1 v_1 + \dots + c_k v_k = 0$ only for $c = 0$. Otherwise they are dependent, and every $v_j$ with $c_j \ne 0$ is a combination of the others.
• A basis of a subspace $S$ is an independent list that spans $S$. The dimension $\dim S$ is the number of vectors in a basis.

Coordinates are unique. Let $v_1, \dots, v_k$ be a basis and $x = \sum_j c_j v_j = \sum_j d_j v_j$. Then $\sum_j (c_j - d_j) v_j = 0$, and independence gives $c_j = d_j$ for every $j$. The numbers $c_j$ are the coordinates of $x$ in that basis. Lesson 04 converts between bases.

The null-space test for independence #

Theorem (null-space test). The columns of $V$ are independent $\iff$ $N(V) = \{0\}$, where $N(V) = \{c : Vc = 0\}$ is the null space of $V$.

Proof. $Vc = c_1 v_1 + \dots + c_k v_k$. A nonzero $c$ with $Vc = 0$ is exactly a nontrivial combination that equals 0. $\blacksquare$

How to run the test. Use elimination (lesson 02 gives the full theory): subtract multiples of rows to create zeros below each pivot. A column without a pivot is free.

• Every column has a pivot: $N(V) = \{0\}$, the vectors are independent.
• Column $j$ is free: set $c_j = 1$ and the other free entries to 0, and solve for the pivot entries from the bottom row up. This gives a nonzero $c$ with $Vc = 0$: the dependency.

Corollary (too many vectors). More than $m$ vectors in $\mathbb{R}^m$ are always dependent. Each pivot needs its own row, so there are at most $m$ pivots. With $k > m$ columns, at least one column is free.

Dimension is well defined #

Lemma. If $w_1, \dots, w_n$ span a subspace $S$, then any $m > n$ vectors $v_1, \dots, v_m$ in $S$ are dependent.

Proof.

1. Each $v_j$ lies in $S = \operatorname{span}(w_1, \dots, w_n)$, so $v_j = \sum_i c_{ij} w_i$. In matrix form, $V = WC$ with $W = [w_1 \; \cdots \; w_n]$ and $C$ of size $n \times m$.
2. $C$ is wide ($m > n$), so by the corollary it has a vector $x \ne 0$ with $Cx = 0$.
3. Then $Vx = W(Cx) = 0$ with $x \ne 0$: the $v_j$ are dependent. $\blacksquare$

Theorem (every basis has the same size). If $v_1, \dots, v_m$ and $w_1, \dots, w_n$ are both bases of $S$, then $m = n$.

Proof. The $w$'s span $S$ and the $v$'s are independent, so the lemma rules out $m > n$. Hence $m \le n$. Swap the roles of the two bases: $n \le m$. $\blacksquare$

Two more consequences of the lemma (Axler 2.38 and 2.42): $n$ independent vectors in $\mathbb{R}^n$ also span it, and $n$ vectors that span $\mathbb{R}^n$ are also independent. So to decide whether $n$ vectors form a basis of $\mathbb{R}^n$, check one thing only: independence ($N(V) = \{0\}$, or $\det V \ne 0$ from lesson 03).

Four views of matrix multiplication #

Let $A$ be $m \times p$, with columns $a_1, \dots, a_p$ and rows $\alpha_1^\top, \dots, \alpha_m^\top$. Let $B$ be $p \times n$, with columns $b_1, \dots, b_n$ and rows $\beta_1^\top, \dots, \beta_p^\top$. The product $AB$ is $m \times n$.

View	Formula	What it says
entry	$(AB)_{ij} = \alpha_i^\top b_j = \sum_k A_{ik} B_{kj}$	row $i$ of $A$ times column $j$ of $B$
column	$AB = [Ab_1 \; \cdots \; Ab_n]$	each column of $AB$ is a combination of the columns of $A$
row	row $i$ of $AB$ $= \alpha_i^\top B$	each row of $AB$ is a combination of the rows of $B$
outer product	$AB = \sum_{k=1}^{p} a_k \beta_k^\top$	a sum of $p$ matrices of rank at most 1

Why they agree. All four compute the same numbers $\sum_k A_{ik} B_{kj}$; only the order of the loops changes. For the outer-product view: the $(i, j)$ entry of $a_k \beta_k^\top$ is $A_{ik} B_{kj}$, and the sum over $k$ gives $(AB)_{ij}$.

Interactive figure: loading…

Why the product is defined this way. $AB$ is the matrix of the composition "first $B$, then $A$": $(AB)x = A(Bx)$. Its column $j$ is $A(Be_j) = Ab_j$ (the column view), and the columns fix the map. Composition is associative, so $(AB)C = A(BC)$, but not commutative: "rotate, then shear" differs from "shear, then rotate".

Two consequences you will use all the time.

• Rank bound. By the column view, $C(AB) \subseteq C(A)$. By the row view, the row space of $AB$ lies inside the row space of $B$. So $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$ (lesson 02 defines rank and shows row rank = column rank).
• Low rank. An outer product $uv^\top$ with $u, v \ne 0$ has rank 1: column $j$ is $v_j u$. A sum of $k$ outer products $\sum_{i=1}^k u_i v_i^\top$ equals $UV^\top$, where $U$ has columns $u_1, \dots, u_k$ and $V$ has columns $v_1, \dots, v_k$. Its rank is at most $k$.

Cost. Every view needs $mpn$ multiplications and about as many additions; the views differ only in the loop order and the memory access. Blocked GEMM kernels on CPUs and GPUs use the outer-product order: they add up products of thin column blocks of $A$ and row blocks of $B$.

Answers to section 1. (1) No. Three vectors in $\mathbb{R}^2$ are more than $m = 2$, so they are dependent (corollary). (2) One. Column $j$ of $uv^\top$ is $v_j u$, a multiple of $u$, so all columns lie on one line: rank 1 when $u, v \ne 0$.

4. Worked example #

(a) A matrix as a map. $A = \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}$ sends $e_1 \mapsto (1, 0)$ and $e_2 \mapsto (1, 2)$. Without row-times-column:

The unit square goes to the parallelogram with corners $(0,0)$, $(1,0)$, $(2,2)$, $(1,2)$. The map is $(x, y) \mapsto (x + y, 2y)$: the shear $(x, y) \mapsto (x + y, y)$, then a vertical stretch by 2. The area becomes 2 (lesson 03: area scale $= |\det A|$).

(b) Independence and basis. Do $v_1 = (1, 2, 0)$, $v_2 = (0, 1, 1)$, $v_3 = (2, 5, 1)$ form a basis of $\mathbb{R}^3$? Put them as columns and eliminate:

Pivots are in columns 1 and 2; column 3 is free. Set $c_3 = 1$. Row 2 gives $c_2 + 1 = 0$, so $c_2 = -1$. Row 1 gives $c_1 + 2 = 0$, so $c_1 = -2$. So $c = (-2, -1, 1) \in N(V)$, and

Not a basis. The span is a plane with basis $\{v_1, v_2\}$, dimension 2. A normal vector of the plane is $v_1 \times v_2 = (2, -1, 1)$, so the plane is $2x - y + z = 0$. Check $v_3$: $4 - 5 + 1 = 0$ ✓.

Now replace $v_3$ by $w = (0, 0, 1)$: $2 \cdot 0 - 0 + 1 = 1 \ne 0$, so $w$ is outside the plane, and $v_1, v_2, w$ are three independent vectors in $\mathbb{R}^3$: a basis.

(c) Four views of one product.

• Entry: $(AB)_{21} = (2, 1) \cdot (1, 1) = 3$.
• Column: column 1 of $AB$ is $A(1, 1) = 1 \cdot (1, 2, 0) + 1 \cdot (0, 1, 3) = (1, 3, 3)$, and column 2 is $A(2, -1) = 2 \cdot (1, 2, 0) - (0, 1, 3) = (2, 3, -3)$.
• Row: row 2 of $AB$ is $2 \cdot (1, 2) + 1 \cdot (1, -1) = (3, 3)$.
• Outer products (column $k$ of $A$ times row $k$ of $B$):

5. In code #

NumPy checks the hand computations above. The notebook for this lesson has these cells and the exercises.

import numpy as np
from scipy.linalg import null_space

# (a) the columns are the images of e1 and e2
A = np.array([[1., 1.], [0., 2.]])
print(A @ np.array([1., 0.]), A @ np.array([0., 1.]))   # [1. 0.] [1. 2.]
print(A @ np.array([2., 1.]))                            # [3. 2.]

# (b) independence through the null space
V = np.array([[1., 0., 2.],
              [2., 1., 5.],
              [0., 1., 1.]])        # columns v1, v2, v3
c = null_space(V)[:, 0]             # unit length, any sign
print(np.linalg.matrix_rank(V), c / c[2])   # 2 [-2. -1.  1.]

# (c) the outer-product view adds up to the product
A3 = np.array([[1., 0.], [2., 1.], [0., 3.]])
B = np.array([[1., 2.], [1., -1.]])
outer_sum = sum(np.outer(A3[:, k], B[k, :]) for k in range(2))
print(np.array_equal(outer_sum, A3 @ B))    # True
print((A3 @ B).tolist())                    # [[1.0, 2.0], [3.0, 3.0], [3.0, -3.0]]

null_space returns a unit vector with an arbitrary sign; dividing by its last entry gives the hand scaling. With floats, libraries decide independence with a tolerance on the singular values (lessons 08 and 13).

6. Where it shows up #

• Neural networks. A linear layer $y = Wx$ outputs a combination of the columns of $W$, weighted by the input. With a bias, $y = Wx + b$ is affine, not linear. A one-hot input $e_j$ selects column $j$ of $W$; an embedding lookup is this product, done without the multiplication.
• Low rank. LoRA writes a weight update as $\Delta W = BA$, with $B$ of size $d \times r$ and $A$ of size $r \times k$. By the outer-product view, $\Delta W$ is a sum of $r$ rank-1 matrices, so $\operatorname{rank}(\Delta W) \le r$, with $r(d + k)$ parameters instead of $dk$. The attention score matrix $QK^\top$ has rank at most the head dimension $d_k$. Truncated SVD and PCA (lessons 08–09) keep the largest outer products.
• ML for science. A basis is a choice of coordinates for a field: empirical orthogonal functions (EOFs, the PCA basis) or spherical harmonics in climate science, Fourier modes in spectral solvers and Fourier neural operators. Keeping a few basis vectors means working in a subspace. Independence is identifiability: the effects of dependent predictors in a regression cannot be separated (lesson 02).

7. Common mistakes #

• Rows instead of columns. $Ae_j$ is column $j$ of $A$, not row $j$.
• Checking independence pair by pair. $(1, 0)$, $(0, 1)$, $(1, 1)$ are pairwise non-parallel, but they are dependent. Independence is about all combinations at once.
• Spanning set vs basis. A spanning set may contain extra vectors; a basis contains none. The dimension counts the vectors of a basis, not of any spanning set.
• $AB = BA$. False in general, even for square matrices; for non-square shapes $BA$ may not even exist.
• Forgetting the origin. A line that misses 0 is not a subspace, and $x \mapsto Wx + b$ with $b \ne 0$ is not a linear map.

8. Check yourself #

1. Which $2 \times 2$ matrix rotates the plane by $90°$ counter-clockwise? Find it from the images of $e_1$ and $e_2$.
   Answer

   $e_1 \mapsto (0, 1)$ and $e_2 \mapsto (-1, 0)$, so the columns give $A = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$.
2. Do $(1, 1, 0)$, $(1, 0, 1)$, $(0, 1, 1)$ form a basis of $\mathbb{R}^3$?
   Answer

   Yes. With the vectors as columns, $R_2 - R_1 = (0, -1, 1)$, then $R_3 + R_2 = (0, 0, 2)$: three pivots, so $N(V) = \{0\}$ and the vectors are independent. Three independent vectors in $\mathbb{R}^3$ also span it. (Also $\det V = -2 \ne 0$.)
3. $M = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$. Give its column space and its null space, and say what it does to the plane.
   Answer

   $C(M)$ is the line through $(1, 2)$. $N(M)$ is the line through $(2, -1)$, because $2 \cdot (1, 2) - 1 \cdot (2, 4) = 0$. The plane is flattened onto the line through $(1, 2)$, and the direction $(2, -1)$ goes to 0.
4. Compute $u_1 v_1^\top + u_2 v_2^\top$ for $u_1 = (1, 1)$, $v_1 = (1, 2)$, $u_2 = (1, -1)$, $v_2 = (3, 0)$, and write it as one matrix product.
   Answer

   $\begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix} + \begin{pmatrix} 3 & 0 \\ -3 & 0 \end{pmatrix} = \begin{pmatrix} 4 & 2 \\ -2 & 2 \end{pmatrix} = UV^\top$ with $U = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ (columns $u_1, u_2$) and $V^\top = \begin{pmatrix} 1 & 2 \\ 3 & 0 \end{pmatrix}$ (rows $v_1^\top, v_2^\top$).
5. Why is the map $x \mapsto Ax$ never one-to-one when $A$ is $2 \times 3$?
   Answer

   Its three columns are vectors in $\mathbb{R}^2$, so they are dependent: some $c \ne 0$ has $Ac = 0$. Then $A(x + c) = Ax$ for every $x$, so two different inputs give the same output.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. What is column $j$ of a matrix $A$, as a map?

   Show answer

2. Write $Ax$ as a combination of columns.

   Show answer

3. What does a $2 \times 2$ matrix with parallel columns do to the plane?

   Show answer

4. Define linearly independent.

   Show answer

5. How do you test whether given vectors are independent?

   Show answer

6. Why are 4 vectors in $\mathbb{R}^3$ always dependent?

   Show answer

7. What is a basis, and what is the dimension?

   Show answer

8. Name the four views of the product $AB$.

   Show answer

9. What is the rank of $uv^\top$ for nonzero $u, v$?

   Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What does a matrix do, geometrically?" — It sends the basis vectors to its columns; linearity fixes the rest. Know the $2 \times 2$ cases: stretch, rotation, shear, reflection, flattening.
• "Give the ways to compute $AB$, and when each is useful." — Entry (dot products); column (outputs live in $C(A)$); row; outer product (low-rank sums, GEMM accumulation, LoRA, SVD).
• "How do you check if vectors are independent? And with floats?" — Null space or rank by elimination in exact arithmetic; with floats, compare the smallest singular value with the largest.
• "Why does every basis have the same size?" — If $n$ vectors span, any $n + 1$ vectors are dependent, because a wide coefficient matrix has a nonzero null vector.

10. Practice #

The notebook for this lesson runs in Colab. It has four short exercises, each with a check cell and a folded solution:

1. Build the $90°$ rotation and a shear from the images of $e_1$ and $e_2$ (a helper in the notebook draws what a matrix does to a grid).
2. Write matmul_columns, matmul_rows and matmul_outer with loops, and check all of them against A @ B.
3. Decide independence and find a dependency with the null space (scipy.linalg.null_space).
4. Is $b$ reachable? Test whether a vector lies in the column space of a $3 \times 2$ matrix.

11. Watch and read #

Linear combinations, span, and basis vectors3Blue1Brown · Essence of linear algebra, chapter 2 · 10 min

Linear transformations and matrices3Blue1Brown · Essence of linear algebra, chapter 3 · 11 min

Matrix multiplication as composition3Blue1Brown · Essence of linear algebra, chapter 4 · 10 min

• Gilbert Strang, MIT 18.06 (2010), lecture 9: Independence, basis, and dimension; lecture 3 shows the views of $AB$.
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS), free PDF: §5.1–5.2 (independence, basis) and §10.1 (row, column and outer-product views of $AB$).
• Sheldon Axler, Linear Algebra Done Right, 4th edition, free PDF: §2A–2C (2.22 is the lemma of section 3, 2.34 the equal-size theorem).