7. Linear Transformations

Chapter 6 studied vector spaces as objects. This chapter studies the functions between them that respect addition and scaling, the linear maps, which are what matrices really are: every matrix is a linear map written in coordinates, and every linear map between finite-dimensional spaces becomes a matrix once bases are chosen. The chapter connects geometry, calculus, and computation through kernel, image, and rank-nullity, then builds dual spaces and quotient spaces, the tools for reasoning about linear maps without coordinates.

<a id="71-definition-and-examples"></a>

7.1 Definition and Examples

This subchapter defines linear maps, derives their first properties, and builds a catalogue of examples: the geometric maps of the plane, projections, and the operators of calculus.

Linear Map Definition and Properties

Why it matters. Section 3.2 observed that $\mathbf{x} \mapsto A\mathbf{x}$ satisfies $A(\mathbf{u} + \mathbf{v}) = A\mathbf{u} + A\mathbf{v}$ and $A(c\mathbf{u}) = c,A\mathbf{u}$. Differentiation obeys the same two rules, and so do integration, transposition, expectation, and sampling a signal. These two rules are what make superposition work: if you know how a system responds to a few simple inputs, you know how it responds to every combination of them. Vector spaces are the objects of linear algebra; linear maps are the arrows between them.

Analogy. Section 6.1 described a vector space as an interface with two methods, add and scale. A linear map is an adapter between two implementations that commutes with the interface: adding first and then translating gives the same result as translating first and then adding. A currency converter with no fees behaves this way. Converting 30 + 20 euros gives the same dollars as converting each amount and adding, and converting 3 times 10 euros gives 3 times the conversion of 10. A converter that charges a fixed fee per transaction fails both rules, and it is exactly an affine map $x \mapsto ax + b$, not a linear one.

Definition. Let $V$ and $W$ be vector spaces over the same field $F$. A function $T : V \to W$ is a linear map (or linear transformation) if, for all $\mathbf{u}, \mathbf{v} \in V$ and all $c \in F$,

1. $T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v})$ (additivity), and
2. $T(c\mathbf{u}) = c,T(\mathbf{u})$ (homogeneity).

When $V = W$, $T$ is called a linear operator on $V$. The two conditions are equivalent to the single test

$$T(c\mathbf{u} + \mathbf{v}) = c,T(\mathbf{u}) + T(\mathbf{v}) \quad \text{for all } \mathbf{u}, \mathbf{v} \in V,\ c \in F.$$

Taking $c = 1$ gives additivity. Taking $\mathbf{u} = \mathbf{v} = \mathbf{0}$ and $c = 1$ gives $T(\mathbf{0}) = 2T(\mathbf{0})$, so $T(\mathbf{0}) = \mathbf{0}$; then $\mathbf{v} = \mathbf{0}$ gives homogeneity.

First consequences.

Property	One-line proof
$T(\mathbf{0}) = \mathbf{0}$	$T(\mathbf{0}) = T(0 \cdot \mathbf{0}) = 0 \cdot T(\mathbf{0}) = \mathbf{0}$
$T(-\mathbf{v}) = -T(\mathbf{v})$	homogeneity with $c = -1$
$T(\mathbf{u} - \mathbf{v}) = T(\mathbf{u}) - T(\mathbf{v})$	combine the two rows above with additivity
$T\big(\sum_i c_i\mathbf{v}_i\big) = \sum_i c_i,T(\mathbf{v}_i)$	induction on the number of terms (Section 1.1)

The last row is the essential one: linear maps preserve linear combinations. It follows that $T$ maps $\operatorname{span}{\mathbf{v}_1, \dots, \mathbf{v}_k}$ onto $\operatorname{span}{T\mathbf{v}_1, \dots, T\mathbf{v}_k}$, sends subspaces to subspaces, and sends a line $\mathbf{p} + t\mathbf{d}$ to the line (or single point) $T\mathbf{p} + t,T\mathbf{d}$.

A linear map is determined by a basis.

Theorem. Let $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a basis of $V$, and let $\mathbf{w}_1, \dots, \mathbf{w}_n$ be any vectors in $W$ (repeats and dependencies allowed). There is exactly one linear map $T : V \to W$ with $T(\mathbf{v}_i) = \mathbf{w}_i$ for every $i$.

Proof. Each $\mathbf{v} \in V$ has unique coordinates, $\mathbf{v} = \sum c_i\mathbf{v}_i$. Uniqueness: any linear $T$ with the required values must satisfy $T(\mathbf{v}) = \sum c_i\mathbf{w}_i$. Existence: define $T$ by that formula. The coordinates of $a\mathbf{u} + \mathbf{v}$ are $a$ times those of $\mathbf{u}$ plus those of $\mathbf{v}$ (the coordinate map is linear, Section 6.5), so $T$ is linear. $\blacksquare$

In practice, storing a linear map out of an $n$-dimensional space takes exactly $n$ vectors, the images of the basis. Section 7.2 stores them as the columns of a matrix.

Examples and non-examples.

Map	Linear?	Reason
$\mathbb{R}^n \to \mathbb{R}^m$, $\mathbf{x} \mapsto A\mathbf{x}$	Yes	matrix-vector multiplication distributes (Section 3.2)
$\mathbb{R}^2 \to \mathbb{R}^2$, $\mathbf{x} \mapsto \mathbf{x} + (1, 0)$	No	translation moves $\mathbf{0}$
$\mathbb{R} \to \mathbb{R}$, $x \mapsto 3x + 2$	No	"linear function" in calculus means affine here
$\mathbb{R}^n \to \mathbb{R}$, $\mathbf{x} \mapsto \lVert\mathbf{x}\rVert$	No	$\lVert -\mathbf{x}\rVert = \lVert\mathbf{x}\rVert \ne -\lVert\mathbf{x}\rVert$
$\mathbb{P}_n \to \mathbb{R}$, $p \mapsto p(2)$	Yes	$(p + q)(2) = p(2) + q(2)$, $(cp)(2) = c,p(2)$
$\mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n}$, $A \mapsto A^T$	Yes	$(A + B)^T = A^T + B^T$, $(cA)^T = cA^T$
$\mathbb{R}^{n \times n} \to \mathbb{R}$, $A \mapsto \operatorname{tr}A$	Yes	the sum of diagonal entries is additive
$\mathbb{R}^{n \times n} \to \mathbb{R}$, $A \mapsto \det A$ ($n \ge 2$)	No	$\det(2I) = 2^n \ne 2\det I$
$\mathbb{R}^{n \times n} \to \mathbb{R}^{n \times n}$, $A \mapsto A^2$	No	$(2A)^2 = 4A^2$
$\mathbb{C} \to \mathbb{C}$, $z \mapsto \bar z$	Over $\mathbb{R}$: yes. Over $\mathbb{C}$: no	$\overline{iz} = -i\bar z \ne i\bar z$

The last row shows that linearity depends on which scalars are allowed (Section 1.2).

Testing linearity. $T(\mathbf{0}) = \mathbf{0}$ is necessary but not sufficient, and so is homogeneity alone. The map $f(x, y) = \sqrt[3]{x^3 + y^3}$ satisfies $f(c\mathbf{x}) = c f(\mathbf{x})$ for every real $c$, but $f(1, 0) + f(0, 1) = 2$ while $f(1, 1) = 2^{1/3} \approx 1.26$. Always check both rules, or the combined test.

           before T                                  after a linear T

   +-----+-----+-----+                          .-----.-----.-----.
   |     |     |     |                         /     /     /     /
   +-----+-----+-----+            T           .-----.-----.-----.
   |     |     |     |        --------->     /     /     /     /
   O-----+-----+-----+                      O-----.-----.-----.

   the origin stays fixed, grid lines stay straight and parallel,
   and equally spaced points stay equally spaced

import numpy as np

rng = np.random.default_rng(0)

def looks_linear(T, n, trials=200):
    """Randomly test T(c u + v) = c T(u) + T(v). One failure disproves linearity."""
    for _ in range(trials):
        u, v, c = rng.normal(size=n), rng.normal(size=n), rng.normal()
        if not np.allclose(T(c * u + v), c * T(u) + T(v)):
            return False
    return True                                    # evidence, not proof

A = np.array([[1.0, 2.0, 0.0], [0.0, -1.0, 3.0]])
print(looks_linear(lambda x: A @ x, 3))                                   # True
print(looks_linear(lambda x: np.array([x[1], x[0] - 4 * x[2]]), 3))      # True
print(looks_linear(lambda x: x + np.array([1.0, 0.0]), 2))                # False: moves the origin
print(looks_linear(lambda x: np.array([np.linalg.norm(x)]), 2))           # False
print(looks_linear(lambda x: np.array([np.cbrt(x[0]**3 + x[1]**3)]), 2))  # False: homogeneous, not additive

# A linear map is fixed by the images of a basis.
# Basis of R^2: b1 = (1, 1), b2 = (1, -1). Choose T(b1) = (2, 0, 1) and T(b2) = (0, 4, 1).
B = np.array([[1.0, 1.0], [1.0, -1.0]])                # basis vectors as columns
W = np.array([[2.0, 0.0], [0.0, 4.0], [1.0, 1.0]])     # their chosen images as columns

def T(x):
    c = np.linalg.solve(B, x)     # coordinates of x in the basis (Section 6.5)
    return W @ c                  # the same combination of the images

print(T(np.array([3.0, 1.0])))    # [4. 4. 3.]: (3, 1) = 2 b1 + 1 b2, so T = 2(2, 0, 1) + (0, 4, 1)

Key takeaways

• $T$ is linear when $T(c\mathbf{u} + \mathbf{v}) = c,T(\mathbf{u}) + T(\mathbf{v})$; equivalently, it preserves all linear combinations.
• Every linear map fixes the origin; translations and "$ax + b$" functions are affine, not linear.
• A linear map is completely determined by the images of a basis, and those images can be chosen freely.
• Whether a map is linear can depend on the field of scalars, as with complex conjugation.
• To disprove linearity, one counterexample suffices; random testing can only disprove.

🧪 Practice

1. Decide which maps are linear, proving it or giving a counterexample: $T(x, y) = (y, x)$; $T(x, y) = (xy, x)$; $T(x, y) = (x + 1, y)$; $T : \mathbb{P}n \to \mathbb{P}{n+1}$, $T(p) = x,p(x)$; $T : \mathbb{P}_n \to \mathbb{P}_n$, $T(p) = p + p'$.
2. A linear map $T : \mathbb{R}^2 \to \mathbb{R}^2$ satisfies $T(1, 2) = (3, -1)$ and $T(0, 1) = (1, 1)$. Find $T(4, 5)$ and a formula for $T(x, y)$.
3. Show that if $\mathbf{v}_1, \dots, \mathbf{v}_k$ are linearly dependent and $T$ is linear, then $T\mathbf{v}_1, \dots, T\mathbf{v}_k$ are dependent. Give an example where independent vectors are mapped to dependent ones.
4. Interview: A colleague says that $f(x) = 2x + 3$ is linear "because its graph is a straight line." Explain precisely why it is not linear in the linear algebra sense, and how it can be made linear by working in one more dimension. Hint: check $f(0)$; then consider the map $(x, 1) \mapsto (2x + 3, 1)$ and write it as a $2 \times 2$ matrix (homogeneous coordinates, Section 2.1).

Geometric Transformations in R^2

Why it matters. The plane is where linear maps can be seen. Every later theorem has a picture here: the determinant as an area factor (Chapter 5), eigenvectors as directions that are only stretched (Chapter 8), and singular values as the axes of an ellipse (Chapter 11). The same maps drive computer graphics, image warping, and data augmentation in machine learning.

The columns tell the whole story. Because $T(x, y) = x,T(\mathbf{e}_1) + y,T(\mathbf{e}_2)$, a linear map of the plane is fixed by where it sends $\mathbf{e}_1 = (1, 0)$ and $\mathbf{e}_2 = (0, 1)$. These two images are the columns of its matrix, $A = [,T(\mathbf{e}_1)\ \ T(\mathbf{e}_2),]$. The unit square goes to the parallelogram spanned by the columns, and every cell of the coordinate grid goes to a translated copy of that parallelogram.

   y                                         y
   |                                         |
 1 +-----+  e2 = (0, 1)                    1 +     .-----------.   T(e2) = (1, 1)
   |     |                                   |    /           /
   |     |            A = [ 2  1 ]           |   /           /
   |     |                [ 0  1 ]           |  /           /
 0 O-----+------> x                        0 O-----------.--------> x
   0     1  e1 = (1, 0)                      0           2      T(e1) = (2, 0)

   unit square, area 1                       parallelogram, area |det A| = 2

What every linear map of the plane does and does not preserve.

Always preserved	Not preserved in general
the origin	lengths
straight lines (a line may collapse to a point)	angles
parallelism	areas, which are multiplied by $\lvert\det A\rvert$ (Section 5.3)
ratios along a line, such as midpoints	orientation, which flips when $\det A < 0$
linear combinations	circles, which become ellipses

Three kinds of maps, by rank.

• Rank 2 ($\det A \ne 0$): a bijection of the plane. The grid becomes a grid of parallelograms, and the unit circle becomes an ellipse whose semi-axes are the singular values of $A$ (Chapter 11).
• Rank 1: the columns are parallel, and the whole plane collapses onto a line through the origin. Every line parallel to the collapsed direction goes to a single point.
• Rank 0: the zero map, which sends everything to the origin.

Reading a map from data. If you know $T$ on two independent vectors $\mathbf{u}_1, \mathbf{u}_2$ rather than on $\mathbf{e}_1, \mathbf{e}_2$, then $A[,\mathbf{u}_1\ \mathbf{u}_2,] = [,T\mathbf{u}_1\ T\mathbf{u}_2,]$, so

$$A = [,T\mathbf{u}_1\ \ T\mathbf{u}_2,],[,\mathbf{u}_1\ \ \mathbf{u}_2,]^{-1}.$$

This is how image-registration software recovers a linear warp from matched landmarks.

import numpy as np

def shoelace(P):
    """Signed area of a polygon whose vertices are the columns of P (counterclockwise gives > 0)."""
    x, y = P
    return 0.5 * np.sum(x * np.roll(y, -1) - np.roll(x, -1) * y)

# An "L" shape traversed counterclockwise; asymmetric, so flips are visible
L = np.array([[0, 2, 2, 1, 1, 0],
              [0, 0, 1, 1, 3, 3]], dtype=float)
print(shoelace(L))                                      # 4.0

maps = {
    "stretch+shear": np.array([[2.0, 1.0], [0.0, 1.0]]),
    "reflection":    np.array([[1.0, 0.0], [0.0, -1.0]]),
    "rank one":      np.array([[1.0, 2.0], [2.0, 4.0]]),
}
for name, A in maps.items():
    ratio = shoelace(A @ L) / shoelace(L)                # signed area factor of the image
    print(f"{name:13s} area ratio {ratio:+.1f}   det {np.linalg.det(A):+.1f}")
# stretch+shear area ratio +2.0   det +2.0
# reflection    area ratio -1.0   det -1.0     (negative: orientation reversed)
# rank one      area ratio +0.0   det +0.0     (the L collapses onto a line)

# The unit circle becomes an ellipse whose semi-axes are the singular values
A = maps["stretch+shear"]
t = np.linspace(0, 2 * np.pi, 100_000)
radii = np.linalg.norm(A @ np.vstack([np.cos(t), np.sin(t)]), axis=0)
print(np.round([radii.max(), radii.min()], 4), np.round(np.linalg.svd(A, compute_uv=False), 4))
# [2.2882 0.874 ] [2.2882 0.874 ]: longest and shortest radius = singular values

# Recover a map from two input/output pairs: T(1, 2) = (1, 0) and T(1, 3) = (0, 1)
U = np.array([[1.0, 1.0], [2.0, 3.0]])                  # inputs as columns
TU = np.array([[1.0, 0.0], [0.0, 1.0]])                 # outputs as columns
print(TU @ np.linalg.inv(U))                            # A = [T u1  T u2] [u1  u2]^{-1}
# [[ 3. -1.]
#  [-2.  1.]]

Key takeaways

• The columns of a $2 \times 2$ matrix are the images of $\mathbf{e}_1$ and $\mathbf{e}_2$; the unit square becomes the parallelogram they span.
• Linear maps keep the origin fixed and preserve lines, parallelism, and ratios along lines; they generally change lengths, angles, and areas.
• Areas are multiplied by $\lvert\det A\rvert$, and orientation reverses exactly when $\det A < 0$.
• A rank-1 map collapses the plane onto a line; an invertible map sends circles to ellipses.
• From two independent input/output pairs, $A = [,T\mathbf{u}_1\ T\mathbf{u}_2,][,\mathbf{u}_1\ \mathbf{u}_2,]^{-1}$.

🧪 Practice

1. Sketch the image of the unit square under $A = \begin{bmatrix} 1 & -1 \ 2 & 1 \end{bmatrix}$. Compute its area and decide whether the orientation is preserved.
2. A linear map sends $(1, 1) \mapsto (3, 1)$ and $(1, -1) \mapsto (1, 3)$. Find its matrix, the area of the image of the unit disk, and whether it reverses orientation.
3. For the rank-1 matrix $\begin{bmatrix} 1 & 2 \ 2 & 4 \end{bmatrix}$, find the line onto which the plane collapses and the family of lines that are each sent to a single point.
4. Interview: A data-augmentation pipeline warps image coordinates by random $2 \times 2$ matrices. Which property of the sampled matrices must be controlled so that images are not squashed into near-lines, and how would you sample "safe" matrices? Hint: keep $\lvert\det A\rvert$ and the ratio of the singular values within bounds; one way is to compose a random rotation, a scaling with factors in $[a, b]$ where $a > 0$, and a small shear.

Rotations, Reflections, Shears, and Scalings

Why it matters. These four families are the building blocks of plane geometry. Every invertible $2 \times 2$ matrix is a rotation, followed by a scaling along the axes, followed by another rotation or a reflection (the singular value decomposition, Chapter 11). Knowing their matrices by heart lets you read a transformation at a glance.

The catalogue.

Name	Matrix	$\det$	Preserves	Inverse
Rotation by $\theta$	$R_\theta = \begin{bmatrix} \cos\theta & -\sin\theta \ \sin\theta & \cos\theta \end{bmatrix}$	$1$	lengths, angles, orientation	$R_{-\theta} = R_\theta^T$
Reflection across the line at angle $\theta$	$H_\theta = \begin{bmatrix} \cos 2\theta & \sin 2\theta \ \sin 2\theta & -\cos 2\theta \end{bmatrix}$	$-1$	lengths, angles; reverses orientation	$H_\theta$ itself
Horizontal shear by $k$	$\begin{bmatrix} 1 & k \ 0 & 1 \end{bmatrix}$	$1$	areas, horizontal lines	shear by $-k$
Scaling	$\begin{bmatrix} s_1 & 0 \ 0 & s_2 \end{bmatrix}$	$s_1 s_2$	the two axis directions	$\operatorname{diag}(1/s_1, 1/s_2)$

Rotation. Rotating $\mathbf{e}_1$ by $\theta$ gives $(\cos\theta, \sin\theta)$. The vector $\mathbf{e}_2$ is $\mathbf{e}1$ turned by $90°$, so it goes to $(\cos(\theta + 90°), \sin(\theta + 90°)) = (-\sin\theta, \cos\theta)$. These are the two columns of $R\theta$.

            y
            |
   R e2 =   |       . R e1 = (cos t, sin t)
  (-sin t,  |     .
    cos t) .|   .
            . .  t
   ---------O------------- x

Reflection. Let $\mathbf{u} = (\cos\theta, \sin\theta)$ be a unit vector along the mirror line. The projection of $\mathbf{x}$ onto the line is $P\mathbf{x} = \mathbf{u}\mathbf{u}^T\mathbf{x}$ (next topic). Reflecting moves $\mathbf{x}$ twice as far as projecting, in the same direction: $H\mathbf{x} = \mathbf{x} + 2(P\mathbf{x} - \mathbf{x}) = (2P - I)\mathbf{x}$. So

$$H_\theta = 2\mathbf{u}\mathbf{u}^T - I = \begin{bmatrix} 2\cos^2\theta - 1 & 2\cos\theta\sin\theta \ 2\cos\theta\sin\theta & 2\sin^2\theta - 1 \end{bmatrix} = \begin{bmatrix} \cos 2\theta & \sin 2\theta \ \sin 2\theta & -\cos 2\theta \end{bmatrix}.$$

              x  *
                  \      mirror line through O at angle theta
                   \  .-'
                    *'        P x : foot of the perpendicular
                 .-' \
              .-'     \
          O.-'         *  H x = 2 P x - x

Shear. A horizontal shear moves each point sideways by an amount proportional to its height, like pushing the top of a deck of cards. Heights do not change, so areas are preserved ($\det = 1$), but lengths and angles change.

Scaling. $\operatorname{diag}(s_1, s_2)$ stretches the axes by $s_1$ and $s_2$. A uniform scaling $sI$ multiplies every length by $\lvert s\rvert$. A negative entry adds a reflection: $\operatorname{diag}(-1, 1)$ reflects across the $y$-axis. However, $\operatorname{diag}(-1, -1) = -I = R_{180°}$ is a rotation, not a reflection, because its determinant is $+1$.

How they combine.

• $R_\alpha R_\beta = R_{\alpha + \beta}$, so plane rotations commute.
• Two reflections make a rotation: $H_\alpha H_\beta = R_{2(\alpha - \beta)}$. The determinants confirm it: $(-1)(-1) = 1$.
• Every $2 \times 2$ matrix $Q$ with $Q^TQ = I$ is a rotation ($\det Q = 1$) or a reflection ($\det Q = -1$).
• A rotation is a product of three shears: $R_\theta = S_x(-\tan\tfrac{\theta}{2}),S_y(\sin\theta),S_x(-\tan\tfrac{\theta}{2})$, where $S_x(k) = \begin{bmatrix} 1 & k \ 0 & 1 \end{bmatrix}$ and $S_y(k) = \begin{bmatrix} 1 & 0 \ k & 1 \end{bmatrix}$. Image editors have used this to rotate bitmaps, since each shear only slides whole rows or whole columns of pixels.
• In $\mathbb{R}^3$, rotations about the coordinate axes have the same $2 \times 2$ block inside a $3 \times 3$ identity, and in general they do not commute.

import numpy as np

def rot(t):
    c, s = np.cos(t), np.sin(t)
    return np.array([[c, -s], [s, c]])

def refl(t):                                   # reflection across the line through 0 at angle t
    c, s = np.cos(2 * t), np.sin(2 * t)
    return np.array([[c, s], [s, -c]])

def shear_x(k):
    return np.array([[1.0, k], [0.0, 1.0]])

def shear_y(k):
    return np.array([[1.0, 0.0], [k, 1.0]])

a, b = 0.7, 0.4
print(np.allclose(rot(a) @ rot(b), rot(a + b)))            # True: angles add
print(np.allclose(rot(a).T @ rot(a), np.eye(2)))           # True: the inverse is the transpose
print(np.allclose(refl(a) @ refl(a), np.eye(2)))           # True: reflecting twice changes nothing
print(np.allclose(refl(a) @ refl(b), rot(2 * (a - b))))    # True: two reflections make a rotation

u = np.array([np.cos(a), np.sin(a)])
print(np.allclose(refl(a), 2 * np.outer(u, u) - np.eye(2)))   # True: H = 2 u u^T - I
print(np.allclose(np.diag([-1.0, -1.0]), rot(np.pi)))          # True: -I is a rotation by 180 degrees

# A rotation as three shears
t = 0.9
print(np.allclose(shear_x(-np.tan(t / 2)) @ shear_y(np.sin(t)) @ shear_x(-np.tan(t / 2)), rot(t)))  # True

x = np.array([1.0, 2.0])
for name, M in [("rotation", rot(a)), ("reflection", refl(a)),
                ("shear", shear_x(1.5)), ("scaling", np.diag([3.0, 0.5]))]:
    print(f"{name:10s} det {np.linalg.det(M):+.2f}   |x| = {np.linalg.norm(x):.3f} -> |Mx| = {np.linalg.norm(M @ x):.3f}")
# rotation   det +1.00   |x| = 2.236 -> |Mx| = 2.236
# reflection det -1.00   |x| = 2.236 -> |Mx| = 2.236
# shear      det +1.00   |x| = 2.236 -> |Mx| = 4.472     (area kept, length changed)
# scaling    det +1.50   |x| = 2.236 -> |Mx| = 3.162

Key takeaways

• $R_\theta$ has columns $(\cos\theta, \sin\theta)$ and $(-\sin\theta, \cos\theta)$; it preserves lengths and orientation, and $R_\theta^{-1} = R_\theta^T$.
• A reflection across a line with unit direction $\mathbf{u}$ is $2\mathbf{u}\mathbf{u}^T - I$; it has determinant $-1$ and is its own inverse.
• Shears preserve area but not lengths or angles; scalings stretch along the axes.
• Rotations of the plane commute, and two reflections compose to a rotation by twice the angle between their mirrors.
• $-I$ in the plane is a rotation by $180°$, not a reflection.

🧪 Practice

1. Write the matrices of: rotation by $90°$ counterclockwise, reflection across $y = x$, reflection across $y = -x$, and the horizontal shear with $k = 2$. Compute the image of $(1, 2)$ under each.
2. Show that reflecting across the $x$-axis and then across the line $y = x$ is a rotation, and find its angle.
3. Find the matrix of the reflection across the line $y = 2x$. Verify that it fixes $(1, 2)$ and sends $(-2, 1)$ to $(2, -1)$.
4. Interview: Why do game engines and graphics APIs represent 3D transformations with $4 \times 4$ matrices instead of $3 \times 3$? Hint: a translation is not linear, since it moves the origin; in homogeneous coordinates (Section 2.1) it becomes a linear map in one dimension higher, so rotation, scaling, and translation all compose by matrix multiplication.

Projections

Why it matters. Projection is how we split a vector into "the part we keep" and "the part we discard". Least squares (Chapter 9) projects a data vector onto the column space of a model. PCA projects data onto a few principal directions. Computer graphics projects scenes onto planes to cast shadows. All of these share one algebraic signature.

Analogy. A projection is a shadow on the floor. When the sun is directly overhead, the shadow is an orthogonal projection; when the sun is low, it is an oblique projection. Either way, the shadow of a shadow is the shadow itself.

Definition. A linear operator $P : V \to V$ is a projection if $P^2 = P$. Such an operator is called idempotent: applying it twice gives the same result as applying it once.

Theorem (structure of a projection). If $P$ is a projection, then

1. $\operatorname{im} P = {\mathbf{v} : P\mathbf{v} = \mathbf{v}}$: the image consists of exactly the vectors that $P$ leaves fixed;
2. $V = \operatorname{im} P \oplus \ker P$ (direct sum, Section 6.2);
3. $I - P$ is also a projection, with $\operatorname{im}(I - P) = \ker P$ and $\ker(I - P) = \operatorname{im} P$.

Proof. (1) If $\mathbf{v} = P\mathbf{u}$, then $P\mathbf{v} = P^2\mathbf{u} = P\mathbf{u} = \mathbf{v}$; the converse is clear. (2) Write $\mathbf{v} = P\mathbf{v} + (\mathbf{v} - P\mathbf{v})$. The first term lies in $\operatorname{im} P$, and $P(\mathbf{v} - P\mathbf{v}) = P\mathbf{v} - P^2\mathbf{v} = \mathbf{0}$, so the second lies in $\ker P$. If $\mathbf{w}$ lies in both, then by (1) $\mathbf{w} = P\mathbf{w} = \mathbf{0}$. (3) $(I - P)^2 = I - 2P + P^2 = I - P$, and the two equalities follow from (1) and (2). $\blacksquare$

The converse also holds. If $V = U \oplus W$, every $\mathbf{v}$ splits uniquely as $\mathbf{u} + \mathbf{w}$, and $P\mathbf{v} = \mathbf{u}$ defines a projection, the projection onto $U$ along $W$. So projections correspond exactly to direct-sum decompositions, and a projection is specified by two subspaces: where the shadow falls ($U$) and the direction of the light ($W$).

      orthogonal projection onto U                oblique projection onto U along W

              v *                                         v *
                |                                            \
                |  v - Pv is perpendicular to U               \  v - Pv lies in W
                |                                              \
   -----O-------*----------------- U          -----O------------*------------ U
               Pv                                               Pv

Orthogonal projections in $\mathbb{R}^n$. Using the dot product:

Target	Projection matrix	Source
line spanned by $\mathbf{a}$	$P = \dfrac{\mathbf{a}\mathbf{a}^T}{\mathbf{a}^T\mathbf{a}}$	vector projection, Section 2.3
subspace with orthonormal basis $Q$ (as columns)	$P = QQ^T$	Chapter 9
column space of $A$ (independent columns)	$P = A(A^TA)^{-1}A^T$	normal equations, Chapter 9

A real projection matrix is an orthogonal projection exactly when $P^T = P$. If $P$ is symmetric, the residual is perpendicular to every vector in the image: $(\mathbf{v} - P\mathbf{v}) \cdot P\mathbf{w} = \mathbf{v}^T(I - P)^TP\mathbf{w} = \mathbf{v}^T(P - P^2)\mathbf{w} = 0$.

An oblique example. Project $\mathbb{R}^2$ onto the $x$-axis along the direction $(1, 1)$. Since $(x, y) = (x - y)(1, 0) + y(1, 1)$,

$$P(x, y) = (x - y, 0), \qquad P = \begin{bmatrix} 1 & -1 \ 0 & 0 \end{bmatrix}, \qquad P^2 = P, \qquad P^T \ne P.$$

Compare it with the orthogonal projection onto the same axis, $\begin{bmatrix} 1 & 0 \ 0 & 0 \end{bmatrix}$. Both have the same image, but their kernels differ.

Useful facts. For every projection, $\operatorname{tr}P = \operatorname{rank}P$. In a basis adapted to $\operatorname{im}P \oplus \ker P$ its matrix is $\operatorname{diag}(1, \dots, 1, 0, \dots, 0)$, so its only possible eigenvalues are $0$ and $1$ (Section 7.2, Chapter 8).

import numpy as np

a = np.array([1.0, 2.0, 2.0])
P = np.outer(a, a) / (a @ a)                       # orthogonal projection onto the line through a
v = np.array([3.0, 0.0, 3.0])
print(P @ v)                                       # [1. 2. 2.]: (a.v / a.a) a = (9 / 9) a
print(np.allclose(P @ P, P), np.allclose(P, P.T))  # True True
print(np.isclose((v - P @ v) @ a, 0))              # True: the residual is perpendicular to a
print(round(np.trace(P), 10), np.linalg.matrix_rank(P))   # 1.0 1: trace equals rank

# Onto the plane spanned by the columns of A (formula derived in Chapter 9)
A = np.array([[1.0, 0.0], [1.0, 1.0], [0.0, 1.0]])
P2 = A @ np.linalg.inv(A.T @ A) @ A.T
print(np.allclose(P2 @ P2, P2), round(np.trace(P2), 10))  # True 2.0

# Oblique: onto the x-axis along (1, 1)
Q = np.array([[1.0, -1.0], [0.0, 0.0]])
print(np.allclose(Q @ Q, Q), np.allclose(Q, Q.T))  # True False: a projection, but not orthogonal
w = np.array([3.0, 1.0])
print(Q @ w, w - Q @ w)                            # [2. 0.] [1. 1.]: shadow on the axis, residual along (1, 1)
I = np.eye(2)
print(np.allclose((I - Q) @ (I - Q), I - Q))       # True: the complementary projection

Key takeaways

• A projection is a linear operator with $P^2 = P$; it fixes every vector in its image.
• Every projection splits the space as $V = \operatorname{im}P \oplus \ker P$, and every direct sum defines a projection: "onto $U$ along $W$".
• $I - P$ is the complementary projection, with image and kernel swapped.
• A real projection matrix is orthogonal exactly when it is symmetric; $\mathbf{a}\mathbf{a}^T/(\mathbf{a}^T\mathbf{a})$ projects onto the line through $\mathbf{a}$.
• $\operatorname{tr}P = \operatorname{rank}P$ for every projection.

🧪 Practice

1. Find the matrix of the orthogonal projection of $\mathbb{R}^2$ onto the line spanned by $(3, 4)$, and verify $P^2 = P$ and $P^T = P$.
2. Find the projection of $\mathbb{R}^2$ onto $\operatorname{span}{(1, 0)}$ along $\operatorname{span}{(2, 1)}$. Check $P^2 = P$ and identify its image and kernel.
3. Prove that if $P$ is a projection, then $\operatorname{im}(I - P) = \ker P$. Then show that the only invertible projection is $I$.
4. Interview: A teammate's code checks that P @ P is close to P and then treats P as "the orthogonal projection onto the column space of P." What additional check is needed, and what can go wrong numerically if P is oblique? Hint: test P against P.T; an oblique projection can have norm much larger than 1, so it can amplify errors, while an orthogonal one never increases lengths.

Differentiation and Integration as Linear Maps

Why it matters. The sum rule and the constant-multiple rule of calculus say exactly that differentiation is linear. Integration is linear for the same reason. Once you see calculus operators as linear maps, matrices can represent them, kernels explain the "$+C$", and numerical methods for differential equations become linear systems.

Differentiation. Define $D : \mathbb{P}_n \to \mathbb{P}_n$ by $D(p) = p'$. Linearity is the pair of rules $(p + q)' = p' + q'$ and $(cp)' = c,p'$. In the monomial basis $(1, x, x^2, x^3)$ of $\mathbb{P}_3$,

$$D(1) = 0,\quad D(x) = 1,\quad D(x^2) = 2x,\quad D(x^3) = 3x^2 \quad\Longrightarrow\quad [D] = \begin{bmatrix} 0 & 1 & 0 & 0 \ 0 & 0 & 2 & 0 \ 0 & 0 & 0 & 3 \ 0 & 0 & 0 & 0 \end{bmatrix}.$$

For example, $p = 5 - x + 4x^2 + 2x^3$ has coordinates $(5, -1, 4, 2)$, and $[D](5, -1, 4, 2)^T = (-1, 8, 6, 0)^T$, which is $p' = -1 + 8x + 6x^2$.

Three structural facts are visible in this matrix:

• $D$ sends every constant to $0$: its kernel is the constants.
• $D$ is not invertible on $\mathbb{P}_n$: the last row is zero, and nothing maps to $x^n$.
• $D^{n+1} = 0$ on $\mathbb{P}_n$: differentiating $n + 1$ times kills every polynomial of degree at most $n$. An operator with some power equal to zero is called nilpotent.

Integration. Define $J : \mathbb{P}n \to \mathbb{P}{n+1}$ by $J(p)(x) = \int_0^x p(t),dt$. It is linear because the integral is. It sends $x^k \mapsto x^{k+1}/(k+1)$, so from $\mathbb{P}_2$ to $\mathbb{P}_3$

$$[J] = \begin{bmatrix} 0 & 0 & 0 \ 1 & 0 & 0 \ 0 & \tfrac12 & 0 \ 0 & 0 & \tfrac13 \end{bmatrix}.$$

The fundamental theorem of calculus, as linear algebra. $D(J(p)) = p$ for every $p$, so $DJ = I$. But $J(D(p)) = p - p(0)$, so $JD \ne I$: the constant term is lost. $J$ is a right inverse of $D$ but not a left inverse. Section 7.3 explains this asymmetry with kernels and images, and Section 7.5 shows that the "$+C$" in an indefinite integral is an element of a quotient space.

More linear maps on function spaces.

Map	Domain and codomain	Remark
$p \mapsto p(t)$	$\mathbb{P}_n \to \mathbb{R}$	evaluation; a linear functional (Section 7.4)
$f \mapsto \int_a^b f(x),dx$	$C[a, b] \to \mathbb{R}$	definite integral; also a functional
$p(x) \mapsto p(x + 1)$	$\mathbb{P}_n \to \mathbb{P}_n$	shift operator; invertible
$p(x) \mapsto x,p(x)$	$\mathbb{P}n \to \mathbb{P}{n+1}$	multiplication by $x$
$y \mapsto y'' + y$	$C^2(\mathbb{R}) \to C(\mathbb{R})$	its kernel is the solution space $\operatorname{span}{\sin, \cos}$ (Section 6.1)
$X \mapsto \mathbb{E}[X]$	random variables $\to \mathbb{R}$	linearity of expectation

Non-examples: $p \mapsto p^2$, $p \mapsto p' + 1$, and $f \mapsto \int_a^b \lvert f\rvert$.

From calculus to matrices. Sample a function at $N$ equally spaced points with spacing $h$. The central difference $(f_{i+1} - f_{i-1})/(2h)$ approximates $f'(x_i)$, and it is a linear map $\mathbb{R}^N \to \mathbb{R}^N$, so it is a matrix. This is the starting point of finite-difference methods: a differential equation becomes a linear system.

import numpy as np
import sympy as sp

def Dmat(n):
    """D: P_n -> P_{n-1} in monomial bases (constant term first), an n x (n+1) matrix."""
    return np.diag(np.arange(1.0, n + 1), k=1)[:n]

def Jmat(n):
    """J: P_n -> P_{n+1}, p -> integral of p from 0 to x, an (n+2) x (n+1) matrix."""
    return np.diag(1.0 / np.arange(1, n + 2), k=-1)[:, :n + 1]

p = np.array([5.0, -1.0, 4.0, 2.0])                 # 5 - x + 4x^2 + 2x^3
print(Dmat(3) @ p)                                   # [-1.  8.  6.]: p' = -1 + 8x + 6x^2
D3 = np.diag(np.arange(1.0, 4.0), k=1)               # D as an operator on P_3 (4 x 4)
print(np.allclose(np.linalg.matrix_power(D3, 4), 0)) # True: D^4 = 0 on P_3

print(np.allclose(Dmat(4) @ Jmat(3), np.eye(4)))     # True: D J = I
print(Jmat(2) @ Dmat(3) @ p)                         # [ 0. -1.  4.  2.]: J D p = p - p(0)

# The operator L(y) = y'' + y is linear; its kernel is the solution space of y'' + y = 0
x, a, b = sp.symbols('x a b')
f, g = sp.Function('f')(x), sp.Function('g')(x)
L = lambda y: sp.diff(y, x, 2) + y
print(sp.simplify(L(a * f + b * g) - (a * L(f) + b * L(g))))   # 0

# Central differences: a 200 x 200 matrix that approximates d/dx on periodic samples
N = 200
xs = np.linspace(0, 2 * np.pi, N, endpoint=False)
h = xs[1] - xs[0]
Dfd = (np.eye(N, k=1) - np.eye(N, k=-1)) / (2 * h)
Dfd[0, -1], Dfd[-1, 0] = -1 / (2 * h), 1 / (2 * h)  # wrap around at the ends
print(f"{np.max(np.abs(Dfd @ np.sin(xs) - np.cos(xs))):.1e}")   # 1.6e-04, about h^2 / 6

Key takeaways

• Differentiation and integration are linear maps; the sum and constant-multiple rules are additivity and homogeneity.
• On $\mathbb{P}_n$ in the monomial basis, $D$ has $1, 2, \dots, n$ on the superdiagonal; it is nilpotent and its kernel is the constants.
• $DJ = I$ but $JD \ne I$: integration is a right inverse of differentiation, and the lost constant is the "$+C$".
• Evaluation, definite integrals, shifts, differential operators, and expectation are all linear.
• Discretizing a function turns a derivative into a matrix, which is the basis of finite-difference methods.

🧪 Practice

1. Write the matrix of $D : \mathbb{P}_2 \to \mathbb{P}_2$ in the basis $(1, x, x^2)$ and in the basis $(1, 1 + x, (1 + x)^2)$. Explain why the two matrices coincide.
2. Let $V = \operatorname{span}{e^x, xe^x}$. Show that $D$ maps $V$ into $V$, find its matrix in the basis $(e^x, xe^x)$, and invert that matrix to find an antiderivative of $xe^x$.
3. Show that the shift $S(p)(x) = p(x + 1)$ on $\mathbb{P}_2$ is linear, find its matrix in the monomial basis, and find its inverse.
4. Interview: Explain how a numerical solver turns the boundary-value problem $y'' = f$ on $[0, 1]$ into a linear system $A\mathbf{y} = \mathbf{f}$. Why is the discrete second-derivative matrix singular until boundary conditions are imposed? Hint: the second difference $(y_{i+1} - 2y_i + y_{i-1})/h^2$ gives a tridiagonal matrix; constants and linear functions have zero second derivative, so they lie in the kernel until $y(0)$ and $y(1)$ are fixed.

<a id="72-matrix-representations"></a>

7.2 Matrix Representations

This subchapter turns linear maps into matrices and back. It shows why matrix multiplication is defined as it is, and how the matrix of a single map changes when the basis changes.

Standard Matrix of a Transformation

Why it matters. A transformation is often described in words or by a formula, such as "rotate by $30°$, then project onto the plane $z = 0$." Computing with it requires numbers. For linear maps between $F^n$ and $F^m$, the conversion is always possible and completely mechanical.

Theorem. Let $T : \mathbb{R}^n \to \mathbb{R}^m$ be linear. There is exactly one $m \times n$ matrix $A$ with $T(\mathbf{x}) = A\mathbf{x}$ for all $\mathbf{x}$, namely

$$A = \big[,T(\mathbf{e}_1)\ \ T(\mathbf{e}_2)\ \cdots\ T(\mathbf{e}_n),\big].$$

Proof. Write $\mathbf{x} = x_1\mathbf{e}_1 + \cdots + x_n\mathbf{e}_n$. By linearity, $T(\mathbf{x}) = x_1T(\mathbf{e}_1) + \cdots + x_nT(\mathbf{e}_n)$, which is $A\mathbf{x}$ by the column view of the matrix-vector product (Section 3.2). If also $T(\mathbf{x}) = B\mathbf{x}$ for all $\mathbf{x}$, then $A\mathbf{e}_j = B\mathbf{e}_j$ for every $j$, so the columns of $A$ and $B$ agree. $\blacksquare$

$A$ is called the standard matrix of $T$. The same theorem holds over any field: $F^n \to F^m$. Its entries are $a_{ij} = $ the $i$-th component of $T(\mathbf{e}_j)$.

Two languages, one object. "Linear map $\mathbb{R}^n \to \mathbb{R}^m$" and "$m \times n$ matrix" are interchangeable. The rest of the chapter translates freely between them:

Linear map language	Matrix language
$T : \mathbb{R}^n \to \mathbb{R}^m$	$A$ is $m \times n$
$T(\mathbf{e}_j)$	column $j$ of $A$
$T(\mathbf{x})$	$A\mathbf{x}$
$\ker T$ (Section 7.3)	$\operatorname{Nul} A$
$\operatorname{im} T$ (Section 7.3)	$\operatorname{Col} A$
$S \circ T$	$BA$ (next topics)
$T^{-1}$	$A^{-1}$

Recipe. Apply $T$ to each standard basis vector and use the results as columns.

• From a formula. $T(x_1, x_2, x_3) = (x_1 + 2x_2,\ 3x_3 - x_1)$ gives $T(\mathbf{e}_1) = (1, -1)$, $T(\mathbf{e}_2) = (2, 0)$, $T(\mathbf{e}_3) = (0, 3)$, so $A = \begin{bmatrix} 1 & 2 & 0 \ -1 & 0 & 3 \end{bmatrix}$. Shortcut: row $i$ of $A$ lists the coefficients in the $i$-th output formula.
• From geometry. "Rotate the plane by $90°$, then project onto the $x$-axis." $\mathbf{e}_1 \mapsto \mathbf{e}_2 \mapsto (0, 0)$ and $\mathbf{e}_2 \mapsto -\mathbf{e}_1 \mapsto (-1, 0)$, so $A = \begin{bmatrix} 0 & -1 \ 0 & 0 \end{bmatrix}$.
• From a vector operation. For fixed $\mathbf{a} \in \mathbb{R}^3$, $T(\mathbf{x}) = \mathbf{a} \times \mathbf{x}$ is linear, and its standard matrix is the skew-symmetric matrix $[\mathbf{a}]_\times$ of Section 4.2.

When $T$ is known on other vectors. If $\mathbf{u}_1, \dots, \mathbf{u}_n$ is a basis of $\mathbb{R}^n$ and $U = [,\mathbf{u}_1 \cdots \mathbf{u}_n,]$, then $AU = [,T\mathbf{u}_1 \cdots T\mathbf{u}_n,]$, so

$$A = \big[,T\mathbf{u}_1\ \cdots\ T\mathbf{u}_n,\big],U^{-1}.$$

For abstract spaces such as $\mathbb{P}_n$ there is no "$\mathbf{e}_j$" until a basis is chosen. The next topic handles that case.

import numpy as np

def standard_matrix(T, n):
    """The columns are T(e_1), ..., T(e_n)."""
    return np.column_stack([T(e) for e in np.eye(n)])

T = lambda x: np.array([x[0] + 2 * x[1], 3 * x[2] - x[0]])
A = standard_matrix(T, 3)
print(A)
# [[ 1.  2.  0.]
#  [-1.  0.  3.]]
x = np.array([2.0, -1.0, 4.0])
print(A @ x, T(x))                       # [ 0. 10.] [ 0. 10.]

a = np.array([1.0, 2.0, 3.0])
print(standard_matrix(lambda x: np.cross(a, x), 3))   # the cross-product matrix [a]_x
# [[ 0. -3.  2.]
#  [ 3.  0. -1.]
#  [-2.  1.  0.]]

rot90 = lambda v: np.array([-v[1], v[0]])
proj_x = lambda v: np.array([v[0], 0.0])
print(standard_matrix(lambda v: proj_x(rot90(v)), 2) + 0.0)   # rotate, then project (+ 0.0 hides -0.0)
# [[ 0. -1.]
#  [ 0.  0.]]

# Known on a non-standard basis: T(1, 2) = (1, 0) and T(1, 3) = (0, 1)
U = np.array([[1.0, 1.0], [2.0, 3.0]])                # inputs as columns
TU = np.eye(2)                                        # outputs as columns
print(np.round(TU @ np.linalg.inv(U), 12))            # A = [T u_j] U^{-1}
# [[ 3. -1.]
#  [-2.  1.]]

Key takeaways

• Every linear $T : F^n \to F^m$ is $\mathbf{x} \mapsto A\mathbf{x}$ for exactly one $m \times n$ matrix $A$.
• Column $j$ of the standard matrix is $T(\mathbf{e}_j)$; row $i$ holds the coefficients of the $i$-th output.
• If $T$ is known on a basis $U$, then $A = [,T\mathbf{u}_j,],U^{-1}$.
• Linear maps between coordinate spaces and matrices are two descriptions of the same object.

🧪 Practice

1. Find the standard matrix of $T(x, y, z) = (x - z,\ 2y,\ x + y + z,\ 0)$, and state its size.
2. $T : \mathbb{R}^2 \to \mathbb{R}^2$ first reflects across the $y$-axis and then rotates by $90°$ counterclockwise. Find its standard matrix by tracking $\mathbf{e}_1$ and $\mathbf{e}_2$, and identify the result as a single familiar transformation.
3. A linear $T : \mathbb{R}^3 \to \mathbb{R}^3$ satisfies $T(1, 0, 0) = (1, 1, 0)$, $T(1, 1, 0) = (0, 1, 1)$, and $T(1, 1, 1) = (1, 0, 1)$. Find its standard matrix.
4. Interview: You can query a black-box linear map $f : \mathbb{R}^{1000} \to \mathbb{R}^{1000}$, but each call is expensive. How many calls recover its matrix exactly? How could you use fewer calls if you knew the matrix has rank at most 20? Hint: $n$ calls on $\mathbf{e}_1, \dots, \mathbf{e}_n$ suffice in general; for low rank, apply $f$ to a few dozen random vectors and use the fact that the outputs span $\operatorname{im} f$ (randomized SVD, Chapter 11).

Matrix Relative to Arbitrary Bases

Why it matters. Spaces such as $\mathbb{P}_n$ or $\mathbb{R}^{2 \times 2}$ have no built-in coordinates, so a matrix for a map on them only exists after bases are chosen. Even in $\mathbb{R}^n$ the standard basis is often a poor choice: a well-chosen basis can make the matrix of a map diagonal, revealing what the map does. The matrix of $T$ therefore depends on two choices, a basis for the input space and a basis for the output space.

Definition. Let $T : V \to W$ be linear, $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ an ordered basis of $V$, and $\mathcal{C} = (\mathbf{w}_1, \dots, \mathbf{w}_m)$ an ordered basis of $W$. The matrix of $T$ relative to $\mathcal{B}$ and $\mathcal{C}$ is the $m \times n$ matrix

$$[T]_{\mathcal{C} \leftarrow \mathcal{B}} = \big[,[T\mathbf{v}1]{\mathcal{C}}\ \ [T\mathbf{v}2]{\mathcal{C}}\ \cdots\ [T\mathbf{v}n]{\mathcal{C}},\big].$$

When $V = W$ and $\mathcal{B} = \mathcal{C}$, write $[T]_{\mathcal{B}}$.

Theorem. For every $\mathbf{v} \in V$,

$$[T\mathbf{v}]{\mathcal{C}} = [T]{\mathcal{C} \leftarrow \mathcal{B}},[\mathbf{v}]_{\mathcal{B}}.$$

Proof. If $[\mathbf{v}]{\mathcal{B}} = (c_1, \dots, c_n)$, then $T\mathbf{v} = \sum c_jT\mathbf{v}j$. The coordinate map $[,\cdot,]{\mathcal{C}}$ is linear (Section 6.5), so $[T\mathbf{v}]{\mathcal{C}} = \sum c_j[T\mathbf{v}j]{\mathcal{C}}$, which is the stated product. $\blacksquare$

The arrow notation matches $P_{\mathcal{C} \leftarrow \mathcal{B}}$ from Section 6.5. A change-of-coordinates matrix is the matrix of the identity map: $P_{\mathcal{C} \leftarrow \mathcal{B}} = [I]_{\mathcal{C} \leftarrow \mathcal{B}}$.

                        T
            V  ------------------>  W
            |                       |
   [ . ]_B  |                       |  [ . ]_C        (coordinate maps)
            v                       v
           F^n ------------------> F^m
                  [T]_{C<-B}

   Both paths from V to F^m give the same result:  [T v]_C = [T]_{C<-B} [v]_B

Recipe.

1. Apply $T$ to each input basis vector $\mathbf{v}_j$.
2. Find the $\mathcal{C}$-coordinates of each result.
3. Use those coordinate vectors as the columns, in order.

Example 1: evaluation on polynomials. $T : \mathbb{P}_2 \to \mathbb{R}^2$, $T(p) = (p(0), p(1))$, with $\mathcal{B} = (1, x, x^2)$.

• With the standard basis $\mathcal{E}$ of $\mathbb{R}^2$: $T(1) = (1, 1)$, $T(x) = (0, 1)$, $T(x^2) = (0, 1)$, so $[T]_{\mathcal{E} \leftarrow \mathcal{B}} = \begin{bmatrix} 1 & 0 & 0 \ 1 & 1 & 1 \end{bmatrix}$. Check with $p = 2 + 3x - x^2$: the product with $(2, 3, -1)$ is $(2, 4)$, and indeed $p(0) = 2$, $p(1) = 4$.
• With $\mathcal{C} = \big((1, 1), (1, -1)\big)$: the $\mathcal{C}$-coordinates of $(a, b)$ are $\big(\tfrac{a + b}{2}, \tfrac{a - b}{2}\big)$, so $[T]_{\mathcal{C} \leftarrow \mathcal{B}} = \begin{bmatrix} 1 & \tfrac12 & \tfrac12 \ 0 & -\tfrac12 & -\tfrac12 \end{bmatrix}$. The map is the same; only its description changed.

Example 2: transpose on $2 \times 2$ matrices. In the basis $(E_{11}, E_{12}, E_{21}, E_{22})$, transposition swaps $E_{12}$ and $E_{21}$ and fixes the other two:

$$[T] = \begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix}.$$

In the basis $(E_{11},\ E_{22},\ E_{12} + E_{21},\ E_{12} - E_{21})$, made of three symmetric matrices and one skew-symmetric matrix, the matrix is $\operatorname{diag}(1, 1, 1, -1)$. The better basis shows that transposition is a reflection: it fixes the symmetric matrices and negates the skew-symmetric ones.

Formula in coordinate spaces. If $T(\mathbf{x}) = A\mathbf{x}$ and the bases are the columns of invertible matrices $B$ (input) and $C$ (output), then $\mathbf{x} = B[\mathbf{x}]{\mathcal{B}}$ and $[\mathbf{y}]{\mathcal{C}} = C^{-1}\mathbf{y}$, so

$$[T]_{\mathcal{C} \leftarrow \mathcal{B}} = C^{-1}AB.$$

import numpy as np

def matrix_rel(A, Bm, Cm):
    """[T]_{C<-B} for T(x) = A x; the bases are the columns of Bm (input) and Cm (output)."""
    return np.linalg.solve(Cm, A @ Bm)            # C^{-1} A B without forming the inverse

A = np.array([[1.0, 2.0, 0.0], [-1.0, 0.0, 3.0]])  # T: R^3 -> R^2 from the previous topic
Bm = np.array([[1.0, 0.0, 1.0], [1.0, 1.0, 0.0], [0.0, 1.0, 1.0]])
Cm = np.array([[1.0, 1.0], [1.0, -1.0]])
M = matrix_rel(A, Bm, Cm)
print(M)
# [[ 1.   2.5  1.5]
#  [ 2.  -0.5 -0.5]]

v = np.array([2.0, -1.0, 4.0])
v_B = np.linalg.solve(Bm, v)                      # [v]_B
Tv_C = np.linalg.solve(Cm, A @ v)                 # [T v]_C
print(np.allclose(M @ v_B, Tv_C))                 # True: the square above commutes

# Transpose on 2x2 matrices; coordinates in (E11, E12, E21, E22) are the row-major entries
E = [e.reshape(2, 2) for e in np.eye(4)]
Tt = np.column_stack([e.T.reshape(4) for e in E])
print(Tt.astype(int))
# [[1 0 0 0]
#  [0 0 1 0]
#  [0 1 0 0]
#  [0 0 0 1]]
S = np.column_stack([E[0].reshape(4), E[3].reshape(4),
                     (E[1] + E[2]).reshape(4), (E[1] - E[2]).reshape(4)])
print(np.diag(np.linalg.solve(S, Tt @ S)))        # [ 1.  1.  1. -1.]: diagonal in the adapted basis

Key takeaways

• $[T]{\mathcal{C} \leftarrow \mathcal{B}}$ has the $\mathcal{C}$-coordinates of $T\mathbf{v}j$ as its $j$-th column, and $[T\mathbf{v}]{\mathcal{C}} = [T]{\mathcal{C} \leftarrow \mathcal{B}}[\mathbf{v}]_{\mathcal{B}}$.
• The same map has different matrices in different bases; the matrix is a description, not the map itself.
• In coordinate spaces, $[T]_{\mathcal{C} \leftarrow \mathcal{B}} = C^{-1}AB$.
• A basis adapted to the map can make its matrix diagonal and expose its geometry.
• Change-of-coordinates matrices are matrices of the identity map: $P_{\mathcal{C} \leftarrow \mathcal{B}} = [I]_{\mathcal{C} \leftarrow \mathcal{B}}$.

🧪 Practice

1. For $D : \mathbb{P}_2 \to \mathbb{P}1$, $D(p) = p'$, find $[D]{\mathcal{C} \leftarrow \mathcal{B}}$ with $\mathcal{B} = (1, x, x^2)$ and $\mathcal{C} = (1, x)$, and then with $\mathcal{C}' = (1, 1 + x)$.
2. For $T(x, y) = (x + y, 2y)$ on $\mathbb{R}^2$, find $[T]_{\mathcal{B}}$ with $\mathcal{B} = \big((1, 0), (1, 1)\big)$. What is special about the result, and what does it say about the vectors in $\mathcal{B}$?
3. For $T : \mathbb{P}_1 \to \mathbb{P}_2$, $T(p) = x,p(x)$, find the matrix relative to the monomial bases, and then relative to $\mathcal{B} = (1 + x, 1 - x)$ and the monomial basis of $\mathbb{P}_2$.
4. Interview: People sometimes say "a matrix is not a linear map." Give an example of two different matrices that represent the same map, and an example of one matrix that represents two different maps. Hint: use the reflection across $y = x$ in the standard basis and in the basis $\big((1, 1), (1, -1)\big)$; then interpret $\begin{bmatrix} 0 & 1 \ 1 & 0 \end{bmatrix}$ in two different bases.

Composition and Matrix Multiplication

Why it matters. Section 4.1 defined the product of matrices by the row-times-column rule, which can look arbitrary. It is chosen for one reason: multiplying matrices is composing linear maps. Composition is everywhere: transformation chains in graphics and robotics, stacked layers in a neural network, and repeated time steps in a simulation.

Composition is linear. If $T : U \to V$ and $S : V \to W$ are linear, so is $S \circ T$:

$$S(T(c\mathbf{u} + \mathbf{v})) = S(c,T\mathbf{u} + T\mathbf{v}) = c,S(T\mathbf{u}) + S(T\mathbf{v}).$$

Theorem. With bases $\mathcal{B}$ of $U$, $\mathcal{C}$ of $V$, and $\mathcal{D}$ of $W$,

$$[S \circ T]{\mathcal{D} \leftarrow \mathcal{B}} = [S]{\mathcal{D} \leftarrow \mathcal{C}},[T]_{\mathcal{C} \leftarrow \mathcal{B}}.$$

Proof. For every $\mathbf{u}$, $[S(T\mathbf{u})]{\mathcal{D}} = [S]{\mathcal{D} \leftarrow \mathcal{C}}[T\mathbf{u}]{\mathcal{C}} = [S]{\mathcal{D} \leftarrow \mathcal{C}}[T]{\mathcal{C} \leftarrow \mathcal{B}}[\mathbf{u}]{\mathcal{B}}$. Taking $\mathbf{u} = \mathbf{v}_j$, whose coordinate vector is $\mathbf{e}_j$, shows that the two matrices have the same $j$-th column. $\blacksquare$

With standard bases this reads: column $j$ of $BA$ is $B(A\mathbf{e}_j)$, which is the column definition of the matrix product.

              T                   S
     U  -----------> V  -----------> W
   (dim n)   A (m x n)  (dim m)  B (p x m)  (dim p)

                      S o T
     U  -------------------------------> W
                  B A   (p x n)

   the inner sizes match because they are both dim V;
   the matrix written on the right acts first

Consequences.

Fact about maps	Fact about matrices
$S \circ T$ means "first $T$, then $S$"	in $BA\mathbf{x}$, $A$ acts first
the middle space must match	$(p \times m)(m \times n)$ needs equal inner sizes
$(R \circ S) \circ T = R \circ (S \circ T)$ for all functions	$(CB)A = C(BA)$ with no index computation
$S \circ T \ne T \circ S$ in general	$BA \ne AB$ in general
$(S \circ T)^{-1} = T^{-1} \circ S^{-1}$	$(BA)^{-1} = A^{-1}B^{-1}$
$T^k = T \circ \cdots \circ T$	$A^k$

The inverse rule is the socks-and-shoes rule: you put on socks, then shoes, and you take them off in the reverse order.

Order matters, geometrically. Let $R$ rotate by $90°$ and $H$ reflect across the $x$-axis:

$$HR = \begin{bmatrix} 1 & 0 \ 0 & -1 \end{bmatrix}\begin{bmatrix} 0 & -1 \ 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & -1 \ -1 & 0 \end{bmatrix}, \qquad RH = \begin{bmatrix} 0 & 1 \ 1 & 0 \end{bmatrix}.$$

"Rotate, then reflect" is the reflection across $y = -x$; "reflect, then rotate" is the reflection across $y = x$.

Angle-addition formulas for free. Rotating by $\beta$ and then by $\alpha$ is rotating by $\alpha + \beta$, so $R_\alpha R_\beta = R_{\alpha + \beta}$. Comparing first columns gives

$$\cos(\alpha + \beta) = \cos\alpha\cos\beta - \sin\alpha\sin\beta, \qquad \sin(\alpha + \beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta.$$

Stacked linear layers collapse. Two linear layers with no nonlinearity between them, $\mathbf{x} \mapsto W_2(W_1\mathbf{x})$, are a single linear layer $W_2W_1$. Its rank is at most the smallest width in the chain, which is why neural networks insert nonlinear activations between layers.

import numpy as np
import sympy as sp

R = np.array([[0, -1], [1, 0]])                    # rotate by 90 degrees
H = np.array([[1, 0], [0, -1]])                    # reflect across the x-axis
x = np.array([2, 1])
print(H @ (R @ x), (H @ R) @ x)                    # [-1 -2] [-1 -2]: rotate first, then reflect
print(R @ (H @ x))                                 # [1 2]: the other order gives another point
print((H @ R).tolist(), (R @ H).tolist())          # [[0, -1], [-1, 0]] [[0, 1], [1, 0]]

a, b = sp.symbols('alpha beta')
def Rs(t):
    return sp.Matrix([[sp.cos(t), -sp.sin(t)], [sp.sin(t), sp.cos(t)]])
print(sp.expand((Rs(a) * Rs(b))[0, 0]), "|", sp.expand((Rs(a) * Rs(b))[1, 0]))
# -sin(alpha)*sin(beta) + cos(alpha)*cos(beta) | sin(alpha)*cos(beta) + sin(beta)*cos(alpha)
print(sp.simplify(Rs(a) * Rs(b) - Rs(a + b)))      # Matrix([[0, 0], [0, 0]])

# Two linear layers without an activation are one linear layer
rng = np.random.default_rng(0)
W1 = rng.normal(size=(2, 5))                       # R^5 -> R^2 (a bottleneck)
W2 = rng.normal(size=(5, 2))                       # R^2 -> R^5
x5 = rng.normal(size=5)
print(np.allclose(W2 @ (W1 @ x5), (W2 @ W1) @ x5), np.linalg.matrix_rank(W2 @ W1))   # True 2

Key takeaways

• The composition of linear maps is linear, and its matrix is the product of the matrices: $[S \circ T] = [S][T]$.
• Matrix multiplication is defined this way precisely so that it represents composition; associativity follows for free.
• Read products right to left: in $BA\mathbf{x}$, $A$ acts first.
• Composition is not commutative, and inverses reverse the order: $(BA)^{-1} = A^{-1}B^{-1}$.
• A chain of linear maps is one linear map whose rank is at most the smallest dimension it passes through.

🧪 Practice

1. Let $T(x, y) = (x + y, x - y)$ and $S(x, y) = (2x, x + 3y)$. Find the standard matrices of $S \circ T$ and $T \circ S$, and confirm that they differ.
2. Prove that $(S \circ T)^{-1} = T^{-1} \circ S^{-1}$ for invertible linear maps, and deduce $(AB)^{-1} = B^{-1}A^{-1}$.
3. Use $R_\theta^3 = R_{3\theta}$ to express $\cos 3\theta$ in terms of $\cos\theta$.
4. Interview: In a graphics pipeline, a vertex goes through a model matrix $M$, a view matrix $V$, and a projection matrix $P$. With column vectors, in what order are they multiplied, what changes under the row-vector convention, and why do engines precompute one combined matrix? Hint: $\mathbf{v}_{\text{clip}} = PVM\mathbf{v}$; with row vectors it becomes $\mathbf{v}^TM^TV^TP^T$; associativity lets one $4 \times 4$ product replace three matrix-vector products per vertex.

Similarity and Change of Basis for Operators

Why it matters. For an operator $T : V \to V$, it is natural to use the same basis on both sides and write $[T]_{\mathcal{B}}$. Different bases give different matrices for the same operator. Similarity is the exact relation "same operator, different basis", and finding a basis in which the matrix is as simple as possible, ideally diagonal, is the central problem of Chapter 8.

Theorem. Let $T : V \to V$ be linear, let $\mathcal{B}$ and $\mathcal{C}$ be bases of $V$, and let $P = P_{\mathcal{B} \leftarrow \mathcal{C}}$. Then

$$[T]{\mathcal{C}} = P^{-1},[T]{\mathcal{B}},P.$$

Proof. Write $T = I \circ T \circ I$ and apply the composition rule: $[T]{\mathcal{C}} = [I]{\mathcal{C} \leftarrow \mathcal{B}},[T]{\mathcal{B}},[I]{\mathcal{B} \leftarrow \mathcal{C}} = P_{\mathcal{C} \leftarrow \mathcal{B}},[T]{\mathcal{B}},P{\mathcal{B} \leftarrow \mathcal{C}}$, and $P_{\mathcal{C} \leftarrow \mathcal{B}} = P_{\mathcal{B} \leftarrow \mathcal{C}}^{-1}$ (Section 6.5). $\blacksquare$

Read $P^{-1}[T]_{\mathcal{B}}P$ from right to left: convert $\mathcal{C}$-coordinates to $\mathcal{B}$-coordinates, apply $T$ there, and convert back.

                       [T]_B
       B-coordinates  -------->  B-coordinates
            ^                         |
          P |                         | P^{-1}
            |                         v
       C-coordinates  -------->  C-coordinates
                       [T]_C  =  P^{-1} [T]_B P

In $\mathbb{R}^n$ with $\mathcal{B}$ the standard basis, $P$ is the matrix whose columns are the vectors of $\mathcal{C}$, and $[T]_{\mathcal{C}} = P^{-1}AP$, as previewed in Section 6.5.

Definition. Square matrices $A$ and $B$ are similar, written $A \sim B$, if $B = P^{-1}AP$ for some invertible $P$. Similarity is an equivalence relation: $A = I^{-1}AI$; if $B = P^{-1}AP$ then $A = (P^{-1})^{-1}BP^{-1}$; and $P^{-1}AP = B$, $Q^{-1}BQ = C$ give $(PQ)^{-1}A(PQ) = C$.

Example: a reflection in disguise. The reflection across $y = 2x$ has standard matrix (Section 7.1, with $\mathbf{u} = (1, 2)/\sqrt5$)

$$H = \frac15\begin{bmatrix} -3 & 4 \ 4 & 3 \end{bmatrix}.$$

Choose $\mathcal{C} = \big((1, 2), (-2, 1)\big)$: the first vector lies on the mirror and the second is perpendicular to it. Then $H(1, 2) = (1, 2)$ and $H(-2, 1) = (2, -1)$, so with $P = \begin{bmatrix} 1 & -2 \ 2 & 1 \end{bmatrix}$,

$$P^{-1}HP = \begin{bmatrix} 1 & 0 \ 0 & -1 \end{bmatrix}.$$

The entries of $H$ hide what the map does; the adapted basis reveals it immediately. Likewise, every projection onto a line in the plane is similar to $\operatorname{diag}(1, 0)$.

Similarity invariants. Similar matrices describe the same operator, so they share every property of the operator itself.

Shared by similar matrices	Reason
determinant	$\det(P^{-1}AP) = \det P^{-1}\det A\det P = \det A$
trace	$\operatorname{tr}(XY) = \operatorname{tr}(YX)$, so $\operatorname{tr}(P^{-1}(AP)) = \operatorname{tr}(AP,P^{-1})$
rank	rank of the operator, independent of basis
characteristic polynomial and eigenvalues	Chapter 8
invertibility; $A^k \sim B^k$	$P^{-1}A^kP = (P^{-1}AP)^k$

Not shared in general	Example
individual entries	$H$ and $\operatorname{diag}(1, -1)$ above
symmetry	a symmetric matrix can be similar to a non-symmetric one
eigenvectors and column space as sets of vectors	they are transformed by $P^{-1}$

Invariants are necessary, not sufficient. $I$ and $\begin{bmatrix} 1 & 1 \ 0 & 1 \end{bmatrix}$ share trace, determinant, rank, and characteristic polynomial $(\lambda - 1)^2$. They are not similar: $P^{-1}IP = I$ for every $P$, so $I$ is similar only to itself. The shear is a genuinely different operator. Deciding similarity in general needs the Jordan form (Chapter 8).

Similarity versus equivalence. For a map $T : V \to W$ between different spaces, the input and output bases can be changed independently, giving $Q^{-1}AP$. Under this coarser relation, called matrix equivalence, the only invariant is the rank: every rank-$r$ matrix is equivalent to $\begin{bmatrix} I_r & 0 \ 0 & 0 \end{bmatrix}$. Similarity is finer because the same basis must be used on both sides. The SVD (Chapter 11) is the version of equivalence that uses orthonormal bases.

import numpy as np

H = np.array([[-3.0, 4.0], [4.0, 3.0]]) / 5        # reflection across y = 2x
P = np.array([[1.0, -2.0], [2.0, 1.0]])            # columns: along the mirror, perpendicular to it
print(np.round(np.linalg.solve(P, H @ P), 12) + 0.0)   # + 0.0 turns -0.0 into 0.0 for display
# [[ 1.  0.]
#  [ 0. -1.]]

rng = np.random.default_rng(1)
A = rng.integers(-3, 4, size=(3, 3)).astype(float)
Pr = rng.normal(size=(3, 3))                       # invertible with probability 1
B = np.linalg.solve(Pr, A @ Pr)                    # B = P^{-1} A P
print(np.allclose(A, B))                           # False: different entries
print(np.isclose(np.linalg.det(A), np.linalg.det(B)), np.isclose(np.trace(A), np.trace(B)),
      np.linalg.matrix_rank(A) == np.linalg.matrix_rank(B))      # True True True
print(np.allclose(np.poly(A), np.poly(B)))         # True: same characteristic polynomial

# Same invariants, not similar: the identity is similar only to itself
shear = np.array([[1.0, 1.0], [0.0, 1.0]])
print(np.trace(shear), np.linalg.det(shear), np.poly(shear))     # 2.0 1.0 [ 1. -2.  1.]
Q = rng.normal(size=(2, 2))
print(np.allclose(np.linalg.solve(Q, np.eye(2) @ Q), np.eye(2)))  # True for every invertible Q

Key takeaways

• For an operator, changing basis by $P = P_{\mathcal{B} \leftarrow \mathcal{C}}$ gives $[T]{\mathcal{C}} = P^{-1}[T]{\mathcal{B}}P$.
• $A \sim B$ means $B = P^{-1}AP$: the same operator described in two bases.
• Similar matrices share determinant, trace, rank, characteristic polynomial, and eigenvalues, but not entries or eigenvectors.
• Equal invariants do not imply similarity: $I$ and the shear $\begin{bmatrix} 1 & 1 \ 0 & 1 \end{bmatrix}$ are not similar.
• A basis adapted to the operator can make its matrix diagonal; finding such bases is the subject of Chapter 8.

🧪 Practice

1. For $A = \begin{bmatrix} 1 & 2 \ 0 & 3 \end{bmatrix}$, compute its matrix in the basis $\mathcal{C} = \big((1, 0), (1, 1)\big)$. What do you notice?
2. Use trace and determinant to show that $\begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}$ and $\begin{bmatrix} 1 & 0 \ 0 & 4 \end{bmatrix}$ are not similar, even though their traces are equal.
3. Prove that if $A \sim B$, then $A^k \sim B^k$ for every $k \ge 1$, and $A^{-1} \sim B^{-1}$ when $A$ is invertible.
4. Interview: Two square matrices have the same eigenvalues with the same multiplicities. Are they necessarily similar? How would you decide in practice, and why is the question numerically delicate? Hint: compare $I$ with a shear; if both are diagonalizable the answer is yes; in general compare the ranks of $(A - \lambda I)^k$ (Jordan structure, Chapter 8), and note that tiny perturbations can change those ranks.

<a id="73-kernel-image-and-structure"></a>

7.3 Kernel, Image, and Structure

This subchapter attaches two subspaces to every linear map: the kernel, which measures what the map destroys, and the image, which measures what it can reach. Rank-nullity links their dimensions, and together they answer every existence and uniqueness question about $T(\mathbf{x}) = \mathbf{w}$.

Kernel of a Linear Map

Why it matters. The kernel is everything a map cannot see. It measures the failure of uniqueness: $T\mathbf{u} = T\mathbf{v}$ exactly when $\mathbf{u} - \mathbf{v}$ lies in the kernel. The null space of a matrix (Sections 3.4 and 6.6) is one example. The constants that differentiation destroys, which produce the "$+C$", are another, and so is the solution space of a homogeneous differential equation.

Analogy. Think of the shadow of an object on the floor under an overhead light. Moving a point straight up or down does not move its shadow. The vertical direction is the kernel of the "shadow" map: changes in that direction are invisible in the output.

Definition. The kernel (or null space) of a linear map $T : V \to W$ is

$$\ker T = {\mathbf{v} \in V : T\mathbf{v} = \mathbf{0}_W}.$$

Theorem. $\ker T$ is a subspace of $V$.

Proof. $T(\mathbf{0}) = \mathbf{0}$, so $\mathbf{0} \in \ker T$. If $T\mathbf{u} = T\mathbf{v} = \mathbf{0}$, then $T(c\mathbf{u} + \mathbf{v}) = c\mathbf{0} + \mathbf{0} = \mathbf{0}$. $\blacksquare$

This one fact explains the pattern noticed in Section 6.2: null spaces, solution sets of homogeneous equations, traceless matrices, and polynomials vanishing at a point are all subspaces, because each is the kernel of a linear map.

Solution sets are translates of the kernel. If $T\mathbf{x}_p = \mathbf{w}$, then

$${\mathbf{x} \in V : T\mathbf{x} = \mathbf{w}} = \mathbf{x}_p + \ker T.$$

Proof. If $T\mathbf{x} = \mathbf{w}$, then $T(\mathbf{x} - \mathbf{x}_p) = \mathbf{0}$, so $\mathbf{x} \in \mathbf{x}_p + \ker T$. Conversely, $T(\mathbf{x}_p + \mathbf{k}) = \mathbf{w} + \mathbf{0}$. $\blacksquare$

Section 3.4 proved this for $A\mathbf{x} = \mathbf{b}$. It holds for every linear map: the general solution of $y'' + y = 1$ is $1 + c_1\sin x + c_2\cos x$, a particular solution plus the kernel of $y \mapsto y'' + y$.

        V                                         W
   +-------------------------+               +-----------------+
   |    x_p + ker T  ........|---- T ------> |  w              |
   |   (a parallel copy)     |               |                 |
   |                         |               |                 |
   |    ker T  ..............|---- T ------> |  0              |
   |   (through the origin)  |               |                 |
   +-------------------------+               +-----------------+
   everything on the dotted line ker T maps to 0;
   everything on its translate maps to the single vector w

Examples.

Map $T$	$\ker T$	$\dim\ker T$
$\mathbf{x} \mapsto A\mathbf{x}$, $A$ of size $m \times n$	$\operatorname{Nul} A$	$n - \operatorname{rank}A$
$D : \mathbb{P}_n \to \mathbb{P}_n$	constant polynomials	$1$
$\mathbb{P}_2 \to \mathbb{R}$, $p \mapsto p(1)$	$\operatorname{span}{x - 1,\ x^2 - 1}$	$2$
$\operatorname{tr} : \mathbb{R}^{n \times n} \to \mathbb{R}$	traceless matrices	$n^2 - 1$
$A \mapsto A - A^T$ on $\mathbb{R}^{n \times n}$	symmetric matrices	$n(n + 1)/2$
$y \mapsto y'' + y$	$\operatorname{span}{\sin x, \cos x}$	$2$
orthogonal projection of $\mathbb{R}^3$ onto a plane	the normal line	$1$
a rotation	${\mathbf{0}}$	$0$

Computing a kernel on an abstract space. Choose bases, compute $M = [T]_{\mathcal{C} \leftarrow \mathcal{B}}$, find $\operatorname{Nul} M$ by row reduction, and turn each null vector $(c_1, \dots, c_n)$ back into the vector $\sum c_j\mathbf{v}j$. This works because $T\mathbf{v} = \mathbf{0}$ exactly when $M[\mathbf{v}]{\mathcal{B}} = \mathbf{0}$.

Worked example. $T : \mathbb{P}_3 \to \mathbb{R}^2$, $T(p) = (p(1), p'(1))$. In the basis $(1, x, x^2, x^3)$: $T(1) = (1, 0)$, $T(x) = (1, 1)$, $T(x^2) = (1, 2)$, $T(x^3) = (1, 3)$, so

$$M = \begin{bmatrix} 1 & 1 & 1 & 1 \ 0 & 1 & 2 & 3 \end{bmatrix} ;\longrightarrow; \begin{bmatrix} 1 & 0 & -1 & -2 \ 0 & 1 & 2 & 3 \end{bmatrix}.$$

The free variables $c_3, c_4$ give null vectors $(1, -2, 1, 0)$ and $(2, -3, 0, 1)$, which are the polynomials $(x - 1)^2$ and $x^3 - 3x + 2 = (x - 1)^2(x + 2)$. So $\ker T$ is the set of cubics with a double root at $1$: ${(x - 1)^2(a + bx)}$.

import sympy as sp

x = sp.symbols('x')
basis = [sp.Integer(1), x, x**2, x**3]

def T(p):
    return [p.subs(x, 1), sp.diff(p, x).subs(x, 1)]     # (p(1), p'(1))

M = sp.Matrix([T(b) for b in basis]).T                   # columns are T(1), T(x), T(x^2), T(x^3)
print(M)                                                  # Matrix([[1, 1, 1, 1], [0, 1, 2, 3]])
for c in M.nullspace():
    p = sum(ci * bi for ci, bi in zip(c, basis))          # from coordinates back to a polynomial
    print(sp.expand(p), "=", sp.factor(p))
# x**2 - 2*x + 1 = (x - 1)**2
# x**3 - 3*x + 2 = (x - 1)**2*(x + 2)

# Kernel of y -> y'' + y, and a solution set = particular solution + kernel
y = sp.Function('y')
print(sp.dsolve(y(x).diff(x, 2) + y(x), y(x)))           # Eq(y(x), C1*sin(x) + C2*cos(x))
print(sp.dsolve(y(x).diff(x, 2) + y(x) - 1, y(x)))       # Eq(y(x), C1*sin(x) + C2*cos(x) + 1)

Key takeaways

• $\ker T = {\mathbf{v} : T\mathbf{v} = \mathbf{0}}$ is always a subspace of the domain.
• $T\mathbf{u} = T\mathbf{v}$ exactly when $\mathbf{u} - \mathbf{v} \in \ker T$, so the kernel measures non-uniqueness.
• Every solution set of $T\mathbf{x} = \mathbf{w}$ is empty or a translate $\mathbf{x}_p + \ker T$.
• To compute a kernel on an abstract space, find the null space of the matrix of $T$ and convert the coordinates back.

🧪 Practice

1. Find a basis of $\ker T$ for $T(x, y, z) = (x + y - z,\ 2x - y + z)$, and describe it geometrically.
2. Find the kernel of $T : \mathbb{R}^{2 \times 2} \to \mathbb{R}^{2 \times 2}$, $T(A) = A + A^T$, and its dimension.
3. Using the worked example, find all $p \in \mathbb{P}_3$ with $p(1) = 2$ and $p'(1) = 0$, written as a particular solution plus the kernel.
4. Interview: A linear regression includes two features that are exactly proportional, such as height in centimetres and height in inches. Describe the kernel of the design matrix and explain what happens to the fitted coefficients. Hint: the kernel contains the vector with $1$ in the centimetre slot, $-2.54$ in the inch slot, and $0$ elsewhere (the inch value is $1/2.54$ of the centimetre value); adding any multiple of it leaves every prediction unchanged, so the coefficients are not unique until regularization or feature removal picks one.

Image and Range

Why it matters. The image is the set of outputs a map can actually produce. It answers the existence question: $T\mathbf{x} = \mathbf{w}$ has a solution exactly when $\mathbf{w}$ lies in the image. The column space of a matrix is one example. Another is the set of possible outputs of a linear layer in a neural network, which is always a subspace of limited dimension, however large the output space is.

Definition. The image (or range) of a linear map $T : V \to W$ is

$$\operatorname{im} T = {T\mathbf{v} : \mathbf{v} \in V} \subseteq W.$$

Its dimension is the rank of $T$, $\operatorname{rank} T = \dim\operatorname{im} T$.

Theorem. $\operatorname{im} T$ is a subspace of $W$.

Proof. $\mathbf{0} = T\mathbf{0}$ is in the image, and $T\mathbf{u} + c,T\mathbf{v} = T(\mathbf{u} + c\mathbf{v})$. $\blacksquare$

Theorem. If $\mathbf{v}_1, \dots, \mathbf{v}_n$ span $V$, then $\operatorname{im} T = \operatorname{span}{T\mathbf{v}_1, \dots, T\mathbf{v}_n}$.

Proof. Each $\mathbf{v}$ equals $\sum c_j\mathbf{v}_j$, so $T\mathbf{v} = \sum c_jT\mathbf{v}_j$; conversely every such combination is $T\big(\sum c_j\mathbf{v}_j\big)$. $\blacksquare$

So the images of a basis span the image, but they may be dependent. Removing the redundant ones leaves a basis. For a matrix, the images of $\mathbf{e}_j$ are the columns, and the pivot columns form a basis of $\operatorname{Col} A$ (Section 6.6).

Codomain versus image. The codomain $W$ is declared in advance; the image is what is actually reached (Section 1.1). For $T : \mathbb{R}^2 \to \mathbb{R}^3$, $T(x, y) = (x, y, 0)$, the codomain is $\mathbb{R}^3$ but the image is only the $xy$-plane. $T$ is surjective exactly when $\operatorname{im} T = W$.

Examples.

Map $T$	$\operatorname{im} T$	$\operatorname{rank} T$
$D : \mathbb{P}_3 \to \mathbb{P}_3$	$\mathbb{P}_2$	$3$
$J : \mathbb{P}_2 \to \mathbb{P}_3$, $p \mapsto \int_0^x p$	${q \in \mathbb{P}_3 : q(0) = 0}$	$3$
$\mathbb{P}_2 \to \mathbb{R}^2$, $p \mapsto (p(0), p(1))$	all of $\mathbb{R}^2$	$2$
$\operatorname{tr} : \mathbb{R}^{n \times n} \to \mathbb{R}$	$\mathbb{R}$	$1$
$A \mapsto A - A^T$	skew-symmetric matrices	$n(n - 1)/2$
orthogonal projection onto a plane	that plane	$2$
$\mathbf{x} \mapsto (\mathbf{a} \cdot \mathbf{x}),\mathbf{b}$ with $\mathbf{a}, \mathbf{b} \ne \mathbf{0}$	$\operatorname{span}{\mathbf{b}}$	$1$

The last row is the general rank-one map: its matrix is the outer product $\mathbf{b}\mathbf{a}^T$, and every rank-one matrix has this form.

Computing an image on an abstract space. Compute $M = [T]{\mathcal{C} \leftarrow \mathcal{B}}$, take its pivot columns as a basis of $\operatorname{Col} M$, and convert each column back to a vector of $W$ using $\mathcal{C}$. For $T(A) = A - A^T$ on $\mathbb{R}^{2 \times 2}$, the only nonzero images of basis matrices are $\pm(E{12} - E_{21})$, so the image is spanned by $\begin{bmatrix} 0 & 1 \ -1 & 0 \end{bmatrix}$.

import numpy as np
import sympy as sp

# T(A) = A - A^T on 2x2 matrices, in the basis (E11, E12, E21, E22)
E = [sp.Matrix(2, 2, lambda i, j, k=k: 1 if 2 * i + j == k else 0) for k in range(4)]
T = lambda A: A - A.T
M = sp.Matrix.hstack(*[T(e).reshape(4, 1) for e in E])
print(M.rank())                                    # 1
for c in M.columnspace():
    print(c.reshape(2, 2))                         # Matrix([[0, 1], [-1, 0]])

# A linear layer R^3 -> R^5 can only output vectors in a 3-dimensional subspace
rng = np.random.default_rng(0)
W = rng.normal(size=(5, 3))
X = rng.normal(size=(3, 1000))                     # 1000 inputs
print(np.linalg.matrix_rank(W @ X))                # 3: all 1000 outputs lie in im W
b = rng.normal(size=5)                             # a random target in R^5
print(np.linalg.matrix_rank(np.column_stack([W, b])))   # 4: b is not in im W, so W x = b has no solution

Key takeaways

• $\operatorname{im} T = {T\mathbf{v}}$ is a subspace of the codomain; its dimension is $\operatorname{rank} T$.
• $T\mathbf{x} = \mathbf{w}$ is solvable exactly when $\mathbf{w} \in \operatorname{im} T$.
• The images of a spanning set span the image; prune dependent ones to get a basis.
• The image can be much smaller than the codomain; $T$ is surjective exactly when they are equal.
• Every rank-one map is $\mathbf{x} \mapsto (\mathbf{a} \cdot \mathbf{x}),\mathbf{b}$, with matrix $\mathbf{b}\mathbf{a}^T$.

🧪 Practice

1. Find a basis of $\operatorname{im} T$ for $T(x, y, z) = (x + 2y + z,\ 2x + 4y + 2z,\ x - z)$.
2. Show that $\operatorname{im} D = \mathbb{P}_{n-1}$ for $D : \mathbb{P}_n \to \mathbb{P}_n$, and find the image of $p \mapsto x,p(x)$ from $\mathbb{P}n$ to $\mathbb{P}{n+1}$.
3. For $T : \mathbb{P}_1 \to \mathbb{R}^3$, $T(p) = (p(0), p(1), p(2))$, find $\operatorname{im} T$ and a single linear equation that describes it.
4. Interview: A linear layer maps $\mathbb{R}^{512} \to \mathbb{R}^{1024}$, and a colleague says it "expands the representation to 1024 dimensions." What is the largest possible dimension of the set of outputs, and how does a ReLU after the layer change the picture? Hint: the outputs form $\operatorname{im} W$, of dimension at most 512; a ReLU is not linear, so its outputs are no longer confined to one subspace, but each of them still comes from a piece of a 512-dimensional set.

Rank-Nullity for Linear Maps

Why it matters. Section 6.6 proved $\operatorname{rank}A + \dim\operatorname{Nul}A = n$ for matrices. The coordinate-free version is a conservation law: every dimension of the input is either destroyed (it lies in the kernel) or survives (it contributes to the image). It lets you find one dimension from the other without computing, and settle existence and uniqueness questions by counting alone.

Theorem (rank-nullity). Let $V$ be finite-dimensional and $T : V \to W$ linear. Then

$$\dim V = \dim\ker T + \dim\operatorname{im} T.$$

Proof. Let $\mathbf{u}_1, \dots, \mathbf{u}_k$ be a basis of $\ker T$, and extend it to a basis $\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{v}_1, \dots, \mathbf{v}_r$ of $V$ (Section 6.4). We show that $T\mathbf{v}_1, \dots, T\mathbf{v}_r$ is a basis of $\operatorname{im} T$.

• Spanning. Every $\mathbf{v} = \sum a_i\mathbf{u}_i + \sum b_j\mathbf{v}_j$ has $T\mathbf{v} = \sum b_jT\mathbf{v}_j$, because $T\mathbf{u}_i = \mathbf{0}$.
• Independence. If $\sum b_jT\mathbf{v}_j = \mathbf{0}$, then $\sum b_j\mathbf{v}_j \in \ker T$, so $\sum b_j\mathbf{v}_j = \sum a_i\mathbf{u}_i$ for some $a_i$. Independence of the full basis forces every $b_j = 0$.

Hence $\dim\operatorname{im} T = r$ and $\dim V = k + r$. $\blacksquare$

Only $V$ needs to be finite-dimensional; $W$ may be infinite-dimensional.

            V   (dim n)                                     W
   +---------------------------+                   +----------------------+
   |  ker T          (dim k)   | ----- T ----->    0                      |
   |- - - - - - - - - - - - - -|                   |                      |
   |  a complement   (dim r)   | ----- T ----->    im T   (dim r)         |
   |  of ker T                 |   one-to-one      |                      |
   +---------------------------+                   +----------------------+
                       n  =  k  +  r

Counting consequences.

Situation	Conclusion
$\dim V > \dim W$	$T$ is not injective: $\dim\ker T \ge \dim V - \dim W > 0$
$\dim V < \dim W$	$T$ is not surjective: $\operatorname{rank} T \le \dim V < \dim W$
$\dim V = \dim W$	$T$ injective $\iff$ $T$ surjective $\iff$ $T$ bijective
always	$\operatorname{rank} T \le \min(\dim V, \dim W)$

Applications.

1. Symmetric and skew-symmetric matrices. Let $T(A) = A - A^T$ on $\mathbb{R}^{n \times n}$. Its kernel is the symmetric matrices. Its image is the skew-symmetric matrices: every output is skew, and every skew $K$ equals $T(K/2)$. Skew matrices are determined by their $n(n - 1)/2$ entries above the diagonal, so $\dim\mathrm{Sym}_n = n^2 - n(n - 1)/2 = n(n + 1)/2$.
2. Traceless matrices. $\operatorname{tr}$ maps onto $\mathbb{R}$, so its kernel has dimension $n^2 - 1$.
3. Polynomials with a prescribed root. $p \mapsto p(1)$ maps $\mathbb{P}_n$ onto $\mathbb{R}$, so ${p : p(1) = 0}$ has dimension $n$.
4. Interpolation: uniqueness gives existence. For distinct nodes $x_0, \dots, x_n$, let $T : \mathbb{P}_n \to \mathbb{R}^{n+1}$, $T(p) = (p(x_0), \dots, p(x_n))$. A nonzero polynomial of degree at most $n$ has at most $n$ roots, so $\ker T = {0}$. Since the dimensions are equal, $T$ is also surjective: an interpolating polynomial exists for every data set, and no construction was needed.

import numpy as np

def matrix_of(T, shape):
    """Matrix of a linear map on arrays of the given shape, using the entries as coordinates."""
    n = int(np.prod(shape))
    return np.column_stack([np.ravel(T(e.reshape(shape))) for e in np.eye(n)])

def rank_nullity(M):
    r = int(np.linalg.matrix_rank(M))
    return M.shape[1], M.shape[1] - r, r            # (dim V, nullity, rank)

n = 4
print(rank_nullity(matrix_of(lambda A: A - A.T, (n, n))))   # (16, 10, 6): Sym_4 has dim 10, Skew_4 has dim 6
print(rank_nullity(matrix_of(np.trace, (n, n))))            # (16, 15, 1)

nodes = np.array([0.0, 0.5, 1.5, 2.0, 3.0])
Vand = np.vander(nodes, increasing=True)            # p -> (p(x_0), ..., p(x_4)) on P_4
print(rank_nullity(Vand))                           # (5, 0, 5): injective, hence surjective

rng = np.random.default_rng(2)
A = rng.normal(size=(6, 3)) @ rng.normal(size=(3, 8))   # a 6 x 8 matrix of rank 3
print(rank_nullity(A))                              # (8, 5, 3)

Key takeaways

• $\dim V = \dim\ker T + \operatorname{rank} T$ for every linear map out of a finite-dimensional space.
• A map into a smaller space has a nonzero kernel; a map into a larger space is not surjective.
• Between spaces of equal finite dimension, injective, surjective, and bijective are equivalent.
• Rank-nullity computes dimensions of subspaces defined as kernels, such as $\dim\mathrm{Sym}_n = n(n + 1)/2$.
• Uniqueness plus equal dimensions gives existence, as in polynomial interpolation.

🧪 Practice

1. A linear map $T : \mathbb{R}^5 \to \mathbb{R}^3$ has $\dim\ker T = 2$. Is $T$ surjective? What if $\dim\ker T = 3$?
2. Use rank-nullity to find the dimension of ${p \in \mathbb{P}_4 : p(0) = p(1) = 0}$.
3. Is there a linear map $T : \mathbb{R}^4 \to \mathbb{R}^4$ with $\ker T = \operatorname{im} T$? What about $T : \mathbb{R}^3 \to \mathbb{R}^3$? Give an example or prove impossibility.
4. Interview: Why can a system of 5 linear equations in 7 unknowns never have exactly one solution? Can it have no solution? Hint: the coefficient matrix has a kernel of dimension at least $7 - 5 = 2$; it is inconsistent when the right-hand side lies outside the image, which can happen when the rank is below 5.

Injectivity, Surjectivity, and Invertibility

Why it matters. Every equation $T\mathbf{x} = \mathbf{w}$ raises the same questions. Does a solution exist for every $\mathbf{w}$ (surjectivity)? Is it unique (injectivity)? Both (invertibility)? For a general function, injectivity must be checked on all pairs of inputs. For a linear map, it reduces to a single question about the kernel.

Theorem. A linear map $T$ is injective if and only if $\ker T = {\mathbf{0}}$.

Proof. ($\Rightarrow$) $T\mathbf{0} = \mathbf{0}$, so by injectivity no other vector maps to $\mathbf{0}$. ($\Leftarrow$) If $T\mathbf{u} = T\mathbf{v}$, then $T(\mathbf{u} - \mathbf{v}) = \mathbf{0}$, so $\mathbf{u} - \mathbf{v} = \mathbf{0}$. $\blacksquare$

The full picture. Let $T : V \to W$ with $\dim V = n$, $\dim W = m$, and $A$ its $m \times n$ matrix in some bases.

	Injective (one-to-one)	Surjective (onto)
Definition	$T\mathbf{u} = T\mathbf{v} \Rightarrow \mathbf{u} = \mathbf{v}$	every $\mathbf{w}$ equals some $T\mathbf{v}$
Subspace test	$\ker T = {\mathbf{0}}$	$\operatorname{im} T = W$
Rank test	$\operatorname{rank} T = n$	$\operatorname{rank} T = m$
Matrix test	pivot in every column; independent columns	pivot in every row; columns span $F^m$
Effect on sets	independent sets go to independent sets	spanning sets go to spanning sets
One-sided inverse	left inverse $L$ with $LT = I_V$	right inverse $R$ with $TR = I_W$
Solutions of $T\mathbf{x} = \mathbf{w}$	at most one	at least one
Requires	$n \le m$	$n \ge m$

Invertibility. $T$ is invertible if it is bijective. Its inverse function is then automatically linear.

Proof. Take $\mathbf{w}_1, \mathbf{w}_2 \in W$ and let $\mathbf{v}_i = T^{-1}\mathbf{w}_i$. Then $T(c\mathbf{v}_1 + \mathbf{v}_2) = c\mathbf{w}_1 + \mathbf{w}_2$, so $T^{-1}(c\mathbf{w}_1 + \mathbf{w}_2) = c,T^{-1}\mathbf{w}_1 + T^{-1}\mathbf{w}_2$. $\blacksquare$

When $\dim V = \dim W$ is finite, rank-nullity makes the two columns of the table equivalent: injective $\iff$ surjective $\iff$ invertible. This is the core of the Invertible Matrix Theorem (Section 4.3). For square matrices, a one-sided inverse is automatically two-sided: $LA = I$ implies $AL = I$.

Infinite dimensions break the symmetry. On the space $\mathbb{P}$ of all polynomials, $D$ is surjective (every polynomial has an antiderivative) but not injective, and $J$ is injective but not surjective. $DJ = I$ but $JD \ne I$. On sequences, the right shift $(x_1, x_2, \dots) \mapsto (0, x_1, x_2, \dots)$ is injective but not surjective, and the left shift $(x_1, x_2, \dots) \mapsto (x_2, x_3, \dots)$ is surjective but not injective. This is Hilbert's hotel: a full hotel with infinitely many rooms can still take a new guest by moving everyone one room up.

One-sided inverses of matrices. If $A$ ($m \times n$) has independent columns, $A^TA$ is invertible and $L = (A^TA)^{-1}A^T$ is a left inverse; it reappears as the least-squares solver in Chapter 9. If $A$ has independent rows, $R = A^T(AA^T)^{-1}$ is a right inverse. One-sided inverses are not unique: adding to $L$ any matrix that vanishes on $\operatorname{Col} A$ gives another.

import numpy as np

rng = np.random.default_rng(3)
A = rng.normal(size=(5, 3))                    # tall: injective (with probability 1), not surjective
L = np.linalg.solve(A.T @ A, A.T)              # left inverse (A^T A)^{-1} A^T
print(np.allclose(L @ A, np.eye(3)), np.allclose(A @ L, np.eye(5)))   # True False

B = rng.normal(size=(3, 5))                    # wide: surjective, not injective
R = B.T @ np.linalg.inv(B @ B.T)               # right inverse
print(np.allclose(B @ R, np.eye(3)), np.allclose(R @ B, np.eye(5)))   # True False

# Left inverses are not unique: add any N (I - A L), which vanishes on Col A
N = rng.normal(size=(3, 5))
L2 = L + N @ (np.eye(5) - A @ L)
print(np.allclose(L2 @ A, np.eye(3)), np.allclose(L, L2))             # True False

Key takeaways

• A linear map is injective exactly when its kernel is ${\mathbf{0}}$, and surjective exactly when its image is the whole codomain.
• Injective means full column rank and has a left inverse; surjective means full row rank and has a right inverse.
• The inverse of a bijective linear map is automatically linear.
• In finite dimensions with $\dim V = \dim W$, injective, surjective, and invertible are equivalent; in infinite dimensions they are not.
• One-sided inverses exist for full-rank rectangular matrices but are not unique.

🧪 Practice

1. Decide whether each map is injective, surjective, both, or neither: $(x, y) \mapsto (x, y, x + y)$ from $\mathbb{R}^2$ to $\mathbb{R}^3$; $D : \mathbb{P}_3 \to \mathbb{P}_2$; $A \mapsto A^T$ on $\mathbb{R}^{2 \times 2}$.
2. Prove that $T$ is injective if and only if it maps every linearly independent set to a linearly independent set.
3. Find two different left inverses of $A = \begin{bmatrix} 1 & 0 \ 0 & 1 \ 1 & 1 \end{bmatrix}$.
4. Interview: A linear autoencoder compresses $784$-pixel images to a $32$-dimensional code with an encoder $E$ ($32 \times 784$) and a decoder $D$ ($784 \times 32$). Can $DE$ equal the identity? What is the best it can be? Hint: $\operatorname{rank}(DE) \le 32$ and $\dim\ker E \ge 752$; the best possible $DE$ is a projection onto a 32-dimensional subspace, and the optimal one is given by PCA (Chapter 11).

Isomorphisms of Vector Spaces

Why it matters. Computers store arrays of numbers, not polynomials, matrices, or signals. Isomorphisms justify representing those objects as vectors in $F^n$: they say exactly when two vector spaces are "the same" as vector spaces, so that every theorem and algorithm for one transfers to the other.

Definition. An isomorphism is an invertible linear map $T : V \to W$. If one exists, $V$ and $W$ are isomorphic, written $V \cong W$.

Isomorphism is an equivalence relation: the identity is an isomorphism, the inverse of an isomorphism is linear (previous topic), and compositions of isomorphisms are isomorphisms. An isomorphism preserves everything defined in terms of linear combinations: linear independence, spans, bases, dimension, and subspaces together with their dimensions.

Theorem. Finite-dimensional vector spaces $V$ and $W$ over the same field are isomorphic if and only if $\dim V = \dim W$.

Proof. ($\Rightarrow$) An isomorphism sends a basis of $V$ to an independent spanning set of $W$, that is, a basis of $W$. ($\Leftarrow$) Choose bases $(\mathbf{v}_i)$ and $(\mathbf{w}_i)$ of the same length. By Section 7.1 there is a linear $T$ with $T\mathbf{v}_i = \mathbf{w}_i$, and the linear map with $\mathbf{w}_i \mapsto \mathbf{v}_i$ is its inverse. $\blacksquare$

Corollary. Every $n$-dimensional space over $F$ is isomorphic to $F^n$, through the coordinate map $\mathbf{v} \mapsto [\mathbf{v}]_{\mathcal{B}}$ (Section 6.5). Dimension is the only invariant: up to isomorphism, there is exactly one vector space of each finite dimension.

Examples.

Space	Isomorphic to	An isomorphism
$\mathbb{P}_n$	$\mathbb{R}^{n+1}$	coefficient vector $(a_0, \dots, a_n)$
$\mathbb{R}^{m \times n}$	$\mathbb{R}^{mn}$	stacking the entries (reshape, flatten, $\operatorname{vec}$)
$\mathbb{C}$, as a space over $\mathbb{R}$	$\mathbb{R}^2$	$a + bi \mapsto (a, b)$
$2 \times 2$ symmetric matrices	$\mathbb{R}^3$	$\begin{bmatrix} a & b \ b & c \end{bmatrix} \mapsto (a, b, c)$
solutions of $y'' + y = 0$	$\mathbb{R}^2$	$y \mapsto (y(0), y'(0))$, by uniqueness of initial-value problems
$\mathcal{L}(\mathbb{R}^n, \mathbb{R}^m)$	$\mathbb{R}^{m \times n}$	the standard matrix (Section 7.4)

Three caveats.

• Isomorphic is not identical. Most isomorphisms depend on a choice of basis, and different choices give different isomorphisms. The isomorphism $V \cong V^{**}$ of Section 7.4 is a rare example that needs no choice.
• Only the vector space structure is preserved. $\mathbb{R}^{2 \times 2} \cong \mathbb{R}^4$ says nothing about matrix multiplication, and $\mathbb{C} \cong \mathbb{R}^2$ says nothing about complex multiplication. Extra structure needs extra checking.
• Infinite dimensions are subtler. $T(p) = x,p(x)$ is an isomorphism of $\mathbb{P}$ onto the proper subspace $x\mathbb{P}$, something impossible in finite dimensions.

Application: solving matrix equations. The map $X \mapsto AX + XB$ on $\mathbb{R}^{n \times n}$ is linear. Using the column-stacking isomorphism $\operatorname{vec} : \mathbb{R}^{n \times n} \to \mathbb{R}^{n^2}$ and the identity $\operatorname{vec}(AXB) = (B^T \otimes A)\operatorname{vec}(X)$, where $\otimes$ is the Kronecker product, the Sylvester equation $AX + XB = C$ becomes an ordinary linear system

$$\big(I \otimes A + B^T \otimes I\big)\operatorname{vec}(X) = \operatorname{vec}(C).$$

import numpy as np

rng = np.random.default_rng(4)
n = 3
A, B, C = (rng.normal(size=(n, n)) for _ in range(3))

vec = lambda X: X.reshape(-1, order="F")          # stack the columns: R^{3x3} -> R^9
unvec = lambda x: x.reshape(n, n, order="F")      # the inverse isomorphism

X0 = rng.normal(size=(n, n))
print(np.allclose(vec(A @ X0 @ B), np.kron(B.T, A) @ vec(X0)))   # True: vec(AXB) = (B^T kron A) vec(X)

# X -> AX + XB is linear on R^{3x3}; through vec it is a 9 x 9 matrix
K = np.kron(np.eye(n), A) + np.kron(B.T, np.eye(n))
X = unvec(np.linalg.solve(K, vec(C)))
print(np.allclose(A @ X + X @ B, C))              # True

# Linear independence in P_2 is decided in R^3 through coefficient vectors
polys = np.array([[1, 1, 0], [0, 1, 1], [1, 0, 1]]).T   # 1 + x, x + x^2, 1 + x^2 as columns
print(np.linalg.matrix_rank(polys))               # 3: independent, hence a basis of P_2

Key takeaways

• An isomorphism is a bijective linear map; its inverse is automatically linear.
• Finite-dimensional spaces over the same field are isomorphic exactly when they have the same dimension.
• Every $n$-dimensional space is isomorphic to $F^n$ through coordinates; this is why arrays can represent polynomials, matrices, and signals.
• Isomorphisms preserve linear structure only; products and geometry are extra structure.
• Flattening with vec turns linear equations in matrices into ordinary linear systems.

🧪 Practice

1. Which of these spaces are isomorphic: $\mathbb{R}^6$, $\mathbb{P}_5$, $\mathbb{R}^{2 \times 3}$, the $3 \times 3$ symmetric matrices, the traceless $3 \times 3$ matrices, $\mathbb{P}_6$?
2. Write an explicit isomorphism between the $2 \times 2$ symmetric matrices and $\mathbb{P}_2$, and verify that it is linear and bijective.
3. Show that $T : \mathbb{P}_2 \to \mathbb{R}^3$, $T(p) = (p(0), p(1), p(2))$, is an isomorphism, and find $T^{-1}(1, 0, 0)$.
4. Interview: A colleague flattens $28 \times 28$ images into vectors in $\mathbb{R}^{784}$ before training a fully connected network, and says nothing is lost because flattening is an isomorphism. In what sense is this correct, and what information does the network effectively ignore? Hint: flattening is a linear bijection, so the vector-space structure is intact; but which pixels are neighbours is not part of that structure, so a fully connected layer behaves the same under any fixed permutation of the pixels, while a convolutional layer does not.

<a id="74-spaces-of-linear-maps-and-duality"></a>

7.4 Spaces of Linear Maps and Duality

This subchapter treats linear maps themselves as vectors. The most important case is the dual space of linear functionals, which gives coordinate-free meanings to row vectors, to the transpose, and to the orthogonal complement.

The Vector Space L(V, W)

Why it matters. Linear maps can be added and scaled, so they form a vector space of their own. This is what makes sense of a gradient-descent step on a weight matrix ($W \leftarrow W - \eta,G$ is a linear combination of linear maps), of operators such as $D^2 + 3D + 2I$, and of the dual space $V^* = \mathcal{L}(V, F)$ that the rest of this subchapter studies.

Definition. $\mathcal{L}(V, W)$ is the set of all linear maps $V \to W$, with the pointwise operations

$$(S + T)(\mathbf{v}) = S\mathbf{v} + T\mathbf{v}, \qquad (cT)(\mathbf{v}) = c,(T\mathbf{v}).$$

Write $\mathcal{L}(V) = \mathcal{L}(V, V)$ for the operators on $V$.

Closure. $S + T$ is linear: $(S + T)(a\mathbf{u} + \mathbf{v}) = aS\mathbf{u} + S\mathbf{v} + aT\mathbf{u} + T\mathbf{v} = a(S + T)\mathbf{u} + (S + T)\mathbf{v}$. The same computation works for $cT$. The remaining axioms hold pointwise, exactly as for function spaces (Section 6.1), and the zero vector is the zero map.

Theorem. If $\dim V = n$ and $\dim W = m$, then for any bases $\mathcal{B}$ of $V$ and $\mathcal{C}$ of $W$, the map

$$\mathcal{L}(V, W) \to F^{m \times n}, \qquad T \mapsto [T]_{\mathcal{C} \leftarrow \mathcal{B}}$$

is an isomorphism. In particular, $\dim\mathcal{L}(V, W) = mn$.

Proof. Linear: the $j$-th column of $[aS + T]$ is $[(aS + T)\mathbf{v}j]{\mathcal{C}} = a[S\mathbf{v}j]{\mathcal{C}} + [T\mathbf{v}j]{\mathcal{C}}$. Injective: if $[T] = 0$, then $T\mathbf{v}_j = \mathbf{0}$ for every $j$, so $T = 0$. Surjective: any matrix prescribes images of the basis vectors, and Section 7.1 provides a linear map with those images. $\blacksquare$

The matrix units $E_{ij}$ correspond to the rank-one maps that send $\mathbf{v}_j \mapsto \mathbf{w}_i$ and every other basis vector to $\mathbf{0}$. They form a basis of $\mathcal{L}(V, W)$.

Composition adds more structure. Composition $\mathcal{L}(V, W) \times \mathcal{L}(U, V) \to \mathcal{L}(U, W)$ is linear in each argument separately:

$$S \circ (aT_1 + T_2) = a,S \circ T_1 + S \circ T_2, \qquad (aS_1 + S_2) \circ T = a,S_1 \circ T + S_2 \circ T.$$

So in $\mathcal{L}(V)$ we can add, scale, and multiply operators, and polynomials of an operator make sense: $p(T) = a_0I + a_1T + \cdots + a_kT^k$. Polynomials in the same operator commute, so they factor like ordinary polynomials. For example, $D^2 + 3D + 2I = (D + I)(D + 2I)$, which is why solving $y'' + 3y' + 2y = 0$ reduces to the roots $-1$ and $-2$ of $\lambda^2 + 3\lambda + 2$. Chapter 8 develops this idea (the Cayley-Hamilton theorem).

What is not a subspace. The invertible operators do not form a subspace of $\mathcal{L}(V)$: the zero map is not invertible, and $I + (-I) = 0$. Different operators usually do not commute: $DX - XD = I$ on polynomials, where $X$ is multiplication by $x$, because $(x,p)' - x,p' = p$.

import numpy as np
import sympy as sp

n = 4                                           # P_4 with basis 1, x, ..., x^4
D = np.diag(np.arange(1.0, n + 1), k=1)         # D as a 5 x 5 matrix
I = np.eye(n + 1)
L1 = D @ D + 3 * D + 2 * I                      # the operator D^2 + 3D + 2I
L2 = (D + I) @ (D + 2 * I)
print(np.allclose(L1, L2))                      # True: polynomials in one operator factor

x = sp.symbols('x')
p = x**3 - x
coeffs = np.array([float(p.coeff(x, k)) for k in range(n + 1)])
print(L1 @ coeffs)                              # [-3.  4.  9.  2.  0.]
print(sp.expand(p.diff(x, 2) + 3 * p.diff(x) + 2 * p))   # 2*x**3 + 9*x**2 + 4*x - 3

# Operators need not commute: (D X - X D) f = f, where X multiplies by x
f = sp.Function('f')(x)
print(sp.simplify(sp.diff(x * f, x) - x * sp.diff(f, x)))   # f(x)

# Linear combinations of maps correspond to linear combinations of matrices
rng = np.random.default_rng(0)
S, T = rng.normal(size=(2, 3)), rng.normal(size=(2, 3))     # two maps R^3 -> R^2
v = rng.normal(size=3)
print(np.allclose((2 * S - T) @ v, 2 * (S @ v) - T @ v))    # True

Key takeaways

• $\mathcal{L}(V, W)$, the set of linear maps $V \to W$, is a vector space under pointwise addition and scaling.
• Choosing bases identifies $\mathcal{L}(V, W)$ with $F^{m \times n}$, so $\dim\mathcal{L}(V, W) = (\dim V)(\dim W)$.
• Composition is linear in each argument, so operators on $V$ can be multiplied and polynomials $p(T)$ make sense.
• Polynomials in a single operator commute and factor; different operators generally do not commute.
• The invertible operators are not a subspace.

🧪 Practice

1. Show that ${T \in \mathcal{L}(\mathbb{R}^3, \mathbb{R}^2) : T(1, 1, 1) = \mathbf{0}}$ is a subspace of $\mathcal{L}(\mathbb{R}^3, \mathbb{R}^2)$ and find its dimension.
2. Find a basis of $\mathcal{L}(\mathbb{R}^2)$ that consists entirely of invertible maps, and verify that it is a basis.
3. Factor the operator $D^2 - 5D + 6I$ and use the factorization to show that $e^{2x}$ and $e^{3x}$ lie in its kernel.
4. Interview: Can there be $n \times n$ matrices $A$ and $B$ with $AB - BA = I$? On the other hand, $D$ and multiplication by $x$ satisfy $DX - XD = I$ on polynomials. Resolve the apparent contradiction. Hint: take the trace of both sides; $\operatorname{tr}(AB) = \operatorname{tr}(BA)$, but $\operatorname{tr}I = n$; the operators on polynomials act on an infinite-dimensional space, where there is no trace.

Linear Functionals

Why it matters. A linear functional turns a vector into a number, linearly. Measurements, prices, weighted scores, evaluations at a point, integrals, and expectations are all functionals. They describe hyperplanes and linear constraints, they are the scores of linear classifiers, and they are what gradients really are.

Analogy. A shopping basket is a vector of quantities (kilograms of apples, kilograms of rice). A price list is a functional: it turns a basket into a total cost. Prices and quantities are both lists of numbers, but they live in different spaces with different units (euros per kilogram versus kilograms), and combining them with the product "price times quantity" is what produces a number. Column vectors are baskets; row vectors are price lists.

Definition. A linear functional on a vector space $V$ over $F$ is a linear map $\varphi : V \to F$.

Functional	Space	Formula
a coordinate	$\mathbb{R}^n$	$\mathbf{x} \mapsto x_i$
a weighted sum, such as a price list	$\mathbb{R}^n$	$\mathbf{x} \mapsto \mathbf{a}^T\mathbf{x}$
evaluation at a point	$\mathbb{P}_n$ or $C[a, b]$	$p \mapsto p(t)$
definite integral	$C[a, b]$	$f \mapsto \int_a^b f(x),dx$
derivative at a point	$\mathbb{P}_n$	$p \mapsto p'(t)$
trace	$\mathbb{R}^{n \times n}$	$A \mapsto \operatorname{tr}A$
expectation on a finite sample space	random variables	$X \mapsto \sum_i p_iX(\omega_i)$

Functionals on $F^n$ are row vectors. If $\varphi : F^n \to F$ is linear, then $\varphi(\mathbf{x}) = \varphi\big(\sum x_j\mathbf{e}_j\big) = \sum x_j\varphi(\mathbf{e}_j) = \mathbf{a}^T\mathbf{x}$, with $a_j = \varphi(\mathbf{e}_j)$. So a functional is a $1 \times n$ matrix. In general, a functional is determined by its values on a basis, and in a basis $\mathcal{B}$ it is the row $\big(\varphi(\mathbf{v}_1), \dots, \varphi(\mathbf{v}_n)\big)$, with $\varphi(\mathbf{v}) = \big(\varphi(\mathbf{v}_1), \dots, \varphi(\mathbf{v}n)\big),[\mathbf{v}]{\mathcal{B}}$.

Geometry: kernels are hyperplanes. A nonzero functional on an $n$-dimensional space has rank 1 (its image is all of $F$), so by rank-nullity its kernel has dimension $n - 1$: a hyperplane through the origin. The level sets ${\varphi = c}$ are parallel translates of that hyperplane (Section 7.5 calls them cosets). A functional on $\mathbb{R}^2$ is like a tilted plane seen as a topographic map: equally spaced, parallel contour lines.

  values of phi(x, y) = x + 2y on a grid   (x to the right, y upward)

   y =  2 :    2     3     4     5     6
   y =  1 :    0     1     2     3     4
   y =  0 :   -2    -1    [0]    1     2
   y = -1 :   -4    -3    -2    -1     0
            x = -2  x = -1 x = 0 x = 1  x = 2

  - phi grows by 1 per step to the right and by 2 per step up: the row vector [1  2]
  - equal values lie on parallel lines x + 2y = c; the line c = 0 is ker phi

A linear classifier predicts with the sign of $\varphi(\mathbf{x}) + b$. Its decision boundary ${\varphi = -b}$ is one of these level sets.

Application: quadrature rules. On $\mathbb{P}_2$, the integral $I(p) = \int_0^1 p(x),dx$ is a functional, and so are the evaluations $p \mapsto p(0)$, $p(\tfrac12)$, $p(1)$. The next topic shows that these three evaluations form a basis of the functionals on $\mathbb{P}_2$, so $I = w_0,\mathrm{ev}0 + w_1,\mathrm{ev}{1/2} + w_2,\mathrm{ev}_1$ for unique weights. Applying both sides to $1, x, x^2$ gives

$$w_0 + w_1 + w_2 = 1, \qquad \tfrac12 w_1 + w_2 = \tfrac12, \qquad \tfrac14 w_1 + w_2 = \tfrac13,$$

so $(w_0, w_1, w_2) = (\tfrac16, \tfrac23, \tfrac16)$. This is Simpson's rule, derived as an identity between functionals.

import numpy as np
from fractions import Fraction

# Functionals on R^n are rows: price list times basket
prices = np.array([2.5, 1.2, 4.0])               # euros per kg of apples, rice, cheese
basket = np.array([2.0, 5.0, 0.5])               # kg of each
print(prices @ basket)                           # 13.0 euros

# Simpson's rule: write the integral over [0, 1] in terms of evaluations at 0, 1/2, 1
nodes = np.array([0.0, 0.5, 1.0])
V = np.vander(nodes, increasing=True)            # row i: (1, t_i, t_i^2)
moments = np.array([1.0, 1 / 2, 1 / 3])          # integrals of 1, x, x^2 over [0, 1]
w = np.linalg.solve(V.T, moments)                # sum_i w_i t_i^k = k-th moment
print([str(Fraction(c).limit_denominator()) for c in w])   # ['1/6', '2/3', '1/6']

p = np.array([2.0, -3.0, 6.0])                   # 2 - 3x + 6x^2
print(round(w @ (V @ p), 12), moments @ p)       # 2.5 2.5: exact on P_2

Key takeaways

• A linear functional is a linear map $V \to F$; evaluations, integrals, traces, expectations, and weighted sums are examples.
• On $F^n$ every functional is $\mathbf{x} \mapsto \mathbf{a}^T\mathbf{x}$: functionals are row vectors, vectors are columns.
• A functional is determined by its values on a basis.
• The kernel of a nonzero functional is a hyperplane, and its level sets are parallel hyperplanes.
• Quadrature rules such as Simpson's rule are identities between functionals.

🧪 Practice

1. Which of these are linear functionals on $\mathbb{P}2$: $p \mapsto p(0)p(1)$; $p \mapsto p'(2)$; $p \mapsto \int{-1}^{1} x,p(x),dx$; $p \mapsto \max_{[0, 1]} p$?
2. A functional $\varphi$ on $\mathbb{R}^3$ satisfies $\varphi(1, 0, 0) = 2$, $\varphi(1, 1, 0) = 0$, and $\varphi(1, 1, 1) = 5$. Find the row vector $\mathbf{a}$ with $\varphi(\mathbf{x}) = \mathbf{a}^T\mathbf{x}$.
3. Find weights $w_0, w_1$ such that $\int_{-1}^{1} p(x),dx = w_0,p(-1/\sqrt3) + w_1,p(1/\sqrt3)$ for all $p \in \mathbb{P}_1$. Then check that the rule is also exact on $\mathbb{P}_3$ (two-point Gauss-Legendre).
4. Interview: Simpson's rule was derived to be exact on $\mathbb{P}_2$, yet it is exact for cubics too. Explain why using linearity alone. Hint: $\mathbb{P}_3$ is spanned by $\mathbb{P}_2$ and $(x - \tfrac12)^3$; both the integral over $[0, 1]$ and Simpson's rule give $0$ on that cubic by symmetry, and two functionals that agree on a spanning set agree everywhere.

Dual Space and Dual Basis

Why it matters. The functionals on $V$ form a vector space, the space of all possible linear measurements. Its dual basis turns coordinates themselves into functionals: "the $i$-th coordinate in basis $\mathcal{B}$" is a linear functional. Duality explains why row vectors and column vectors behave differently under a change of basis, which matters for gradients, physical units, and tensors.

Definition. The dual space of $V$ is $V^* = \mathcal{L}(V, F)$. By the previous topics, $\dim V^* = (\dim V)(1) = \dim V$ when $V$ is finite-dimensional.

Theorem (dual basis). Let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a basis of $V$. There are unique functionals $\varphi_1, \dots, \varphi_n \in V^*$ with

$$\varphi_i(\mathbf{v}j) = \delta{ij} = \begin{cases} 1 & i = j \ 0 & i \ne j \end{cases},$$

and they form a basis of $V^$, called the dual basis $\mathcal{B}^$.

Proof. Each $\varphi_i$ exists and is unique because a linear map may take any prescribed values on a basis (Section 7.1). If $\sum a_i\varphi_i = 0$, applying both sides to $\mathbf{v}_j$ gives $a_j = 0$, so the $\varphi_i$ are independent. There are $n = \dim V^*$ of them, so they form a basis. $\blacksquare$

Two formulas follow, and they are the reason the dual basis is useful:

$$\mathbf{v} = \sum_{i} \varphi_i(\mathbf{v}),\mathbf{v}i, \qquad \psi = \sum{i} \psi(\mathbf{v}_i),\varphi_i \quad (\psi \in V^*).$$

The first says that $\varphi_i$ is the $i$-th coordinate function of the basis $\mathcal{B}$. The second says that a functional's coordinates in $\mathcal{B}^*$ are its values on $\mathcal{B}$.

Computing a dual basis in $F^n$. Put the basis vectors as the columns of $B$. The dual basis functionals are the rows of $B^{-1}$, because $(B^{-1}B)_{ij} = (\text{row } i \text{ of } B^{-1}) \cdot \mathbf{v}j = \delta{ij}$.

Example. For $\mathcal{B} = \big((1, 1), (1, 2)\big)$, $B^{-1} = \begin{bmatrix} 2 & -1 \ -1 & 1 \end{bmatrix}$, so $\varphi_1(x, y) = 2x - y$ and $\varphi_2(x, y) = -x + y$. Check: $\varphi_1(1, 1) = 1$, $\varphi_1(1, 2) = 0$, $\varphi_2(1, 1) = 0$, $\varphi_2(1, 2) = 1$.

Warning: $\varphi_i$ depends on the whole basis. Keep $\mathbf{v}_1 = (1, 1)$ but change $\mathbf{v}_2$ to $(0, 1)$. Now $B^{-1} = \begin{bmatrix} 1 & 0 \ -1 & 1 \end{bmatrix}$, and $\varphi_1(x, y) = x$, which differs from before although $\mathbf{v}_1$ did not change. "The component along $\mathbf{v}_1$" means nothing until you say which other directions are being discarded.

Example: Lagrange interpolation. For distinct nodes $t_0, \dots, t_n$, the Lagrange polynomials satisfy $L_j(t_i) = \delta_{ij}$. So the evaluations $(\mathrm{ev}{t_0}, \dots, \mathrm{ev}{t_n})$ are exactly the dual basis of $(L_0, \dots, L_n)$, which is why the Lagrange coordinates of $p$ are its values at the nodes (Section 6.5).

Vectors and functionals transform oppositely. Let the new basis be $B' = BP$, so $P = P_{\mathcal{B} \leftarrow \mathcal{B}'}$.

Object	Coordinates	When the basis changes from $B$ to $BP$
vector $\mathbf{v}$	column $[\mathbf{v}]_{\mathcal{B}}$	$[\mathbf{v}]{\mathcal{B}'} = P^{-1}[\mathbf{v}]{\mathcal{B}}$ (contravariant)
functional $\psi$	row $\big(\psi(\mathbf{v}_1), \dots, \psi(\mathbf{v}_n)\big)$	new row $=$ old row $\cdot,P$ (covariant)
the number $\psi(\mathbf{v})$	row times column	unchanged

Units make this concrete. Switch the basis vector from 1 metre to 1 centimetre ($P = \tfrac{1}{100}$). The coordinate of a displacement is multiplied by 100 (2 m becomes 200 cm), but a temperature gradient, a functional, is divided by 100 (3 °C per metre becomes 0.03 °C per centimetre). Their product, the temperature change, is the same in both systems.

The double dual. Each $\mathbf{v} \in V$ defines a functional on $V^$: $\mathrm{ev}{\mathbf{v}}(\varphi) = \varphi(\mathbf{v})$. The map $\mathbf{v} \mapsto \mathrm{ev}{\mathbf{v}}$ from $V$ to $V^{**}$ is linear and injective, and for finite-dimensional $V$ the dimensions match, so it is an isomorphism. It requires no choice of basis, unlike any isomorphism $V \cong V^$, which needs a basis or an inner product (Chapter 9, Riesz representation). In infinite dimensions, $V^*$ can be strictly larger than $V$: the dual of $\mathbb{P}$ is isomorphic to the space of all sequences, because a functional may take arbitrary values on $1, x, x^2, \dots$.

import numpy as np

B = np.array([[1.0, 1.0], [1.0, 2.0]])          # basis (1, 1), (1, 2) as columns
Phi = np.linalg.inv(B)                          # the rows are the dual basis functionals
print(Phi)
# [[ 2. -1.]
#  [-1.  1.]]
print(Phi @ B)                                  # identity: phi_i(v_j) = delta_ij
v = np.array([3.0, 7.0])
c = Phi @ v                                     # coordinates of v, read off by the functionals
print(c, np.allclose(B @ c, v))                 # [-1.  4.] True

# Changing v2 changes phi_1, even though v1 is the same
print(np.linalg.inv(np.array([[1.0, 0.0], [1.0, 1.0]]))[0])   # [1. 0.]: now phi_1(x, y) = x

# Vectors and functionals transform oppositely; their pairing does not change
psi = np.array([3.0, -2.0])                     # psi(x, y) = 3x - 2y in standard coordinates
P = np.array([[2.0, 1.0], [0.0, 1.0]])
B2 = B @ P                                      # the new basis
v_B, v_B2 = np.linalg.solve(B, v), np.linalg.solve(B2, v)
psi_B, psi_B2 = psi @ B, psi @ B2               # values of psi on each basis
print(np.allclose(v_B2, np.linalg.solve(P, v_B)), np.allclose(psi_B2, psi_B @ P))   # True True
print(psi_B @ v_B, psi_B2 @ v_B2, psi @ v)      # -5.0 -5.0 -5.0

Key takeaways

• $V^* = \mathcal{L}(V, F)$ has the same dimension as $V$ when $V$ is finite-dimensional.
• The dual basis satisfies $\varphi_i(\mathbf{v}j) = \delta{ij}$; $\varphi_i$ is the $i$-th coordinate function of the basis.
• In $F^n$ the dual basis consists of the rows of $B^{-1}$, and each $\varphi_i$ depends on the whole basis.
• Vector coordinates change by $P^{-1}$, functional coordinates change by $P$, and the pairing $\psi(\mathbf{v})$ is invariant.
• $V \cong V^{**}$ without any choice; $V \cong V^*$ only after choosing a basis or an inner product.

🧪 Practice

1. Find the dual basis of $\big((1, 0, 0), (1, 1, 0), (1, 1, 1)\big)$ in $\mathbb{R}^3$, and use it to write $(4, -2, 5)$ in that basis.
2. On $\mathbb{P}_1$ with basis $(1, x)$, find the dual basis. Express $\mathrm{ev}_2 : p \mapsto p(2)$ and $p \mapsto \int_0^1 p$ in it.
3. On $\mathbb{P}_2$ with nodes $0, 1, 2$, verify that $(\mathrm{ev}_0, \mathrm{ev}_1, \mathrm{ev}_2)$ is the dual basis of the Lagrange basis. Then write $p \mapsto p'(0)$ as a combination of $\mathrm{ev}_0, \mathrm{ev}_1, \mathrm{ev}_2$; the result is a one-sided finite-difference formula.
4. Interview: A physics simulation changes length units from metres to millimetres. Velocities are multiplied by 1000, but the gradient of a potential is divided by 1000. Explain the difference in terms of vectors and covectors, and say what goes wrong if a code base stores both as the same Vector3 type. Hint: velocity is a vector (coordinates change by $P^{-1}$), the gradient is a functional (it changes by $P$); the potential change $\nabla U \cdot \mathbf{v},\Delta t$ is invariant only if each is converted correctly, and one type for both invites converting the gradient the wrong way.

Transpose of a Linear Map

Why it matters. Section 4.2 defined the transpose of a matrix by swapping indices and proved $(AB)^T = B^TA^T$ by an index computation. The transpose has a coordinate-free meaning: it is the map that pulls functionals back through $T$. This explains the product rule at once, shows why row rank equals column rank, and is the mathematical core of backpropagation.

Definition. Let $T : V \to W$ be linear. The dual map (or transpose) $T' : W^* \to V^*$ is

$$T'(\psi) = \psi \circ T, \qquad \text{that is,} \qquad (T'\psi)(\mathbf{v}) = \psi(T\mathbf{v}).$$

To measure $T\mathbf{v}$ with $\psi$, measure $\mathbf{v}$ with $T'\psi$. Note the reversed direction: $T$ goes from $V$ to $W$, while $T'$ goes from $W^$ to $V^$. $T'$ is linear, since $(a\psi_1 + \psi_2) \circ T = a,\psi_1 \circ T + \psi_2 \circ T$.

               T                                 T'
       V  ----------->  W                V*  <-----------  W*
       v  |---------->  T v          psi o T  <----------|  psi

             (T' psi)(v)  =  psi(T v)

Theorem. If $A = [T]_{\mathcal{C} \leftarrow \mathcal{B}}$, then the matrix of $T'$ relative to the dual bases is the transpose:

$$[T']_{\mathcal{B}^* \leftarrow \mathcal{C}^*} = A^T.$$

Proof. Let $\mathcal{B}^* = (\varphi_j)$ and $\mathcal{C}^* = (\psi_i)$. The coordinates of $T'\psi_i$ in $\mathcal{B}^*$ are its values on the $\mathbf{v}_j$ (previous topic): $(T'\psi_i)(\mathbf{v}_j) = \psi_i(T\mathbf{v}_j) = $ the $i$-th $\mathcal{C}$-coordinate of $T\mathbf{v}j$ $= a{ij}$. So column $i$ of $[T']$ is row $i$ of $A$. $\blacksquare$

In $\mathbb{R}^n$, with functionals written as rows $\mathbf{y}^T$: $T'(\mathbf{y}^T) = \mathbf{y}^TA$, or in column form, $\mathbf{y} \mapsto A^T\mathbf{y}$.

Properties, each with a one-line proof.

Map identity	Proof	Matrix identity
$(S \circ T)' = T' \circ S'$	$\chi \circ S \circ T = T'(S'\chi)$	$(BA)^T = A^TB^T$
$(aS + T)' = aS' + T'$	composition is linear in the first slot	$(aB + A)^T = aB^T + A^T$
$I' = I$	$\psi \circ I = \psi$	$I^T = I$
$(T^{-1})' = (T')^{-1}$	apply the first row to $T \circ T^{-1} = I$	$(A^{-1})^T = (A^T)^{-1}$

The next topic adds the key structural facts $\ker T' = (\operatorname{im} T)^0$ and $\operatorname{im} T' = (\ker T)^0$, which give a coordinate-free proof that $\operatorname{rank} A^T = \operatorname{rank} A$.

Example. Let $D : \mathbb{P}_2 \to \mathbb{P}_1$ and $\psi = \mathrm{ev}_1$ on $\mathbb{P}_1$. Then $D'(\mathrm{ev}_1) = \mathrm{ev}_1 \circ D$ is the functional $p \mapsto p'(1)$ on $\mathbb{P}_2$. In coordinates: $[D] = \begin{bmatrix} 0 & 1 & 0 \ 0 & 0 & 2 \end{bmatrix}$, and $\mathrm{ev}_1$ has values $(1, 1)$ on $(1, x)$. So $D'(\mathrm{ev}_1)$ has values $[D]^T(1, 1)^T = (0, 1, 2)$ on $(1, x, x^2)$, which is $a + bx + cx^2 \mapsto b + 2c = p'(1)$.

Backpropagation is the transpose. For a layer $\mathbf{y} = A\mathbf{x}$ followed by a loss $\ell(\mathbf{y})$, the derivative of $\ell$ at $\mathbf{y}$ is a functional on the output space, the row $\mathbf{g}^T = \nabla\ell(\mathbf{y})^T$. By the chain rule, the derivative of $\ell \circ A$ is $\mathbf{g}^T A = A'(\mathbf{g}^T)$: the gradient with respect to the input is $A^T\mathbf{g}$. Backpropagation applies the transpose of each layer in reverse order, exactly as $(S \circ T)' = T' \circ S'$ predicts. It uses $A^T$, not $A^{-1}$: the transpose always exists, even for non-square or singular layers.

import numpy as np

rng = np.random.default_rng(5)
A = rng.normal(size=(3, 4))                    # T: R^4 -> R^3
y = rng.normal(size=3)                         # a functional psi(w) = y . w on R^3
x = rng.normal(size=4)
print(np.isclose(y @ (A @ x), (A.T @ y) @ x))  # True: psi(T x) = (T' psi)(x)

# D: P_2 -> P_1 pulls ev_1 back to p -> p'(1)
Dm = np.array([[0.0, 1.0, 0.0], [0.0, 0.0, 2.0]])
print(Dm.T @ np.array([1.0, 1.0]))             # [0. 1. 2.]: values of p -> p'(1) on 1, x, x^2

# Backpropagation through a linear layer: loss(x) = 0.5 * ||A x - b||^2
b = rng.normal(size=3)
loss = lambda x: 0.5 * np.sum((A @ x - b) ** 2)
g_out = A @ x - b                              # gradient of the loss with respect to the output
g_in = A.T @ g_out                             # pulled back to the input by the transpose
h = 1e-6
fd = np.array([(loss(x + h * e) - loss(x - h * e)) / (2 * h) for e in np.eye(4)])
print(np.allclose(g_in, fd, atol=1e-6))        # True: matches finite differences

Key takeaways

• The dual map $T' : W^* \to V^*$ is $T'\psi = \psi \circ T$; it pulls measurements back and reverses direction.
• Relative to dual bases, the matrix of $T'$ is $A^T$; this is what the matrix transpose means.
• $(S \circ T)' = T' \circ S'$ explains $(AB)^T = B^TA^T$ without indices.
• Gradients are functionals, so backpropagation through a linear layer multiplies by $A^T$.

🧪 Practice

1. Let $T(x, y) = (x,\ x + y,\ 2y)$ and $\psi(u, v, w) = u - v + w$. Compute $T'\psi$ as a formula, and check your answer using $A^T$.
2. Prove $(S \circ T)' = T' \circ S'$ and $(T^{-1})' = (T')^{-1}$ directly from the definition.
3. For $D : \mathbb{P}_2 \to \mathbb{P}_1$ and $\varphi(q) = \int_0^1 q(x),dx$, describe the functional $D'\varphi$ on $\mathbb{P}_2$ in words.
4. Interview: Why does backpropagation through a linear layer $\mathbf{y} = W\mathbf{x}$ multiply the incoming gradient by $W^T$ rather than by $W^{-1}$? Hint: the gradient is a functional on the output space that must be pulled back to the input space; pulling back is composition, $\mathbf{g}^T W$, which is defined for any shape of $W$, whereas $W^{-1}$ would undo the layer, and it rarely exists.

Annihilators

Why it matters. A subspace can be described in two ways: as the span of some vectors, or as the solution set of some linear equations. The annihilator connects the two descriptions. It is the coordinate-free version of the orthogonal complement and needs no inner product. It also gives a clean proof that row rank equals column rank, and a short certificate that a linear system has no solution.

Definition. For a subset $S \subseteq V$, its annihilator is

$$S^0 = {\varphi \in V^* : \varphi(\mathbf{s}) = 0 \text{ for all } \mathbf{s} \in S}.$$

It is a subspace of $V^*$: if $\varphi$ and $\chi$ vanish on $S$, so does $a\varphi + \chi$. Elements of $U^0$ are exactly the linear equations that every vector of $U$ satisfies.

Theorem. If $U$ is a subspace of a finite-dimensional space $V$, then

$$\dim U + \dim U^0 = \dim V.$$

Proof. Let $\mathbf{v}_1, \dots, \mathbf{v}_k$ be a basis of $U$, extend it to a basis $\mathbf{v}_1, \dots, \mathbf{v}n$ of $V$, and let $\varphi_1, \dots, \varphi_n$ be the dual basis. We claim that $U^0 = \operatorname{span}{\varphi{k+1}, \dots, \varphi_n}$. Each $\varphi_j$ with $j > k$ vanishes on $\mathbf{v}_1, \dots, \mathbf{v}_k$, hence on $U$. Conversely, any $\varphi \in U^0$ equals $\sum_i \varphi(\mathbf{v}_i)\varphi_i$, and $\varphi(\mathbf{v}_i) = 0$ for $i \le k$. So $\dim U^0 = n - k$. $\blacksquare$

The number $n - \dim U$ is the number of independent linear equations needed to cut out $U$: a plane in $\mathbb{R}^3$ needs one equation, and a line needs two.

In $\mathbb{R}^n$. Write functionals as rows $\mathbf{a}^T$. Then $\mathbf{a}^T \in U^0$ exactly when $\mathbf{a} \cdot \mathbf{u} = 0$ for every $\mathbf{u} \in U$, that is, $\mathbf{a} \in U^\perp$. If the columns of $M$ span $U$, then $U^0$ corresponds to $\operatorname{Nul} M^T$, the left null space of Section 6.6.

Example. $U = \operatorname{span}{(1, 0, 1), (0, 1, 1)}$ in $\mathbb{R}^3$. A functional $(a, b, c)$ annihilates $U$ when $a + c = 0$ and $b + c = 0$, so $U^0 = \operatorname{span}{\varphi}$ with $\varphi(x, y, z) = x + y - z$. Hence $U$ is the plane $x + y - z = 0$, and $2 + 1 = 3$.

Example. In $\mathbb{P}_2$, $U = {p : p(1) = 0}$ has dimension 2, and $U^0 = \operatorname{span}{\mathrm{ev}_1}$ has dimension 1.

Kernel and image of the transpose. For a linear $T : V \to W$ between finite-dimensional spaces:

1. $\ker T' = (\operatorname{im} T)^0$.
2. $\operatorname{im} T' = (\ker T)^0$.

Proof. (1) $T'\psi = 0$ means $\psi(T\mathbf{v}) = 0$ for every $\mathbf{v}$, which means $\psi$ vanishes on $\operatorname{im} T$. (2) If $\varphi = T'\psi$ and $\mathbf{v} \in \ker T$, then $\varphi(\mathbf{v}) = \psi(T\mathbf{v}) = 0$, so $\operatorname{im} T' \subseteq (\ker T)^0$. For the dimensions, using (1), the theorem above, and rank-nullity twice: $\dim\operatorname{im} T' = \dim W - \dim\ker T' = \dim W - (\dim W - \operatorname{rank} T) = \operatorname{rank} T = \dim V - \dim\ker T = \dim(\ker T)^0$. $\blacksquare$

Corollary (row rank equals column rank). $\operatorname{rank} T' = \operatorname{rank} T$, so $\operatorname{rank} A^T = \operatorname{rank} A$ for every matrix, with no row reduction involved.

Corollary (Fredholm alternative). $T\mathbf{v} = \mathbf{w}$ has a solution if and only if $\psi(\mathbf{w}) = 0$ for every $\psi \in \ker T'$. For matrices: $A\mathbf{x} = \mathbf{b}$ is solvable if and only if $\mathbf{y}^T\mathbf{b} = 0$ for every $\mathbf{y}$ with $\mathbf{y}^TA = \mathbf{0}^T$, the condition $\mathbf{b} \perp \operatorname{Nul} A^T$ of Section 6.6. A single $\mathbf{y}$ with $\mathbf{y}^TA = \mathbf{0}^T$ and $\mathbf{y}^T\mathbf{b} \ne 0$ is a certificate of infeasibility: anyone can verify it with two products, without solving anything.

Coordinate-free	Real matrices with the dot product
$\operatorname{im} T$	$\operatorname{Col} A$
$\ker T$	$\operatorname{Nul} A$
$\ker T' = (\operatorname{im} T)^0$	$\operatorname{Nul} A^T = (\operatorname{Col} A)^\perp$
$\operatorname{im} T' = (\ker T)^0$	$\operatorname{Row} A = (\operatorname{Nul} A)^\perp$

import numpy as np
import sympy as sp

M = sp.Matrix([[1, 0], [0, 1], [1, 1]])        # U = span{(1, 0, 1), (0, 1, 1)} as columns
ann = M.T.nullspace()                          # rows a with a . u = 0 for every u in U
print([a.T for a in ann])                      # [Matrix([[-1, -1, 1]])]: the equation -x - y + z = 0
print(M.rank() + len(ann))                     # 3 = dim R^3

# A certificate that A x = b has no solution
A = sp.Matrix([[1, 2, 1], [2, 4, 0], [3, 6, 1]])   # row 3 = row 1 + row 2
b = sp.Matrix([1, 0, 0])
for y in A.T.nullspace():
    print(y.T, (y.T * A).tolist(), (y.T * b)[0])
# Matrix([[-1, -1, 1]]) [[0, 0, 0]] -1  -> y^T A = 0 but y^T b != 0: inconsistent

# Row rank equals column rank, for a random rank-deficient matrix
rng = np.random.default_rng(6)
R = rng.normal(size=(5, 2)) @ rng.normal(size=(2, 7))
print(np.linalg.matrix_rank(R), np.linalg.matrix_rank(R.T))   # 2 2

Key takeaways

• $S^0$ is the set of functionals that vanish on $S$; for a subspace $U$, it is the set of linear equations satisfied by $U$.
• $\dim U + \dim U^0 = \dim V$: a subspace of dimension $k$ needs $n - k$ independent equations.
• In $\mathbb{R}^n$ the annihilator corresponds to the orthogonal complement, but its definition needs no inner product.
• $\ker T' = (\operatorname{im} T)^0$ and $\operatorname{im} T' = (\ker T)^0$; hence row rank equals column rank.
• $A\mathbf{x} = \mathbf{b}$ is unsolvable exactly when some $\mathbf{y}$ has $\mathbf{y}^TA = \mathbf{0}^T$ and $\mathbf{y}^T\mathbf{b} \ne 0$.

🧪 Practice

1. For $U = \operatorname{span}{(1, 2, 0, 1), (0, 1, 1, 1)} \subseteq \mathbb{R}^4$, find a basis of $U^0$ and describe $U$ as the solution set of two linear equations.
2. In $\mathbb{P}_3$, let $U = {p : p(0) = p(1) = 0}$. Find $\dim U$, and show that $U^0 = \operatorname{span}{\mathrm{ev}_0, \mathrm{ev}_1}$.
3. Prove that $S \subseteq T$ implies $T^0 \subseteq S^0$, and that $(U + W)^0 = U^0 \cap W^0$ for subspaces $U, W$.
4. Interview: A linear solver reports that $A\mathbf{x} = \mathbf{b}$ is inconsistent. How could it give you a short proof that you can verify independently, without re-solving the system? Hint: return a vector $\mathbf{y}$ with $A^T\mathbf{y} = \mathbf{0}$ and $\mathbf{y} \cdot \mathbf{b} \ne 0$; if a solution existed, $\mathbf{y} \cdot \mathbf{b} = \mathbf{y} \cdot A\mathbf{x} = (A^T\mathbf{y}) \cdot \mathbf{x} = 0$. Farkas' lemma is the analogous certificate for linear programming.

<a id="75-quotient-spaces"></a>

7.5 Quotient Spaces

This subchapter builds a new vector space by treating every vector of a chosen subspace as zero. Quotients make "equal up to ..." precise, and they give the cleanest description of what every linear map does: collapse its kernel and identify what remains with its image.

Cosets and Quotient Construction

Why it matters. Many situations treat two vectors as the same when they differ by an element of a fixed subspace. Antiderivatives are defined only up to a constant. Solutions of $A\mathbf{x} = \mathbf{b}$ differ by vectors in $\operatorname{Nul} A$. Signals are often compared up to a constant offset. Modular arithmetic (Section 1.2) treats integers as equal when they differ by a multiple of $n$. The quotient space $V/U$ makes "up to $U$" into a vector space in its own right.

Analogy. A 12-hour clock cannot tell 3 o'clock from 15 o'clock: it forgets multiples of 12. The quotient $V/U$ is a clock for vectors: it forgets the components in $U$ and keeps only what is left. Unlike a projection, it does not need a "floor" to project onto; it simply declares the differences in $U$ invisible.

Cosets. Let $U$ be a subspace of $V$. Define $\mathbf{v} \sim \mathbf{w}$ when $\mathbf{v} - \mathbf{w} \in U$. This is an equivalence relation (Section 1.1):

• reflexive, because $\mathbf{v} - \mathbf{v} = \mathbf{0} \in U$;
• symmetric, because $U$ is closed under negation;
• transitive, because $(\mathbf{u} - \mathbf{v}) + (\mathbf{v} - \mathbf{w}) = \mathbf{u} - \mathbf{w}$ and $U$ is closed under addition.

The equivalence class of $\mathbf{v}$ is the coset

$$\mathbf{v} + U = {\mathbf{v} + \mathbf{u} : \mathbf{u} \in U}.$$

Basic facts:

• $\mathbf{v} + U = \mathbf{w} + U$ if and only if $\mathbf{v} - \mathbf{w} \in U$. Any element of a coset can serve as its representative.
• Two cosets are either equal or disjoint, so the cosets partition $V$.
• Geometrically, the cosets are the translates of $U$, all parallel to it. Only $\mathbf{0} + U = U$ is a subspace; the others are affine subspaces.

   V = R^2,  U = span{(1, 1)}: the cosets are the lines parallel to y = x

            y
            |        /     /     /     /
            |      /     /     /     /        each slanted line is ONE element of R^2 / U
            |    /     /     /     /
            |  /     /     /     /            (2, 0) + U  =  (3, 1) + U  =  (0, -2) + U
   ---------O-----*-----*-----*---------- x   a coset can be named by any of its points
           /     /     /     /
          U  (1,0)+U (2,0)+U (3,0)+U

The quotient space. $V/U$ is the set of all cosets of $U$, with

$$(\mathbf{v} + U) + (\mathbf{w} + U) = (\mathbf{v} + \mathbf{w}) + U, \qquad c,(\mathbf{v} + U) = c\mathbf{v} + U.$$

Well-definedness is the crucial check. These formulas are stated in terms of representatives, so the result must not depend on which representatives are used. Suppose $\mathbf{v} + U = \mathbf{v}' + U$ and $\mathbf{w} + U = \mathbf{w}' + U$. Then

$$(\mathbf{v} + \mathbf{w}) - (\mathbf{v}' + \mathbf{w}') = (\mathbf{v} - \mathbf{v}') + (\mathbf{w} - \mathbf{w}') \in U, \qquad c\mathbf{v} - c\mathbf{v}' = c(\mathbf{v} - \mathbf{v}') \in U,$$

so the sums and scalar multiples are the same cosets. This is exactly where $U$ being a subspace is used. The vector space axioms are then inherited from $V$, the zero vector of $V/U$ is the coset $\mathbf{0} + U = U$, and $-(\mathbf{v} + U) = -\mathbf{v} + U$.

The quotient map. $\pi : V \to V/U$, $\pi(\mathbf{v}) = \mathbf{v} + U$, is linear by the definition of the operations, surjective, and has $\ker\pi = U$, since $\mathbf{v} + U = U$ exactly when $\mathbf{v} \in U$. So every subspace is the kernel of some linear map.

Examples.

$V$	$U$	$V/U$ behaves like	A natural label for $\mathbf{v} + U$
$\mathbb{R}^2$	the $x$-axis	$\mathbb{R}$	the $y$-coordinate
$\mathbb{R}^2$	$\operatorname{span}{(1, 1)}$	$\mathbb{R}$	$x - y$
$\mathbb{P}_n$	constants	$\mathbb{P}_{n-1}$	the derivative $p'$
$\mathbb{R}^n$	$\operatorname{Nul} A$	$\operatorname{Col} A$	$A\mathbf{x}$
$\mathbb{R}^{n \times n}$	symmetric matrices	skew-symmetric matrices	$\tfrac12(A - A^T)$
$\mathbb{Z}$ (an analogy; not a vector space)	$n\mathbb{Z}$	$\mathbb{Z}_n$	the remainder mod $n$

The indefinite integral is literally a coset: $\int 2x,dx = x^2 + C$ is the element $x^2 + {\text{constants}}$ of a quotient space, and "$+C$" names the subspace being ignored.

Computing with cosets. In code, a coset is stored as one representative together with $U$; equality is tested by checking whether the difference lies in $U$. With an inner product there is a canonical representative: the unique one orthogonal to $U$, which is also the shortest. It is $(I - P_U)\mathbf{v}$, where $P_U$ is the orthogonal projection onto $U$ (Section 7.1).

import numpy as np

class Coset:
    """The coset v + U in R^n, where U is the column space of the matrix U."""
    def __init__(self, v, U):
        self.v, self.U = np.asarray(v, dtype=float), U

    def __eq__(self, other):                      # v + U == w + U  iff  v - w lies in U
        d = self.v - other.v
        return np.linalg.matrix_rank(np.column_stack([self.U, d])) == np.linalg.matrix_rank(self.U)

    def __add__(self, other):
        return Coset(self.v + other.v, self.U)

    def __rmul__(self, c):
        return Coset(c * self.v, self.U)

    def canonical(self):                          # the representative orthogonal to U (the shortest)
        P = self.U @ np.linalg.pinv(self.U)       # orthogonal projection onto U
        return self.v - P @ self.v

U = np.array([[1.0], [1.0]])                      # U = span{(1, 1)} in R^2
a, a2 = Coset([2, 0], U), Coset([3, 1], U)        # two names for the same coset
b, b2 = Coset([0, 1], U), Coset([-4, -3], U)
print(a == a2, b == b2, a == b)                   # True True False
print((a + b) == (a2 + b2), (3 * a) == (3 * a2))  # True True: the result does not depend on the names
print(a.canonical(), a2.canonical())              # [ 1. -1.] [ 1. -1.]: one canonical representative
print(np.linalg.norm(a.v), round(np.linalg.norm(a2.v), 4))   # 2.0 3.1623: "length of a representative" is not well defined

Key takeaways

• For a subspace $U$, vectors are equivalent when their difference lies in $U$; the equivalence classes are the cosets $\mathbf{v} + U$, parallel translates of $U$.
• $V/U$, the set of cosets, is a vector space under $(\mathbf{v} + U) + (\mathbf{w} + U) = (\mathbf{v} + \mathbf{w}) + U$ and $c(\mathbf{v} + U) = c\mathbf{v} + U$.
• Any operation defined through representatives must be checked for well-definedness; the vector space operations pass because $U$ is a subspace.
• The quotient map $\pi : V \to V/U$ is linear and surjective with kernel $U$.
• "$+C$" in an indefinite integral and solution sets $\mathbf{x}_p + \operatorname{Nul} A$ are cosets.

🧪 Practice

1. In $\mathbb{R}^3$ with $U = \operatorname{span}{(1, 0, 1)}$, decide whether $(1, 2, 3) + U = (3, 2, 5) + U$, and whether $(1, 2, 3) + U = (0, 2, 3) + U$.
2. In $\mathbb{P}_2$ with $U$ the constant polynomials, show that $p + U = q + U$ if and only if $p' = q'$. Describe the coset $x^2 + U$ as a set.
3. Show that defining $\lVert \mathbf{v} + U\rVert = \lVert\mathbf{v}\rVert$ is not well defined, but $\lVert \mathbf{v} + U\rVert = \min_{\mathbf{u} \in U}\lVert\mathbf{v} + \mathbf{u}\rVert$ is. Compute it for $(2, 0) + \operatorname{span}{(1, 1)}$.
4. Interview: In a game, you want to compare positions of objects while ignoring the "up" direction. One programmer proposes dropping the $z$-coordinate; another proposes working in $\mathbb{R}^3/\operatorname{span}{\mathbf{u}}$, where $\mathbf{u}$ is the up vector. When do the two approaches agree, and when is the quotient the cleaner design? Hint: dropping $z$ quietly chooses the $xy$-plane as the set of representatives, which only matches when $\mathbf{u} = \mathbf{e}_z$; on a curved planet the up vector varies, and "equal up to $\mathbf{u}$" stays meaningful while "drop a coordinate" does not.

Dimension of a Quotient Space

Why it matters. The dimension of $V/U$ measures how many independent directions survive when $U$ is ignored. This is the number of "effective degrees of freedom", the number of linear equations needed to describe $U$, and it stays meaningful even when $V$ and $U$ are both infinite-dimensional.

Theorem. If $V$ is finite-dimensional and $U$ is a subspace, then

$$\dim(V/U) = \dim V - \dim U.$$

Proof 1 (rank-nullity). The quotient map $\pi : V \to V/U$ is surjective with kernel $U$, so $\dim V = \dim U + \dim(V/U)$. $\blacksquare$

Proof 2 (an explicit basis). Extend a basis $\mathbf{u}_1, \dots, \mathbf{u}_k$ of $U$ to a basis $\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_1, \dots, \mathbf{w}_r$ of $V$. Then $\mathbf{w}_1 + U, \dots, \mathbf{w}_r + U$ is a basis of $V/U$. Spanning: $\mathbf{v} = \sum a_i\mathbf{u}_i + \sum b_j\mathbf{w}_j$ gives $\mathbf{v} + U = \sum b_j(\mathbf{w}_j + U)$, because the $\mathbf{u}_i$ terms lie in $U$. Independence: if $\sum b_j(\mathbf{w}_j + U) = U$, then $\sum b_j\mathbf{w}_j \in U$, so it is a combination of the $\mathbf{u}_i$, and independence of the full basis forces every $b_j = 0$. $\blacksquare$

Codimension. The number $\dim(V/U)$ is the codimension of $U$ in $V$. By the annihilator theorem (Section 7.4), it equals $\dim U^0$: the number of independent linear equations needed to cut out $U$. A hyperplane is a subspace of codimension 1.

Subspace $U$ of $V$	$\dim U$	$\operatorname{codim} U = \dim(V/U)$
${\mathbf{0}}$ in $\mathbb{R}^3$	$0$	$3$
a line in $\mathbb{R}^3$	$1$	$2$
a plane in $\mathbb{R}^3$	$2$	$1$
$\mathrm{Sym}_n$ in $\mathbb{R}^{n \times n}$	$n(n + 1)/2$	$n(n - 1)/2$
$\mathbb{P}_{n-1}$ in $\mathbb{P}_n$	$n$	$1$ (the leading coefficient)
${p : p(0) = 0}$ in $\mathbb{P}$ (all polynomials)	infinite	$1$

The last row shows why quotients matter in infinite dimensions: $\dim V - \dim U$ is meaningless there, but $\mathbb{P}/{p : p(0) = 0} \cong \mathbb{R}$ through $p + U \mapsto p(0)$, so the codimension is exactly 1.

Quotients versus complements. If $V = U \oplus W$, then $W \cong V/U$ through $\mathbf{w} \mapsto \mathbf{w} + U$. It is injective because $W \cap U = {\mathbf{0}}$, and surjective because $\mathbf{v} = \mathbf{u} + \mathbf{w}$ gives $\mathbf{v} + U = \mathbf{w} + U$. Every complement meets every coset in exactly one point, so every complement is a copy of $V/U$. But a subspace has many complements, while the quotient is unique:

   U = span{(1, 1)} in R^2; a coset is labelled by c = x - y

   coset label  c                  -1         0         1         2
   where it meets W1 = y-axis    (0, 1)    (0, 0)    (0, -1)   (0, -2)
   where it meets W2 = x-axis    (-1, 0)   (0, 0)    (1, 0)    (2, 0)

   W1 and W2 are different complements of U, and both are copies of R^2 / U.
   The quotient itself needs no such choice.

When an inner product is available, the orthogonal complement $U^\perp$ is a canonical choice (Chapter 9); that is the representative canonical() used in the previous topic.

import sympy as sp

def quotient_basis(Ucols):
    """Extend a basis of U (given as columns) with standard vectors.
    The added vectors w_j give the basis w_j + U of V / U."""
    n, k = Ucols.rows, Ucols.cols
    M = Ucols.row_join(sp.eye(n))
    _, pivots = M.rref()                       # the first k pivots are the columns of U
    return [M[:, j] for j in pivots[k:]]

U = sp.Matrix([[1, 0], [0, 1], [1, 1], [0, 1]])    # U = span{(1,0,1,0), (0,1,1,1)} in R^4
W = quotient_basis(U)
print([w.T for w in W])                        # [Matrix([[1, 0, 0, 0]]), Matrix([[0, 1, 0, 0]])]
print(len(W) == U.rows - U.rank())             # True: dim V/U = 4 - 2

# Coordinates of the coset v + U in that basis: solve v = U a + W c and keep c
v = sp.Matrix([3, 1, 2, 5])
sol = U.row_join(sp.Matrix.hstack(*W)).solve(v)
print(sol.T, "-> coset coordinates", sol[2:, :].T)
# Matrix([[-3, 5, 6, -4]]) -> coset coordinates Matrix([[6, -4]])

Key takeaways

• $\dim(V/U) = \dim V - \dim U$; extending a basis of $U$ gives a basis of $V/U$.
• The codimension $\dim(V/U)$ equals $\dim U^0$, the number of independent equations defining $U$.
• Codimension can be finite even when $V$ and $U$ are infinite-dimensional.
• Every complement $W$ of $U$ is isomorphic to $V/U$, but complements are not unique, while the quotient is.

🧪 Practice

1. Find $\dim(\mathbb{R}^4/U)$ for $U = {\mathbf{x} : x_1 + x_2 + x_3 + x_4 = 0}$ and for $U = \operatorname{span}{(1, 1, 0, 0), (2, 2, 0, 0)}$.
2. Let $U = {p \in \mathbb{P}_3 : p(1) = 0}$. Show that $p + U \mapsto p(1)$ is a well-defined isomorphism $\mathbb{P}_3/U \to \mathbb{R}$, and give a basis of $\mathbb{P}_3/U$.
3. Prove that if $V = U \oplus W$, then $\mathbf{w} \mapsto \mathbf{w} + U$ is an isomorphism $W \to V/U$.
4. Interview: A model has 100 parameters, and a team imposes 7 linear constraints on them. How many free parameters remain? What changes if two of the constraints turn out to be consequences of the others? Hint: the feasible set (if nonempty) is a coset of the subspace cut out by the homogeneous constraints; its dimension is $100 - r$, where $r$ is the rank of the constraint functionals, so $93$ if they are independent and $95$ if only $5$ are.

First Isomorphism Theorem

Why it matters. Every linear map does two things: it collapses its kernel to zero, and it is one-to-one on everything else. The first isomorphism theorem states this precisely: $V/\ker T \cong \operatorname{im} T$. It explains rank-nullity, factors every map into simple pieces, and underlies the rank factorization $A = CR$ and low-rank compression of matrices.

Analogy. Shadows again. The map from a 3D point to its shadow on the floor collapses every vertical line (a coset of the kernel) to a single point. After that collapse, nothing more is lost: different vertical lines cast different shadows. So the set of vertical lines is "the same" as the set of shadows.

Theorem (first isomorphism theorem). Let $T : V \to W$ be linear and $K = \ker T$. Then

$$\tilde T : V/K \to \operatorname{im} T, \qquad \tilde T(\mathbf{v} + K) = T\mathbf{v}$$

is a well-defined isomorphism. In particular, $V/\ker T \cong \operatorname{im} T$.

Proof.

• Well defined. If $\mathbf{v} + K = \mathbf{v}' + K$, then $\mathbf{v} - \mathbf{v}' \in K$, so $T\mathbf{v} = T\mathbf{v}'$.
• Linear. $\tilde T\big(c(\mathbf{v} + K) + (\mathbf{w} + K)\big) = \tilde T\big((c\mathbf{v} + \mathbf{w}) + K\big) = c,T\mathbf{v} + T\mathbf{w}$.
• Injective. If $\tilde T(\mathbf{v} + K) = \mathbf{0}$, then $T\mathbf{v} = \mathbf{0}$, so $\mathbf{v} \in K$ and $\mathbf{v} + K = K$, the zero coset.
• Surjective. Every element of $\operatorname{im} T$ is some $T\mathbf{v} = \tilde T(\mathbf{v} + K)$. $\blacksquare$

The first and third steps are converses of each other: same coset $\iff$ same image.

Every linear map factors into three simple pieces.

                              T
           V  ------------------------------------>  W
           |                                         ^
     pi    |  surjective:                            |  iota
           |  collapses ker T                        |  injective: the inclusion of im T into W
           v                                         |
        V / ker T  ------------------------------>  im T
                     T~ : an isomorphism

                    T  =  iota  o  T~  o  pi

Consequences.

• Rank-nullity again. $\dim V - \dim\ker T = \dim(V/\ker T) = \dim\operatorname{im} T$.
• Surjective maps identify quotients. If $T : V \to W$ is onto, then $W \cong V/\ker T$:
  • $D : \mathbb{P}n \to \mathbb{P}{n-1}$ gives $\mathbb{P}n/{\text{constants}} \cong \mathbb{P}{n-1}$;
  • $\operatorname{tr}$ gives $\mathbb{R}^{n \times n}/{\text{traceless}} \cong \mathbb{R}$;
  • $A \mapsto \tfrac12(A - A^T)$ gives $\mathbb{R}^{n \times n}/\mathrm{Sym}_n \cong \mathrm{Skew}_n$.
• The indefinite integral is an inverse. $\tilde D : \mathbb{P}n/{\text{constants}} \to \mathbb{P}{n-1}$ is an isomorphism, and its inverse sends $q$ to the coset $J(q) + {\text{constants}}$, which is "$\int q,dx = J(q) + C$".
• Relation to Section 6.6. There, $A$ restricted to $\operatorname{Row} A$ was an isomorphism onto $\operatorname{Col} A$. $\operatorname{Row} A$ is one particular complement of $\operatorname{Nul} A$, the orthogonal one, so it is a copy of $\mathbb{R}^n/\operatorname{Nul} A$. The quotient version needs no inner product.

Matrix version: rank factorization. Let $A$ be $m \times n$ of rank $r$. Then $A = CR$ with

• $C$ ($m \times r$): the pivot columns of $A$, which are independent, so $C$ is injective; they form a basis of $\operatorname{Col} A$;
• $R$ ($r \times n$): the nonzero rows of $\operatorname{rref}(A)$, which are independent rows, so $R$ is surjective onto $F^r$.

$R$ plays the role of $\pi$: $R\mathbf{x} = R\mathbf{x}'$ exactly when $\mathbf{x} - \mathbf{x}' \in \operatorname{Nul} A$, so $R\mathbf{x}$ is a coordinate vector for the coset $\mathbf{x} + \operatorname{Nul} A$. $C$ plays the role of $\iota \circ \tilde T$. The identity $A = CR$ holds because column $j$ of $\operatorname{rref}(A)$ lists the coefficients that express column $j$ of $A$ through the pivot columns.

Storing $C$ and $R$ takes $r(m + n)$ numbers instead of $mn$. This is the idea behind low-rank compression and low-rank adapters (LoRA) for fine-tuning large models, where a weight update is learned as a product of two thin matrices. The SVD (Chapter 11) gives the best such factorization when $A$ is only approximately low-rank.

import sympy as sp

A = sp.Matrix([[1, 2, 0, 3], [2, 4, 1, 4], [3, 6, 1, 7]])   # row 3 = row 1 + row 2
rref, pivots = A.rref()
r = len(pivots)
C = A[:, list(pivots)]                   # pivot columns: injective, a basis of Col A
R = rref[:r, :]                          # nonzero rows of the RREF: surjective onto F^r
print(pivots, r)                         # (0, 2) 2
print(C.tolist(), R.tolist())            # [[1, 0], [2, 1], [3, 1]] [[1, 2, 0, 3], [0, 0, 1, -2]]
print(C * R == A)                        # True

# R x labels the coset x + Nul A: adding a kernel vector does not change it
x = sp.Matrix([1, 1, 1, 1])
for k in A.nullspace():
    print(k.T, (R * (x + 5 * k)).T == (R * x).T)
# Matrix([[-2, 1, 0, 0]]) True
# Matrix([[-3, 0, 2, 1]]) True

# The inverse of D~ : P_3 / constants -> P_2 is the indefinite integral
t = sp.symbols('t')
q = 3 * t**2 - 4 * t + 1
print(sp.integrate(q, t), "+ C")         # t**3 - 2*t**2 + t + C: one coset, many representatives

Key takeaways

• For any linear $T$, the map $\mathbf{v} + \ker T \mapsto T\mathbf{v}$ is a well-defined isomorphism $V/\ker T \cong \operatorname{im} T$.
• Every linear map factors as a surjection (collapse the kernel), an isomorphism, and an injection (include the image).
• Rank-nullity is the dimension count of this isomorphism.
• For matrices this is the rank factorization $A = CR$ into an injective $m \times r$ and a surjective $r \times n$ factor.
• Low-rank storage uses $r(m + n)$ numbers instead of $mn$, which is the basis of matrix compression and LoRA.

🧪 Practice

1. Show that $\mathbb{R}^3/\operatorname{span}{(1, 1, 1)} \cong \mathbb{R}^2$ by finding a surjective linear map $\mathbb{R}^3 \to \mathbb{R}^2$ whose kernel is $\operatorname{span}{(1, 1, 1)}$.
2. Compute a rank factorization $A = CR$ for $A = \begin{bmatrix} 1 & 1 & 2 \ 2 & 2 & 4 \ 0 & 1 & 1 \end{bmatrix}$, and check that $R\mathbf{x}$ is unchanged when a kernel vector is added to $\mathbf{x}$.
3. Apply the theorem to $T(A) = A - A^T$ on $\mathbb{R}^{n \times n}$ to identify $\mathbb{R}^{n \times n}/\mathrm{Sym}_n$, and compute its dimension.
4. Interview: Explain why every $m \times n$ matrix of rank $r$ can be written as the product of an $m \times r$ and an $r \times n$ matrix, and why this matters when fine-tuning a model with $4096 \times 4096$ weight matrices using rank-8 updates. Hint: factor through the $r$-dimensional image (first isomorphism theorem); the update needs $8 \cdot (4096 + 4096) = 65{,}536$ parameters instead of $4096^2 \approx 16.8$ million, about 0.4% as many.

<a id="8-eigenvalues-and-eigenvectors"></a>