Part I: Foundations — Chapter 2

Linear Maps

Definition, kernel, image, rank-nullity theorem, and matrix representation

2.1 Definition of Linear Maps

A linear map (also called a linear transformation or linear operator) is a function between vector spaces that preserves the operations of vector addition and scalar multiplication. Linear maps are the "structure-preserving maps" (morphisms) of vector spaces.

Definition: Linear Map

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

$$T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v}) \qquad \text{(additivity)}$$

$$T(\alpha \mathbf{v}) = \alpha T(\mathbf{v}) \qquad \text{(homogeneity)}$$

Equivalently, in a single condition: $T(\alpha\mathbf{u} + \beta\mathbf{v}) = \alpha T(\mathbf{u}) + \beta T(\mathbf{v})$for all $\alpha, \beta \in \mathbb{F}$.

The set of all linear maps from $V$ to $W$ is denoted $\mathcal{L}(V, W)$or $\text{Hom}(V, W)$. When $V = W$, we write $\mathcal{L}(V)$ and call elements endomorphisms. An invertible linear map is an isomorphism.

Derivation 1: $T(\mathbf{0}) = \mathbf{0}$

Every linear map sends the zero vector to the zero vector. This follows from homogeneity:

$$T(\mathbf{0}) = T(0 \cdot \mathbf{v}) = 0 \cdot T(\mathbf{v}) = \mathbf{0}$$

This provides a quick test: if a function doesn't map $\mathbf{0}$ to $\mathbf{0}$, it cannot be linear. For example, the translation $T(\mathbf{x}) = \mathbf{x} + \mathbf{b}$(with $\mathbf{b} \neq \mathbf{0}$) is not linear but affine.

Important Examples of Linear Maps

Zero map: $T(\mathbf{v}) = \mathbf{0}$ for all $\mathbf{v}$.
Identity map: $I(\mathbf{v}) = \mathbf{v}$.
Differentiation: $D: \mathcal{P}_n \to \mathcal{P}_{n-1}$ defined by $D(p) = p'$.
Integration: $\int_0^x: \mathcal{P}_n \to \mathcal{P}_{n+1}$.
Projection: $\pi(\mathbf{v}) = \frac{\langle \mathbf{v}, \mathbf{u}\rangle}{\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u}$.
Rotation: $R_\theta: \mathbb{R}^2 \to \mathbb{R}^2$ by angle $\theta$.

2.2 Kernel and Image

Definition: Kernel

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}\}$$

Definition: Image

The image (or range) of $T$ is:

$$\text{Im}(T) = \{T(\mathbf{v}) : \mathbf{v} \in V\} = \{w \in W : \exists\, \mathbf{v} \in V,\, T(\mathbf{v}) = \mathbf{w}\}$$

Derivation 2: Kernel is a Subspace

We verify that $\ker(T)$ is a subspace of $V$ using the subspace test. First, $T(\mathbf{0}) = \mathbf{0}$ so $\mathbf{0} \in \ker(T)$. Now let $\mathbf{u}, \mathbf{v} \in \ker(T)$ and $\alpha \in \mathbb{F}$:

$$T(\alpha\mathbf{u} + \mathbf{v}) = \alpha T(\mathbf{u}) + T(\mathbf{v}) = \alpha \cdot \mathbf{0} + \mathbf{0} = \mathbf{0}$$

So $\alpha\mathbf{u} + \mathbf{v} \in \ker(T)$. Similarly, $\text{Im}(T)$ is a subspace of $W$.

The kernel measures the "failure of injectivity": $T$ is injective (one-to-one) if and only if $\ker(T) = \{\mathbf{0}\}$. This follows because$T(\mathbf{u}) = T(\mathbf{v})$ implies $T(\mathbf{u} - \mathbf{v}) = \mathbf{0}$, so $\mathbf{u} - \mathbf{v} \in \ker(T)$.

2.3 The Rank-Nullity Theorem

The rank-nullity theorem is one of the most fundamental results in linear algebra. It provides an exact relationship between the dimensions of the kernel and image.

Theorem: Rank-Nullity (Dimension Theorem)

Let $T: V \to W$ be a linear map with $V$ finite-dimensional. Then:

$$\dim(V) = \dim(\ker(T)) + \dim(\text{Im}(T))$$

Equivalently, $n = \text{nullity}(T) + \text{rank}(T)$ where $n = \dim(V)$.

Derivation 3: Proof of the Rank-Nullity Theorem

Let $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ be a basis for $\ker(T)$, where$r = \dim(\ker(T))$. Extend this to a basis for $V$:

$$\{\mathbf{u}_1, \ldots, \mathbf{u}_r, \mathbf{v}_1, \ldots, \mathbf{v}_s\}$$

where $r + s = n = \dim(V)$. We claim that $\{T(\mathbf{v}_1), \ldots, T(\mathbf{v}_s)\}$is a basis for $\text{Im}(T)$.

Spanning: Any $\mathbf{w} \in \text{Im}(T)$ equals $T(\mathbf{x})$for some $\mathbf{x} = \sum a_i \mathbf{u}_i + \sum b_j \mathbf{v}_j$. Then:

$$\mathbf{w} = T(\mathbf{x}) = \sum_{i=1}^r a_i \underbrace{T(\mathbf{u}_i)}_{= \mathbf{0}} + \sum_{j=1}^s b_j T(\mathbf{v}_j) = \sum_{j=1}^s b_j T(\mathbf{v}_j)$$

Linear independence: Suppose $\sum_{j=1}^s c_j T(\mathbf{v}_j) = \mathbf{0}$. Then $T\left(\sum c_j \mathbf{v}_j\right) = \mathbf{0}$, so$\sum c_j \mathbf{v}_j \in \ker(T)$. Writing this as$\sum c_j \mathbf{v}_j = \sum d_i \mathbf{u}_i$ gives a linear relation among basis vectors of $V$, forcing all coefficients to be zero. In particular, all $c_j = 0$.

Therefore $\dim(\text{Im}(T)) = s = n - r = \dim(V) - \dim(\ker(T))$. ∎

Consequences

If $\dim(V) = \dim(W)$, then: injective $\iff$ surjective $\iff$ bijective.
A system $A\mathbf{x} = \mathbf{b}$ has solutions iff $\mathbf{b} \in \text{Im}(A)$.
The solution set is an affine subspace of dimension $\text{nullity}(A)$.
For square matrices: $A$ invertible $\iff$ $\ker(A) = \{\mathbf{0}\}$ $\iff$ $\text{rank}(A) = n$.

2.4 Matrix Representation

Once bases are chosen for both domain and codomain, every linear map can be represented by a matrix. This is the bridge between the abstract theory of linear maps and concrete matrix computations.

Derivation 4: From Linear Map to Matrix

Let $\mathcal{B} = \{\mathbf{e}_1, \ldots, \mathbf{e}_n\}$ be a basis for $V$and $\mathcal{C} = \{\mathbf{f}_1, \ldots, \mathbf{f}_m\}$ be a basis for $W$. For each basis vector, express its image:

$$T(\mathbf{e}_j) = \sum_{i=1}^{m} a_{ij} \mathbf{f}_i$$

The matrix $A = (a_{ij})_{m \times n}$ is the matrix of $T$with respect to $\mathcal{B}$ and $\mathcal{C}$. Then for any$\mathbf{v} = \sum x_j \mathbf{e}_j$:

$$[T(\mathbf{v})]_{\mathcal{C}} = A [\mathbf{v}]_{\mathcal{B}}$$

This shows that the column $j$ of $A$ is $[T(\mathbf{e}_j)]_{\mathcal{C}}$—the coordinate vector of $T(\mathbf{e}_j)$ in the basis $\mathcal{C}$.

Derivation 5: Composition and Matrix Multiplication

If $T: V \to W$ has matrix $A$ and $S: W \to U$ has matrix $B$, then the composition $S \circ T: V \to U$ has matrix $BA$. This derivesthe formula for matrix multiplication:

$$(BA)_{ij} = \sum_{k=1}^{m} b_{ik} a_{kj}$$

Matrix multiplication is not defined arbitrarily—it is the unique definition that makes the correspondence between linear maps and matrices a functor. The fact that matrix multiplication is associative but not commutative follows directly from the corresponding properties of function composition.

2.5 The Space of Linear Maps

The set $\mathcal{L}(V, W)$ is itself a vector space under pointwise operations:

$$(S + T)(\mathbf{v}) = S(\mathbf{v}) + T(\mathbf{v}), \qquad (\alpha T)(\mathbf{v}) = \alpha \cdot T(\mathbf{v})$$

Its dimension is $\dim(\mathcal{L}(V, W)) = \dim(V) \cdot \dim(W) = nm$, which matches the number of entries in an $m \times n$ matrix. The isomorphism$\mathcal{L}(V, W) \cong \mathbb{F}^{m \times n}$ is the fundamental link between abstract linear algebra and matrix theory.

Isomorphism Theorem

All finite-dimensional vector spaces of the same dimension are isomorphic:$\dim(V) = n \implies V \cong \mathbb{F}^n$. The isomorphism is given by the coordinate map $\mathbf{v} \mapsto [\mathbf{v}]_{\mathcal{B}}$ with respect to any basis $\mathcal{B}$. This means there is essentially only one vector space of each dimension (up to isomorphism).

2.6 Historical Development

Arthur Cayley (1858)

Cayley introduced the modern notion of matrix and matrix multiplication in his Memoir on the Theory of Matrices. He showed that matrices could be treated as algebraic objects in their own right, not merely as arrays of numbers. His work laid the groundwork for representing linear maps as matrices.

Emmy Noether (1920s)

Noether revolutionized algebra by developing the abstract approach to algebraic structures. Her work on modules over rings generalized vector spaces and linear maps, establishing the conceptual framework that modern algebra uses. Her emphasis on structure-preserving maps (homomorphisms) profoundly influenced how we think about linear maps today.

John von Neumann (1930s)

Von Neumann's rigorous formulation of quantum mechanics in terms of operators on Hilbert spaces demonstrated the power of viewing physical transformations as linear maps on infinite-dimensional spaces. His Mathematical Foundations of Quantum Mechanics (1932) remains influential.

2.7 Applications

Differential Equations

The operator $L = \frac{d^2}{dx^2} + p(x)\frac{d}{dx} + q(x)$ defines a linear map on spaces of functions. The kernel of $L$ is the solution space of the homogeneous ODE$Ly = 0$, and by the rank-nullity theorem for a second-order operator, this kernel has dimension 2. The theory of linear ODEs is essentially the spectral theory of differential operators.

Image Compression

In image processing, a digital image is a matrix (a linear map from pixel coordinates to intensity values). Compression algorithms factor this matrix using low-rank approximations, effectively finding a lower-dimensional image of the original map that preserves the most important visual information. The rank of the approximation controls the compression ratio.

Control Theory

The state-space model $\dot{\mathbf{x}} = A\mathbf{x} + B\mathbf{u}$ represents a dynamical system where $A$ and $B$ are linear maps. The controllability of the system depends on the image of the controllability matrix $[B \mid AB \mid A^2B \mid \cdots]$, and observability depends on the kernel of the observability matrix.

Cryptography

Many cryptographic systems are based on linear maps over finite fields. The McEliece cryptosystem uses error-correcting codes (linear maps over $\mathbb{F}_2$), and lattice-based cryptography relies on the difficulty of solving approximate closest vector problems in high-dimensional lattices, which are subgroups of $\mathbb{Z}^n$.

2.8 Computational Exploration

The following simulation verifies linearity of matrix-vector multiplication, computes kernels and images via SVD, demonstrates the rank-nullity theorem across various matrix sizes, and visualizes how linear maps transform geometric objects.

Linear Maps: Kernel, Image, and Rank-Nullity

Python

linear_maps.py200 lines

import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

# ============================================================
# Linear Maps: Kernel, Image, and Rank-Nullity Theorem
# ============================================================

# --- 1. Verify linearity of a map ---
print("=" * 60)
print("LINEARITY VERIFICATION")
print("=" * 60)

# Define a linear map T: R^3 -> R^2
A = np.array([[1, 2, 3],
              [4, 5, 6]], dtype=float)

def T(x):
    return A @ x

u = np.array([1.0, -2.0, 3.0])
v = np.array([4.0, 0.5, -1.0])
alpha = 2.7

# Check T(alpha*u + v) = alpha*T(u) + T(v)
lhs = T(alpha * u + v)
rhs = alpha * T(u) + T(v)
print(f"T(alpha*u + v) = {lhs}")
print(f"alpha*T(u) + T(v) = {rhs}")
print(f"Linearity holds: {np.allclose(lhs, rhs)}")

# --- 2. Kernel (Null Space) computation ---
print()
print("=" * 60)
print("KERNEL (NULL SPACE)")
print("=" * 60)

B = np.array([[1, 2, 3, 4],
              [2, 4, 6, 8],
              [1, 3, 5, 7]], dtype=float)

# Compute null space via SVD
U_mat, s, Vt = np.linalg.svd(B)
tol = 1e-10
null_mask = s < tol
# Also check remaining singular values
rank_B = np.sum(s > tol)
null_dim = B.shape[1] - rank_B

print(f"Matrix B (3x4):")
print(B)
print(f"Singular values: {s}")
print(f"Rank: {rank_B}")
print(f"Nullity: {null_dim}")

# Extract null space vectors
null_space = Vt[rank_B:].T
print(f"Null space basis vectors (columns):")
print(null_space)

# Verify: B @ null_vector = 0
for i in range(null_space.shape[1]):
    nv = null_space[:, i]
    print(f"  B @ null_vec_{i+1} = {B @ nv} (should be ~zero)")

# --- 3. Image (Column Space) ---
print()
print("=" * 60)
print("IMAGE (COLUMN SPACE)")
print("=" * 60)

# Image = column space of B
# Extract basis for column space from SVD
col_space = U_mat[:, :rank_B]
print(f"Column space basis (orthonormal):")
print(col_space)
print(f"Dimension of image: {rank_B}")

# --- 4. Rank-Nullity Theorem verification ---
print()
print("=" * 60)
print("RANK-NULLITY THEOREM")
print("=" * 60)

matrices = [
    ("2x3", np.array([[1, 2, 3], [4, 5, 6]], dtype=float)),
    ("3x3", np.array([[1, 0, 0], [0, 1, 0], [0, 0, 0]], dtype=float)),
    ("4x3", np.array([[1, 2, 0], [0, 1, 1], [1, 3, 1], [2, 5, 1]], dtype=float)),
    ("3x5", np.random.randn(3, 5)),
]

for name, M in matrices:
    r = np.linalg.matrix_rank(M)
    n = M.shape[1]  # domain dimension
    nullity = n - r
    print(f"  {name} matrix: rank={r}, nullity={nullity}, "
          f"rank+nullity={r + nullity}, domain dim={n}, "
          f"Theorem holds: {r + nullity == n}")

# --- 5. Matrix representation of linear maps ---
print()
print("=" * 60)
print("MATRIX REPRESENTATION")
print("=" * 60)

# Differentiation on P_3 (polynomials of degree <= 3)
# Basis: {1, x, x^2, x^3}
# D(1) = 0, D(x) = 1, D(x^2) = 2x, D(x^3) = 3x^2
D = np.array([[0, 1, 0, 0],
              [0, 0, 2, 0],
              [0, 0, 0, 3],
              [0, 0, 0, 0]], dtype=float)

print("Differentiation operator on P_3:")
print(D)
print(f"Rank of D: {np.linalg.matrix_rank(D)}")
print(f"Kernel of D: polynomials of degree 0 (constants)")

# D^2 (second derivative)
D2 = D @ D
print(f"D^2 (second derivative):")
print(D2)

# D^4 = 0 (nilpotent)
D4 = np.linalg.matrix_power(D, 4)
print(f"D^4 (should be zero): {np.allclose(D4, 0)}")

# --- 6. Visualization ---
fig, axes = plt.subplots(1, 3, figsize=(16, 5))

# Plot 1: Linear map as geometric transformation
ax = axes[0]
theta = np.linspace(0, 2 * np.pi, 100)
circle_x = np.cos(theta)
circle_y = np.sin(theta)
circle = np.vstack([circle_x, circle_y])

# Transformation matrix
T_mat = np.array([[2, 1], [0.5, 1.5]])
transformed = T_mat @ circle

ax.plot(circle_x, circle_y, color="#3b82f6", linewidth=2, label="Unit circle")
ax.plot(transformed[0], transformed[1], color="#0ea5e9", linewidth=2, label="T(circle)")
ax.set_aspect("equal")
ax.grid(True, alpha=0.3)
ax.legend(fontsize=9)
ax.set_title("Linear Map as Transformation", fontsize=12, fontweight="bold")
ax.set_facecolor("#0f172a")
ax.set_xlim(-4, 4)
ax.set_ylim(-3, 3)

# Plot 2: Rank-nullity bar chart
ax = axes[1]
dims = [3, 4, 5, 6, 7, 8]
ranks = []
nullities = []
for d in dims:
    M_rand = np.random.randn(3, d)
    r = np.linalg.matrix_rank(M_rand)
    ranks.append(r)
    nullities.append(d - r)

x_pos = np.arange(len(dims))
bars1 = ax.bar(x_pos - 0.15, ranks, 0.3, color="#3b82f6", label="Rank")
bars2 = ax.bar(x_pos + 0.15, nullities, 0.3, color="#38bdf8", label="Nullity")
ax.set_xticks(x_pos)
ax.set_xticklabels([f"3x{d}" for d in dims])
ax.set_xlabel("Matrix Size", fontsize=11)
ax.set_ylabel("Dimension", fontsize=11)
ax.set_title("Rank-Nullity Theorem", fontsize=12, fontweight="bold")
ax.legend(fontsize=9)
ax.set_facecolor("#0f172a")

# Plot 3: Kernel and image of a projection
ax = axes[2]
# Projection onto x-axis in R^2
proj = np.array([[1, 0], [0, 0]], dtype=float)
n_points = 200
points = np.random.randn(2, n_points) * 1.5
projected = proj @ points

ax.scatter(points[0], points[1], c="#3b82f6", alpha=0.3, s=10, label="Original")
ax.scatter(projected[0], projected[1], c="#0ea5e9", alpha=0.7, s=15, label="Projected")
ax.axhline(y=0, color="#38bdf8", linewidth=2, linestyle="--", alpha=0.8)
ax.axvline(x=0, color="#f87171", linewidth=2, linestyle="--", alpha=0.5, label="Kernel direction")
ax.set_aspect("equal")
ax.grid(True, alpha=0.3)
ax.legend(fontsize=9)
ax.set_title("Projection: Kernel and Image", fontsize=12, fontweight="bold")
ax.set_facecolor("#0f172a")
ax.set_xlim(-4, 4)
ax.set_ylim(-4, 4)

plt.tight_layout()
plt.savefig("output.png", dpi=150, bbox_inches="tight",
            facecolor="#0f172a", edgecolor="none")
plt.show()
print("\nPlot saved: Linear maps visualizations")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Vector Spaces Matrices & Determinants →