Linear Maps, Kernel and Image (the Rank-Nullity Theorem)

A linear map is a function between vector spaces that respects the only structure vector spaces have: addition and scalar multiplication. This chapter develops the two subspaces every linear map carries with it — the kernel (what collapses to zero) and the image (what is actually reached) — and proves the single theorem that relates their sizes to the size of the domain: the rank-nullity theorem. This is arguably the most-used theorem in the entire course.

Have to hand: basis, dimension, and the exchange lemma (Chapter 3); comfort with the "extend a basis" technique.

1. Linear Maps

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

1. $T(u+v) = T(u)+T(v)$ (additivity);
2. $T(av) = aT(v)$ (homogeneity).

Equivalently, a single condition: $T(au+bv) = aT(u)+bT(v)$ for all scalars $a,b$ and vectors $u,v$ (take $a=b=1$ for additivity, $b=0$ for homogeneity, and conversely combine the two).

Immediate consequence. $T(0_V) = 0_W$ for any linear map. Proof: $T(0_V) = T(0\cdot 0_V) = 0\cdot T(0_V) = 0_W$, using homogeneity and the Chapter 1 theorem $0\cdot w = 0$. (So a map with $T(0)\ne0$ — e.g. $T(x)=x+1$ — is never linear, however simple it looks.)

Examples. $T:\mathbb{R}^3\to\mathbb{R}^2$, $T(x,y,z)=(x+y,\,2z)$ is linear (check both conditions directly on components). $T:\mathcal{P}_n(\mathbb{R})\to\mathcal{P}_{n-1}(\mathbb{R})$, $T(p)=p'$ (differentiation) is linear, by the sum and constant-multiple rules of calculus. $T(x,y)=(x^2,y)$ is not linear: $T(1,0)+T(1,0)=(1,0)+(1,0)=(2,0)$, but $T(2,0)=(4,0)\ne(2,0)$, so additivity fails.

Theorem (linear maps are determined by their action on a basis). Let $v_1,\dots,v_n$ be a basis of $V$, and let $w_1,\dots,w_n \in W$ be arbitrary vectors. Then there exists a unique linear map $T:V\to W$ with $T(v_i)=w_i$ for every $i$.

Proof. Existence. Every $v\in V$ has a unique representation $v=a_1v_1+\cdots+a_nv_n$ (Chapter 3). Define $T(v):=a_1w_1+\cdots+a_nw_n$. This is well-defined precisely because the $a_i$ are unique. Linearity: if $v=\sum a_iv_i$, $v'=\sum a_i'v_i$, then $v+v'=\sum(a_i+a_i')v_i$ (uniqueness of coordinates of a sum, since this is a representation and representations are unique), so $T(v+v')=\sum(a_i+a_i')w_i = \sum a_iw_i+\sum a_i'w_i = T(v)+T(v')$; homogeneity is similar. Uniqueness. If $T,T'$ both satisfy $T(v_i)=T'(v_i)=w_i$, then for any $v=\sum a_iv_i$, linearity forces $T(v)=\sum a_iT(v_i)=\sum a_iw_i = \sum a_iT'(v_i) = T'(v)$, so $T=T'$. $\blacksquare$

This theorem is the reason a linear map can be fully specified by a finite table of data (its values on a basis) — and is exactly why a linear map between finite-dimensional spaces can be recorded as a matrix (Chapter 5).

2. Kernel and Image

Definition. For a linear map $T:V\to W$: the kernel is $\ker T := \{v\in V : T(v)=0_W\}$; the image is $\operatorname{im} T := \{T(v) : v\in V\} \subseteq W$.

Proposition. $\ker T$ is a subspace of $V$, and $\operatorname{im} T$ is a subspace of $W$.

Proof. Kernel. $0_V\in\ker T$ since $T(0_V)=0_W$. If $u,v\in\ker T$ and $a,b\in\mathbb{F}$, then $T(au+bv)=aT(u)+bT(v)=a\cdot0+b\cdot0=0$, so $au+bv\in\ker T$: closed under linear combinations, hence a subspace (Chapter 2's combined test). Image. $0_W=T(0_V)\in\operatorname{im}T$. If $w_1=T(v_1), w_2=T(v_2)\in\operatorname{im}T$ and $a,b\in\mathbb{F}$, then $aw_1+bw_2 = aT(v_1)+bT(v_2)=T(av_1+bv_2)\in\operatorname{im}T$, since $av_1+bv_2\in V$. $\blacksquare$

The kernel is exactly the (homogeneous) solution set of "$T(v)=0$" met already in Chapter 2 and 3's examples — this chapter identifies that solution set as the kernel of a specific linear map, explaining why it was always a subspace.

3. Injectivity and the Kernel

Theorem. $T$ is injective if and only if $\ker T = \{0\}$.

Proof. ($\Rightarrow$) If $T$ is injective and $v\in\ker T$, then $T(v)=0=T(0)$, so injectivity forces $v=0$. ($\Leftarrow$) Suppose $\ker T=\{0\}$ and $T(u)=T(v)$. Then $T(u-v)=T(u)-T(v)=0$ (using linearity: $T(u)+T(-v)=T(u)-T(v)$, since $T(-v)=T((-1)v)=(-1)T(v)=-T(v)$), so $u-v\in\ker T=\{0\}$, giving $u=v$. $\blacksquare$

This is one of the most useful facts in the course: to check injectivity of a linear map, you never need to compare two arbitrary potentially-different inputs — it suffices to solve the single equation $T(v)=0$ and check only the trivial solution occurs.

4. The Rank-Nullity Theorem

Definition. For $T:V\to W$ with $V$ finite-dimensional, the rank is $\operatorname{rank}(T):=\dim(\operatorname{im}T)$ and the nullity is $\operatorname{nullity}(T):=\dim(\ker T)$.

Theorem (Rank-Nullity). If $V$ is finite-dimensional and $T:V\to W$ is linear, then $\dim V = \operatorname{rank}(T) + \operatorname{nullity}(T).$

Proof. Let $u_1,\dots,u_k$ be a basis of $\ker T$ (a subspace of the finite-dimensional $V$, hence finite-dimensional itself, Chapter 3). Extend it to a basis $u_1,\dots,u_k,v_1,\dots,v_m$ of $V$ (extension theorem, Chapter 3), so $\dim V = k+m$. It remains to show $\operatorname{rank}(T)=m$, i.e. that $T(v_1),\dots,T(v_m)$ is a basis of $\operatorname{im}T$.

Spans $\operatorname{im}T$. Any $w=T(v)\in\operatorname{im}T$ has $v=\sum_{i=1}^k a_iu_i + \sum_{j=1}^m b_jv_j$ (basis representation), so $w=T(v)=\sum a_iT(u_i) + \sum b_jT(v_j) = \sum b_jT(v_j)$, since $T(u_i)=0$ ($u_i\in\ker T$). So $T(v_1),\dots,T(v_m)$ spans $\operatorname{im}T$.

Independent. Suppose $\sum_{j=1}^m c_jT(v_j)=0$. By linearity, $T\!\left(\sum c_jv_j\right)=0$, so $\sum c_jv_j \in\ker T$, hence $\sum c_jv_j = \sum d_iu_i$ for some scalars $d_i$ (basis of the kernel). Rearranging, $\sum c_jv_j - \sum d_iu_i = 0$; but $u_1,\dots,u_k,v_1,\dots,v_m$ is independent (it's a basis of $V$), so every coefficient is $0$ — in particular every $c_j=0$.

So $T(v_1),\dots,T(v_m)$ is a basis of $\operatorname{im}T$, giving $\operatorname{rank}(T)=m = \dim V - k = \dim V - \operatorname{nullity}(T)$. $\blacksquare$

Worked example. $T:\mathbb{R}^3\to\mathbb{R}^2$, $T(x,y,z)=(x+y, y+z)$. Find $\ker T$: $x+y=0, y+z=0 \Rightarrow x=-y, z=-y$, so $\ker T = \{(-y,y,-y) : y\in\mathbb{R}\} = \operatorname{span}((-1,1,-1))$, giving $\operatorname{nullity}(T)=1$. By rank-nullity, $\operatorname{rank}(T) = 3-1=2$; since $\operatorname{im}T\subseteq\mathbb{R}^2$ and $\dim\mathbb{R}^2=2$, the equality case of Chapter 3's subspace proposition gives $\operatorname{im}T=\mathbb{R}^2$ — $T$ is surjective, confirmed without checking a single output vector by hand.

5. Consequences for Injectivity and Surjectivity

Corollary. If $\dim V > \dim W$, no linear map $T:V\to W$ can be injective.

Proof. $\operatorname{rank}(T) = \dim(\operatorname{im}T) \le \dim W$ (subspace dimension bound, Chapter 3). By rank-nullity, $\operatorname{nullity}(T) = \dim V - \operatorname{rank}(T) \ge \dim V - \dim W > 0$, so $\ker T \ne \{0\}$, and $T$ is not injective by Section 3. $\blacksquare$

Corollary. If $\dim V < \dim W$, no linear map $T:V\to W$ can be surjective.

Proof. $\operatorname{rank}(T)\le\dim V < \dim W$ (rank-nullity gives $\operatorname{rank}(T)=\dim V - \operatorname{nullity}(T)\le\dim V$), so $\operatorname{im}T$ is a proper subspace of $W$ (strictly smaller dimension), hence $\operatorname{im}T\ne W$. $\blacksquare$

Corollary. If $\dim V = \dim W$ (both finite), then $T$ is injective if and only if it is surjective.

Proof. $T$ injective $\iff$ $\operatorname{nullity}(T)=0$ $\iff$ $\operatorname{rank}(T)=\dim V=\dim W$ (rank-nullity) $\iff$ $\operatorname{im}T=W$ (equality case, Chapter 3) $\iff$ $T$ surjective. $\blacksquare$

This last corollary is used constantly: for a square linear system or a map between equal-dimensional spaces, injectivity and surjectivity are not independent properties to check — proving one gives the other for free.

Common Exam Pitfalls

• Checking additivity and homogeneity on only specific numbers. Linearity must hold for all $u,v,a$; a map can satisfy it for particular values while failing in general ($T(0)=0$ is necessary but never sufficient to prove linearity).
• Confusing kernel (a subset of the domain $V$) with image (a subset of the codomain $W$). They live in different spaces whenever $V\ne W$, and rank-nullity relates their dimensions, not the sets themselves.
• Forgetting $\ker T=\{0\}$ only shows injectivity, not surjectivity, and vice versa — the two are linked only via rank-nullity and only when $\dim V=\dim W$.
• Misapplying rank-nullity to infinite-dimensional domains. The theorem as proved here requires $V$ finite-dimensional (so that a basis of the kernel can be extended to a finite basis of $V$).
• Assuming any $n$-vectors-to-$n$-vectors map between equal dimensions is automatically bijective. It is only guaranteed if it is already known to be linear — the equivalence of injective/surjective is a theorem about linear maps specifically, not an arbitrary function.
• Sign or arithmetic slips when solving $T(v)=0$ for the kernel. Since nullity is read off this computation, an error here corrupts the rank-nullity count entirely; always double-check by substituting the kernel basis back into $T$.

Summary

• Linear map: $T(au+bv)=aT(u)+bT(v)$ for all scalars and vectors; forces $T(0)=0$.
• A linear map is completely and uniquely determined by its values on a basis of the domain.
• Kernel $\ker T=\{v:T(v)=0\}$ and image $\operatorname{im}T=\{T(v)\}$ are always subspaces (of $V$ and $W$ respectively).
• Injective $\iff \ker T=\{0\}$ — reduces checking injectivity to solving one equation.
• Rank-nullity theorem: $\dim V = \operatorname{rank}(T)+\operatorname{nullity}(T)$, proved by extending a kernel basis to a basis of $V$ and showing the extension maps to a basis of the image.
• Consequences: $\dim V>\dim W \Rightarrow$ never injective; $\dim V<\dim W \Rightarrow$ never surjective; $\dim V=\dim W \Rightarrow$ injective $\iff$ surjective.