Linear Algebra — 02 · Vector Spaces, Subspaces, Basis and Dimension

Linear Algebra 00 and 01 worked with columns of numbers. This post asks what those columns have in common with polynomials, functions, matrices and the solutions of a differential equation — and answers with one definition: a vector space. From that definition come the ideas that organise the rest of the subject: subspaces, span, linear independence, basis and dimension. The central theorem is that dimension is well defined — every basis of a space has the same size — and it is proved here in full through the Steinitz exchange lemma. The abstract ideas are then brought back to matrices through Strang's four fundamental subspaces, with a complete worked example, a proof that row rank equals column rank, and the rank–nullity theorem in matrix form. The post ends with sums and direct sums of subspaces and the formula $\dim(U + W) = \dim U + \dim W - \dim(U \cap W)$.

Series map: 00 Vectors & Linear Systems → 01 Matrix Algebra, Inverses & LU → 02 Vector Spaces, Basis & Dimension (this post) → 03 Linear Maps, Change of Basis & Determinants → 04 Eigenvalues & Diagonalization → 05 Inner Products, Spectral Theorem & SVD.

---

Learning Outcome

• State the axioms of a vector space over a field, and check them for $F^n$, polynomials, functions and matrices.
• Prove simple consequences of the axioms, such as $0\mathbf{v} = \mathbf{0}$ and $(-1)\mathbf{v} = -\mathbf{v}$.
• Use the subspace test, and recognise common subspaces and non-subspaces.
• Work with span and linear independence in any vector space, including the linear dependence lemma.
• Prove the Steinitz exchange lemma and deduce that dimension is well defined.
• Extend an independent list to a basis, shrink a spanning list to a basis, and compute coordinates.
• Find bases and dimensions of the four fundamental subspaces of a matrix from its RREF.
• Prove that row rank equals column rank and that $\operatorname{rank} A + \dim N(A) = n$.
• Work with sums and direct sums, and prove the dimension formula for $U + W$.

---

Chapter 1 — Fields and vector spaces

Terminology

• Field — a set $F$ with an addition and a multiplication that satisfy the usual rules of arithmetic: both operations are associative and commutative, multiplication distributes over addition, there are elements $0 \neq 1$ with $a + 0 = a$ and $1a = a$, every $a$ has a negative $-a$, and every nonzero $a$ has an inverse $a^{-1}$. Examples: $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, and $\mathbb{F}_2 = \{0, 1\}$ with arithmetic mod 2. The integers $\mathbb{Z}$ are not a field ($2$ has no integer inverse).
• Scalars — the elements of the field. In this series $F$ is $\mathbb{R}$ or $\mathbb{C}$ unless stated.

Everything in Linear Algebra 00 and 01 — elimination, pivots, inverses, LU — used only these field rules, so it works word for word over any field.

The definition

A vector space over $F$ is a set $V$ with an addition $V \times V \to V$ and a scalar multiplication $F \times V \to V$ such that, for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ and $a, b \in F$:

1. $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ (commutativity).
2. $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ (associativity).
3. There is an element $\mathbf{0} \in V$ with $\mathbf{v} + \mathbf{0} = \mathbf{v}$ for all $\mathbf{v}$ (additive identity).
4. For each $\mathbf{v}$ there is $\mathbf{w}$ with $\mathbf{v} + \mathbf{w} = \mathbf{0}$ (additive inverse).
5. $a(b\mathbf{v}) = (ab)\mathbf{v}$.
6. $1\mathbf{v} = \mathbf{v}$.
7. $a(\mathbf{u} + \mathbf{v}) = a\mathbf{u} + a\mathbf{v}$.
8. $(a + b)\mathbf{v} = a\mathbf{v} + b\mathbf{v}$.

The elements of $V$ are called vectors, whatever they actually are.

First consequences

Proposition. In any vector space: (a) the zero vector is unique; (b) each $\mathbf{v}$ has exactly one additive inverse, written $-\mathbf{v}$; (c) $0\mathbf{v} = \mathbf{0}$; (d) $a\mathbf{0} = \mathbf{0}$; (e) $(-1)\mathbf{v} = -\mathbf{v}$.

Proof. (a) If $\mathbf{0}$ and $\mathbf{0}'$ are both identities, $\mathbf{0} = \mathbf{0} + \mathbf{0}' = \mathbf{0}'$. (b) If $\mathbf{w}, \mathbf{w}'$ are both inverses of $\mathbf{v}$, then $\mathbf{w} = \mathbf{w} + (\mathbf{v} + \mathbf{w}') = (\mathbf{w} + \mathbf{v}) + \mathbf{w}' = \mathbf{w}'$. (c) $0\mathbf{v} = (0 + 0)\mathbf{v} = 0\mathbf{v} + 0\mathbf{v}$; add $-(0\mathbf{v})$ to both sides. (d) The same with $a\mathbf{0} = a(\mathbf{0} + \mathbf{0})$. (e) $\mathbf{v} + (-1)\mathbf{v} = (1 + (-1))\mathbf{v} = 0\mathbf{v} = \mathbf{0}$, so $(-1)\mathbf{v}$ is the inverse of $\mathbf{v}$, by (b). $\blacksquare$

Examples

Space	Vectors	Operations
$F^n$	columns $(x_1, \dots, x_n)$	entry by entry
$\mathcal{P}_n(F)$	polynomials of degree at most $n$	add coefficients; scale coefficients
$\mathcal{P}(F)$	all polynomials	same
$F^S$	all functions $f : S \to F$ on a set $S$	$(f + g)(s) = f(s) + g(s)$, $(af)(s) = a f(s)$
$C[a, b]$	continuous real functions on $[a, b]$	pointwise
$M_{m \times n}(F)$	$m \times n$ matrices	entry by entry

$F^n$ is really the special case $F^S$ with $S = \{1, \dots, n\}$: a column is a function from positions to numbers.

Non-examples. The first quadrant $\{(x, y) : x, y \ge 0\}$ fails axiom 4 — $(1, 0)$ has no inverse inside it. The line $\{(x, y) : y = x + 1\}$ has no zero vector. The polynomials of degree exactly 2 are not closed under addition: $(t^2 + t) + (-t^2) = t$.

---

Chapter 2 — Subspaces

Terminology

• Subspace — a subset $U \subseteq V$ that is itself a vector space with the same addition and scalar multiplication.

Theorem (subspace test). A subset $U$ of a vector space $V$ is a subspace if and only if

1. $\mathbf{0} \in U$;
2. $\mathbf{u}, \mathbf{w} \in U \Rightarrow \mathbf{u} + \mathbf{w} \in U$ (closed under addition);
3. $a \in F$, $\mathbf{u} \in U \Rightarrow a\mathbf{u} \in U$ (closed under scalar multiplication).

Proof. A subspace clearly satisfies 2 and 3, and it contains its own zero vector $\mathbf{z}$ with $\mathbf{z} + \mathbf{z} = \mathbf{z}$; adding $-\mathbf{z}$ in $V$ shows $\mathbf{z} = \mathbf{0}$, so 1 holds. Conversely, suppose 1–3 hold. Conditions 2 and 3 make addition and scalar multiplication land in $U$. Axioms 1, 2, 5–8 are identities that hold for all vectors of $V$, so in particular for those of $U$. Axiom 3 holds by condition 1. For axiom 4: if $\mathbf{u} \in U$ then $-\mathbf{u} = (-1)\mathbf{u} \in U$ by condition 3 and part (e) of the proposition. $\blacksquare$

Trick: conditions 2 and 3 together are the same as "closed under linear combinations": $a\mathbf{u} + b\mathbf{w} \in U$ for all $\mathbf{u}, \mathbf{w} \in U$ and scalars $a, b$. Check $\mathbf{0}$ first — it is the fastest way to reject a non-subspace.

Examples and non-examples

• Null space $N(A) = \{\mathbf{x} \in F^n : A\mathbf{x} = \mathbf{0}\}$ is a subspace of $F^n$: $A\mathbf{0} = \mathbf{0}$, and $A(a\mathbf{u} + b\mathbf{w}) = aA\mathbf{u} + bA\mathbf{w} = \mathbf{0}$.
• Column space $C(A) = \{A\mathbf{x} : \mathbf{x} \in F^n\}$, the span of the columns, is a subspace of $F^m$.
• $\{p \in \mathcal{P}_2(\mathbb{R}) : p(1) = 0\}$ is a subspace; $\{p : p(1) = 5\}$ is not (no zero polynomial).
• The symmetric $n \times n$ matrices form a subspace of $M_{n \times n}$.
• The solutions $y$ of $y'' + y = 0$ form a subspace of the twice-differentiable functions $\mathbb{R} \to \mathbb{R}$.
• The solutions of $A\mathbf{x} = \mathbf{b}$ with $\mathbf{b} \neq \mathbf{0}$ are not a subspace (Linear Algebra 00, Chapter 7): $\mathbf{0}$ is not a solution.
• The union of the $x$-axis and the $y$-axis in $\mathbb{R}^2$ is not a subspace: $(1, 0) + (0, 1) = (1, 1)$ is in neither.

Intersections are subspaces. If $U$ and $W$ are subspaces, so is $U \cap W$: it contains $\mathbf{0}$, and a linear combination of vectors in both lies in both. Unions usually are not, as the axes show; Chapter 8 replaces the union by the sum $U + W$.

---

Chapter 3 — Span and linear independence in general

The definitions from Linear Algebra 00 carry over unchanged. For a finite list $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $V$:

• $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is the set of all linear combinations $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k$. By convention the span of the empty list is $\{\mathbf{0}\}$.
• The list spans $V$ if its span is all of $V$.
• The list is linearly independent if $a_1\mathbf{v}_1 + \dots + a_k\mathbf{v}_k = \mathbf{0}$ forces $a_1 = \dots = a_k = 0$; otherwise it is dependent. The empty list is independent.

Proposition. $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is the smallest subspace of $V$ containing every $\mathbf{v}_i$.

Proof. It contains $\mathbf{0}$, and a combination of combinations is a combination, so it is a subspace; it contains each $\mathbf{v}_i$. Any subspace containing all $\mathbf{v}_i$ is closed under linear combinations, so it contains the span. $\blacksquare$

The linear dependence lemma

Lemma. If $\mathbf{v}_1, \dots, \mathbf{v}_m$ is linearly dependent, then there is an index $j$ such that

1. $\mathbf{v}_j \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{j-1})$, and
2. removing $\mathbf{v}_j$ from the list does not change its span.

Proof. Take a relation $a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m = \mathbf{0}$ with not all $a_i = 0$, and let $j$ be the largest index with $a_j \neq 0$. Then

$$\mathbf{v}_j = -\frac{a_1}{a_j}\mathbf{v}_1 - \dots - \frac{a_{j-1}}{a_j}\mathbf{v}_{j-1},$$

which proves 1. (If $j = 1$ this says $\mathbf{v}_1 = \mathbf{0}$, the span of the empty list.) For 2, in any combination of the full list, replace $\mathbf{v}_j$ by the right-hand side above; the result is a combination of the list without $\mathbf{v}_j$. $\blacksquare$

Independence outside Fⁿ

• In $\mathcal{P}_2(\mathbb{R})$, the list $1, t, t^2$ is independent: if $a + bt + ct^2$ is the zero polynomial, all its coefficients are 0.
• In the functions $\mathbb{R} \to \mathbb{R}$, $\sin$ and $\cos$ are independent: if $a\sin x + b\cos x = 0$ for all $x$, then $x = 0$ gives $b = 0$ and $x = \pi/2$ gives $a = 0$.

Common pitfall: "$a\sin x + b\cos x = 0$" means equality as functions, for every $x$. Finding one $x$ where a combination is zero proves nothing; you must show the combination is zero everywhere only when all weights are zero.

---

Chapter 4 — Basis, the exchange lemma and dimension

Terminology

• Basis of $V$ — a list of vectors in $V$ that is linearly independent and spans $V$.
• Finite-dimensional — $V$ is spanned by some finite list. Otherwise infinite-dimensional.
• Standard basis of $F^n$ — $\mathbf{e}_1, \dots, \mathbf{e}_n$. Of $\mathcal{P}_n(F)$ — $1, t, \dots, t^n$.

Theorem (unique representation). A list $\mathbf{v}_1, \dots, \mathbf{v}_n$ is a basis of $V$ if and only if every $\mathbf{v} \in V$ can be written as $a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$ in exactly one way.

Proof. Spanning is "at least one way". If a basis gave two ways, subtracting them gives $\sum (a_i - b_i)\mathbf{v}_i = \mathbf{0}$, so every $a_i = b_i$ by independence. Conversely, uniqueness for $\mathbf{v} = \mathbf{0}$ (which is $0\mathbf{v}_1 + \dots + 0\mathbf{v}_n$) is exactly independence. $\blacksquare$

The Steinitz exchange lemma

Lemma (Steinitz exchange). Let $V$ be a vector space. Suppose $\mathbf{u}_1, \dots, \mathbf{u}_m$ is linearly independent in $V$ and $\mathbf{w}_1, \dots, \mathbf{w}_n$ spans $V$. Then $m \le n$. Moreover, after renumbering the $\mathbf{w}$'s, the list

$$\mathbf{u}_1, \dots, \mathbf{u}_m, \mathbf{w}_{m+1}, \dots, \mathbf{w}_n$$

also spans $V$.

Proof. We show by induction on $k = 0, 1, \dots, m$ that $k \le n$ and that, after renumbering, $\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_{k+1}, \dots, \mathbf{w}_n$ spans $V$. For $k = 0$ this is the hypothesis.

Assume it holds for some $k < m$. Since the list $\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_{k+1}, \dots, \mathbf{w}_n$ spans $V$, we can write

$$\mathbf{u}_{k+1} = a_1\mathbf{u}_1 + \dots + a_k\mathbf{u}_k + b_{k+1}\mathbf{w}_{k+1} + \dots + b_n\mathbf{w}_n.$$

If every $b_j$ were 0 (in particular, if no $\mathbf{w}$'s were left, $k = n$), then $\mathbf{u}_{k+1}$ would be a combination of $\mathbf{u}_1, \dots, \mathbf{u}_k$, contradicting independence of the $\mathbf{u}$'s. So some $b_j \neq 0$; hence $k + 1 \le n$. Renumber so that $b_{k+1} \neq 0$ and solve for $\mathbf{w}_{k+1}$:

$$\mathbf{w}_{k+1} = \frac{1}{b_{k+1}}\Bigl(\mathbf{u}_{k+1} - \sum_{i=1}^{k} a_i\mathbf{u}_i - \sum_{j=k+2}^{n} b_j\mathbf{w}_j\Bigr).$$

So $\mathbf{w}_{k+1}$ lies in the span of $\mathbf{u}_1, \dots, \mathbf{u}_{k+1}, \mathbf{w}_{k+2}, \dots, \mathbf{w}_n$. That span therefore contains the whole old spanning list, so it is $V$. This completes the step. At $k = m$ we get $m \le n$ and the stated spanning list. $\blacksquare$

Small example. In $\mathbb{R}^3$ take the independent $\mathbf{u}_1 = (1, 1, 0)$, $\mathbf{u}_2 = (0, 1, 1)$ and the spanning $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$. Since $\mathbf{u}_1 = \mathbf{e}_1 + \mathbf{e}_2$ has a nonzero coefficient on $\mathbf{e}_1$, swap it out: $\mathbf{u}_1, \mathbf{e}_2, \mathbf{e}_3$ spans. Then $\mathbf{u}_2 = 0\,\mathbf{u}_1 + \mathbf{e}_2 + \mathbf{e}_3$; swap out $\mathbf{e}_2$: $\mathbf{u}_1, \mathbf{u}_2, \mathbf{e}_3$ spans $\mathbb{R}^3$. (Three vectors that span $\mathbb{R}^3$ are automatically a basis — see the theorem at the end of this chapter.)

Dimension is well defined

Theorem. In a finite-dimensional vector space, any two bases have the same length.

Proof. Let $B_1$ and $B_2$ be bases, of lengths $m$ and $n$. $B_1$ is independent and $B_2$ spans, so $m \le n$ by Steinitz. Swap roles: $n \le m$. $\blacksquare$

This common length is the dimension $\dim V$.

Space	Dimension	A basis
$\{\mathbf{0}\}$	0	the empty list
$F^n$	$n$	$\mathbf{e}_1, \dots, \mathbf{e}_n$
$\mathcal{P}_n(F)$	$n + 1$	$1, t, \dots, t^n$
$M_{m \times n}(F)$	$mn$	matrices with one entry 1, the rest 0
symmetric $2 \times 2$	3	one basis matrix each for the (1,1), (2,2) and paired off-diagonal entries
$\mathcal{P}(F)$	infinite	$1, t, t^2, \dots$ (no finite list spans)

Watch out: $\mathbb{C}^n$ has dimension $n$ over $\mathbb{C}$ but $2n$ over $\mathbb{R}$ (a basis over $\mathbb{R}$ is $\mathbf{e}_1, i\mathbf{e}_1, \dots, \mathbf{e}_n, i\mathbf{e}_n$). Dimension depends on the field of scalars.

Growing and shrinking to a basis

Theorem. Let $V$ be finite-dimensional with $\dim V = n$.

1. Every spanning list can be shrunk to a basis by removing vectors.
2. Every independent list can be extended to a basis by adding vectors.
3. Any $n$ independent vectors form a basis; any $n$ spanning vectors form a basis.
4. Every subspace $U$ is finite-dimensional with $\dim U \le n$, and $\dim U = n$ only if $U = V$.

Proof. (1) While the list is dependent, the dependence lemma lets you remove one vector without changing the span. The process stops at an independent spanning list. (2) Apply Steinitz with a basis as the spanning list: the independent list plus the remaining $n - m$ basis vectors spans $V$; it has length $n$, and by (1) some sublist is a basis, which must have length $n$, so it is the whole list. (3) An independent list of length $n$ extends to a basis of length $n$, so nothing is added; a spanning list of length $n$ shrinks to a basis of length $n$, so nothing is removed. (4) Any independent list in $U$ is independent in $V$, so it has length at most $n$ by Steinitz. Keep adding vectors of $U$ not yet in the span of an independent list (independence is kept, by Exercise 7); this stops after at most $n$ steps with a basis of $U$. If $\dim U = n$, that basis is $n$ independent vectors of $V$, so by (3) it spans $V$, hence $U = V$. $\blacksquare$

---

Chapter 5 — Coordinates

If $B = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ is a basis of $V$, each $\mathbf{v}$ has unique weights with $\mathbf{v} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$. The column $[\mathbf{v}]_B = (a_1, \dots, a_n) \in F^n$ is the coordinate vector of $\mathbf{v}$ relative to $B$.

The map $\mathbf{v} \mapsto [\mathbf{v}]_B$ is one-to-one, onto $F^n$, and respects linear combinations: $[a\mathbf{u} + b\mathbf{w}]_B = a[\mathbf{u}]_B + b[\mathbf{w}]_B$. So every $n$-dimensional space over $F$ behaves exactly like $F^n$, and computations in it can be done with columns and matrices. Linear Algebra 03 makes this precise (isomorphism) and studies how coordinates change when the basis changes.

Example in $\mathbb{R}^2$. With $B = ((1, 1), (1, -1))$ and $\mathbf{x} = (3, 1)$: solve $a(1,1) + b(1,-1) = (3, 1)$, so $a + b = 3$, $a - b = 1$, giving $a = 2$, $b = 1$. So $[\mathbf{x}]_B = (2, 1)$, while the standard coordinates are $(3, 1)$ — same vector, different description.

Example in $\mathcal{P}_2(\mathbb{R})$. With $B = (1,\ 1 + t,\ (1 + t)^2)$, find $[t^2]_B$. Put $s = 1 + t$; then $t = s - 1$ and $t^2 = s^2 - 2s + 1$. So

$$t^2 = 1 \cdot (1 + t)^2 - 2(1 + t) + 1 \cdot 1, \qquad [t^2]_B = (1, -2, 1)$$

(the weights on $1$, $1 + t$ and $(1 + t)^2$, in that order). Check: $(1 + 2t + t^2) - 2 - 2t + 1 = t^2$.

---

Chapter 6 — The four fundamental subspaces

Terminology

For an $m \times n$ matrix $A$ of rank $r$ (the number of pivots):

Subspace	Symbol	Lives in	Definition
Column space	$C(A)$	$F^m$	all $A\mathbf{x}$; span of the columns
Null space	$N(A)$	$F^n$	all $\mathbf{x}$ with $A\mathbf{x} = \mathbf{0}$
Row space	$C(A^T)$	$F^n$	span of the rows
Left null space	$N(A^T)$	$F^m$	all $\mathbf{y}$ with $A^T\mathbf{y} = \mathbf{0}$, that is $\mathbf{y}^TA = \mathbf{0}^T$

Two facts about row operations

Let $EA = R$ with $E$ invertible (a product of elementary matrices) and $R$ the RREF.

Fact 1 — the row space does not change. Every row of $R$ is a combination of rows of $A$, and since $A = E^{-1}R$, every row of $A$ is a combination of rows of $R$. So $C(A^T) = C(R^T)$.

Fact 2 — linear relations among columns do not change. $A\mathbf{x} = \mathbf{0} \iff EA\mathbf{x} = \mathbf{0} \iff R\mathbf{x} = \mathbf{0}$, because $E$ is invertible. So a combination of columns of $A$ is zero exactly when the same combination of columns of $R$ is zero, and $N(A) = N(R)$. (The column spaces of $A$ and $R$ usually differ.)

Bases from the RREF

• $C(A)$ — the pivot columns of $A$ (not of $R$). In $R$ the pivot columns are distinct standard basis vectors, so they are independent, and every other column is a combination of them. By Fact 2 the same holds for the corresponding columns of $A$.
• $C(A^T)$ — the nonzero rows of $R$. They span the row space by Fact 1, and they are independent because each has a leading 1 in a column where the other rows have 0.
• $N(A)$ — the $n - r$ special solutions (one free variable 1, the others 0), as in Linear Algebra 00.
• $N(A^T)$ — the last $m - r$ rows of $E$: those rows multiply $A$ to give the zero rows of $R$.

Worked example

Use the matrix from Linear Algebra 00, Chapter 6:

$$A = \begin{pmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{pmatrix}, \qquad R = \begin{pmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}, \qquad m = 3,\ n = 4,\ r = 2.$$

Pivot columns 1 and 3; free variables $x_2, x_4$.

• Column space (dimension $r = 2$, in $\mathbb{R}^3$): basis $(1, 2, 3)$ and $(2, 6, 8)$ — columns 1 and 3 of $A$. The other columns satisfy the same relations as in $R$: column 2 $= 2 \times$ column 1, and column 4 $= -2 \times$ column 1 $+ 2 \times$ column 3. Check: $-2(1,2,3) + 2(2,6,8) = (2, 8, 10)$.
• Row space (dimension $r = 2$, in $\mathbb{R}^4$): basis $(1, 2, 0, -2)$ and $(0, 0, 1, 2)$.
• Null space (dimension $n - r = 2$, in $\mathbb{R}^4$): basis $\mathbf{s}_1 = (-2, 1, 0, 0)$ and $\mathbf{s}_2 = (2, 0, -2, 1)$.
• Left null space (dimension $m - r = 1$, in $\mathbb{R}^3$): the elimination steps $R_2 - 2R_1$, $R_3 - 3R_1$, $R_3 - R_2$ make row 3 into $-(\text{row } 1) - (\text{row } 2) + (\text{row } 3) = \mathbf{0}$. So $\mathbf{y} = (-1, -1, 1)$ is a basis: $\mathbf{y}^TA = \mathbf{0}^T$.

Orthogonality — a preview

Each row of $A$ dotted with a null-space vector gives 0 — that is what $A\mathbf{x} = \mathbf{0}$ says, one row at a time. So every vector of $N(A)$ is orthogonal to every vector of $C(A^T)$. In the example, $(1, 2, 0, -2)\cdot(-2, 1, 0, 0) = 0$, $(1, 2, 0, -2)\cdot(2, 0, -2, 1) = 0$, $(0, 0, 1, 2)\cdot(-2, 1, 0, 0) = 0$ and $(0, 0, 1, 2)\cdot(2, 0, -2, 1) = 0$. In the same way $N(A^T)$ is orthogonal to $C(A)$: $(-1, -1, 1)\cdot(1, 2, 3) = 0$ and $(-1, -1, 1)\cdot(2, 6, 8) = 0$. Over $\mathbb{R}$ the dimensions add up ($2 + 2 = 4$, $2 + 1 = 3$), which makes each pair orthogonal complements — proved in Linear Algebra 05.

Row rank equals column rank

Theorem. For every matrix, $\dim C(A) = \dim C(A^T) = r$, the number of pivots.

Proof. The pivot columns of $A$ are a basis of $C(A)$, and there are $r$ of them. The nonzero rows of $R$ are a basis of $C(A^T)$, and there are $r$ of them (one per pivot). $\blacksquare$

This is not obvious: for a $3 \times 100$ matrix it says that the 100 columns span a space of the same dimension as the 3 rows. It also shows $\operatorname{rank} A = \operatorname{rank} A^T$, and that $r \le \min(m, n)$.

Rank-one matrices. A matrix has rank 1 exactly when it is a nonzero column times a nonzero row, $A = \mathbf{u}\mathbf{v}^T$: every column is a multiple of $\mathbf{u}$, every row a multiple of $\mathbf{v}^T$. The outer-product view of Linear Algebra 01 writes any $AB$ as a sum of such pieces.

---

Chapter 7 — Rank–nullity (matrix form)

Theorem (rank–nullity). For an $m \times n$ matrix $A$,

$$\dim C(A) + \dim N(A) = n.$$

Proof. Let $r$ be the number of pivots. $\dim C(A) = r$ by Chapter 6. It remains to show that the $n - r$ special solutions $\mathbf{s}_1, \dots, \mathbf{s}_{n-r}$ are a basis of $N(A)$.

Independent: look only at the free-variable entries. In $\mathbf{s}_k$ the $k$-th free variable is 1 and the others are 0. So in $\sum c_k\mathbf{s}_k$ the $k$-th free entry is $c_k$; if the sum is $\mathbf{0}$, every $c_k = 0$.

Spanning: let $\mathbf{x} \in N(A)$ with free-variable values $f_1, \dots, f_{n-r}$. Then $\mathbf{z} = \mathbf{x} - \sum f_k\mathbf{s}_k$ is in $N(A)$ and has every free variable equal to 0. The RREF expresses each basic variable in terms of the free ones, so all basic variables of $\mathbf{z}$ are 0 too; thus $\mathbf{z} = \mathbf{0}$ and $\mathbf{x} = \sum f_k\mathbf{s}_k$.

So $\dim N(A) = n - r$, and $r + (n - r) = n$. $\blacksquare$

In words: each of the $n$ columns either contributes a pivot (a new direction in the column space) or a free variable (a new direction in the null space). For the example, $2 + 2 = 4$. Applied to $A^T$ (which has $m$ columns and the same rank), it gives $\dim N(A^T) = m - r$, here $3 - 2 = 1$.

The general version — for a linear map $T : V \to W$, $\dim V = \dim \operatorname{im} T + \dim \ker T$ — is proved in Linear Algebra 03.

Consequences

Condition on the rank	Meaning for $A\mathbf{x} = \mathbf{b}$
$r = m$ (full row rank)	solvable for every $\mathbf{b}$; $C(A) = F^m$
$r = n$ (full column rank)	at most one solution; $N(A) = \{\mathbf{0}\}$
$r = m = n$	exactly one solution; $A$ invertible
$r < m$ and $r < n$	either no solution or infinitely many

For a square matrix, "rank $n$", "$N(A) = \{\mathbf{0}\}$" and "$C(A) = F^n$" join the invertible matrix theorem from Linear Algebra 01.

Trick: rank–nullity is a quick sanity check. A $5 \times 7$ matrix has rank at most 5, so its null space has dimension at least $7 - 5 = 2$ — there are nonzero solutions of $A\mathbf{x} = \mathbf{0}$ before any computation.

---

Chapter 8 — Sums and direct sums

Terminology

• Sum of subspaces $U, W \subseteq V$: $U + W = \{\mathbf{u} + \mathbf{w} : \mathbf{u} \in U, \mathbf{w} \in W\}$. It is the smallest subspace containing both (a subspace containing $U$ and $W$ contains all such sums).
• Direct sum — the sum is direct, written $U \oplus W$, if every vector of $U + W$ can be written as $\mathbf{u} + \mathbf{w}$ in only one way.

Proposition. $U + W$ is direct if and only if $U \cap W = \{\mathbf{0}\}$.

Proof. Suppose the sum is direct and $\mathbf{v} \in U \cap W$. Then $\mathbf{0} = \mathbf{v} + (-\mathbf{v})$ with $\mathbf{v} \in U$, $-\mathbf{v} \in W$, and also $\mathbf{0} = \mathbf{0} + \mathbf{0}$; uniqueness gives $\mathbf{v} = \mathbf{0}$. Conversely, if $U \cap W = \{\mathbf{0}\}$ and $\mathbf{u} + \mathbf{w} = \mathbf{u}' + \mathbf{w}'$, then $\mathbf{u} - \mathbf{u}' = \mathbf{w}' - \mathbf{w}$ lies in both $U$ and $W$, so it is $\mathbf{0}$. $\blacksquare$

Watch out: for three or more subspaces, pairwise zero intersections are not enough. Three distinct lines through the origin in $\mathbb{R}^2$ meet pairwise only at $\mathbf{0}$, but their sum is not direct (three vectors in $\mathbb{R}^2$ are dependent).

The dimension formula

Theorem. If $U$ and $W$ are finite-dimensional subspaces of $V$, then

$$\dim(U + W) = \dim U + \dim W - \dim(U \cap W).$$

Proof. Let $\mathbf{z}_1, \dots, \mathbf{z}_k$ be a basis of $U \cap W$. Extend it to a basis $\mathbf{z}_1, \dots, \mathbf{z}_k, \mathbf{u}_1, \dots, \mathbf{u}_p$ of $U$ and to a basis $\mathbf{z}_1, \dots, \mathbf{z}_k, \mathbf{w}_1, \dots, \mathbf{w}_q$ of $W$ (Chapter 4). The combined list $\mathbf{z}_1, \dots, \mathbf{z}_k, \mathbf{u}_1, \dots, \mathbf{u}_p, \mathbf{w}_1, \dots, \mathbf{w}_q$ clearly spans $U + W$. For independence, suppose

$$\sum a_i\mathbf{z}_i + \sum b_j\mathbf{u}_j + \sum c_l\mathbf{w}_l = \mathbf{0}.$$

Then $\sum c_l\mathbf{w}_l = -\sum a_i\mathbf{z}_i - \sum b_j\mathbf{u}_j$ lies in $W$ and in $U$, hence in $U \cap W$, so $\sum c_l\mathbf{w}_l = \sum d_i\mathbf{z}_i$ for some $d_i$. The $\mathbf{z}$'s and $\mathbf{w}$'s together are a basis of $W$, so all $c_l = 0$ (and all $d_i = 0$). Now $\sum a_i\mathbf{z}_i + \sum b_j\mathbf{u}_j = \mathbf{0}$ is a relation in a basis of $U$, so all $a_i, b_j = 0$. Hence the combined list is a basis, and

$$\dim(U + W) = k + p + q = (k + p) + (k + q) - k. \qquad \blacksquare$$

This is the same shape as $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert$ for finite sets.

Examples

• In $\mathbb{R}^3$, let $U = \operatorname{span}(\mathbf{e}_1, \mathbf{e}_2)$ (the $xy$-plane) and $W = \operatorname{span}(\mathbf{e}_2, \mathbf{e}_3)$ (the $yz$-plane). Then $U \cap W = \operatorname{span}(\mathbf{e}_2)$ and $\dim(U + W) = 2 + 2 - 1 = 3$, so $U + W = \mathbb{R}^3$, but the sum is not direct.
• The plane $P = \{\mathbf{x} : x_1 + x_2 + x_3 = 0\}$ and the line $L = \operatorname{span}(1, 1, 1)$ satisfy $P \cap L = \{\mathbf{0}\}$ (a point $(c, c, c)$ with $3c = 0$), so $\dim(P + L) = 2 + 1 = 3$ and $\mathbb{R}^3 = P \oplus L$. For example $(1, 2, 3) = (-1, 0, 1) + (2, 2, 2)$.
• Every square matrix splits uniquely into symmetric plus skew-symmetric parts, $M = \tfrac12(M + M^T) + \tfrac12(M - M^T)$, so over $\mathbb{R}$ or $\mathbb{C}$ (any field where $2 \neq 0$), $M_{n \times n} = \text{Sym} \oplus \text{Skew}$. For $M = \begin{pmatrix} 1 & 2 \\ 4 & 3 \end{pmatrix}$ the parts are $\begin{pmatrix} 1 & 3 \\ 3 & 3 \end{pmatrix}$ and $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$.
• For a real $m \times n$ matrix, $\mathbb{R}^n = C(A^T) \oplus N(A)$. The intersection is $\{\mathbf{0}\}$, because a vector in both is orthogonal to itself, and $\mathbf{x}\cdot\mathbf{x} = 0$ forces $\mathbf{x} = \mathbf{0}$; the dimensions add to $r + (n - r) = n$. So every $\mathbf{x} \in \mathbb{R}^n$ splits uniquely as $\mathbf{x} = \mathbf{x}_r + \mathbf{x}_n$, a row-space part plus a null-space part — the left half of the four-subspace picture. Since $A\mathbf{x}_n = \mathbf{0}$, $A\mathbf{x} = A\mathbf{x}_r$: every $\mathbf{b}$ in $C(A)$ is $A\mathbf{x}_r$ for a row-space vector $\mathbf{x}_r$, which is the arrow from row space to column space in the figure of Chapter 6.

---

Practice Exercises

Exercise 1 — A polynomial subspace

Show that $U = \{p \in \mathcal{P}_2(\mathbb{R}) : p(1) = 0\}$ is a subspace, and find a basis and its dimension.

Solution

The zero polynomial has $p(1) = 0$, and $(ap + bq)(1) = ap(1) + bq(1) = 0$, so $U$ is a subspace. $p(t) = c_0 + c_1t + c_2t^2$ is in $U$ iff $c_0 + c_1 + c_2 = 0$, i.e. $c_0 = -c_1 - c_2$, so $p = c_1(t - 1) + c_2(t^2 - 1)$. The list $t - 1$, $t^2 - 1$ spans $U$ and is independent (only the second has a $t^2$ term), so $\dim U = 2$. This matches rank–nullity: $U$ is the null space of the map $p \mapsto p(1)$, and $3 - 1 = 2$.

Exercise 2 — Not a subspace

Is $\{(x, y) \in \mathbb{R}^2 : xy \ge 0\}$ a subspace?

Solution

No. It contains $\mathbf{0}$ and is closed under scalar multiplication ($(cx)(cy) = c^2xy \ge 0$), but not under addition: $(1, 0) + (0, -1) = (1, -1)$ has $xy = -1 < 0$. It is the union of the first and third quadrants.

Exercise 3 — Shrink to a basis

Find a basis for $\operatorname{span}\{(1, 2, 1), (2, 4, 2), (1, 0, 1), (0, 1, 0)\}$ taken from the given vectors, and its dimension.

Solution

Put them as columns and row reduce: $\begin{pmatrix} 1 & 2 & 1 & 0 \\ 2 & 4 & 0 & 1 \\ 1 & 2 & 1 & 0 \end{pmatrix} \to \begin{pmatrix} 1 & 2 & 0 & 1/2 \\ 0 & 0 & 1 & -1/2 \\ 0 & 0 & 0 & 0 \end{pmatrix}$. Pivot columns 1 and 3, so $(1, 2, 1)$ and $(1, 0, 1)$ are a basis and the dimension is 2. (All four vectors satisfy $x_1 = x_3$, a plane.)

Exercise 4 — Four subspaces of a rank-one matrix

For $B = \begin{pmatrix} 1 & 2 \\ 2 & 4 \\ 3 & 6 \end{pmatrix}$, give bases and dimensions of all four subspaces.

Solution

$m = 3$, $n = 2$, $r = 1$ ($B = (1, 2, 3)^T(1, 2)$). $C(B)$: $(1, 2, 3)$, dimension 1. $C(B^T)$: $(1, 2)$, dimension 1. $N(B)$: $(-2, 1)$, dimension $n - r = 1$. $N(B^T)$: solutions of $y_1 + 2y_2 + 3y_3 = 0$, basis $(-2, 1, 0)$, $(-3, 0, 1)$, dimension $m - r = 2$. Check orthogonality: $(1, 2)\cdot(-2, 1) = 0$.

Exercise 5 — Coordinates

Find the coordinates of $p(t) = 2 + 3t + t^2$ relative to $B = (1,\ 1 + t,\ (1 + t)^2)$.

Solution

$(1 + t)^2 = 1 + 2t + t^2$, so $p - (1 + t)^2 = 1 + t$. Hence $p = 0 \cdot 1 + 1 \cdot (1 + t) + 1 \cdot (1 + t)^2$, and $[p]_B = (0, 1, 1)$. Check: $(1 + t) + (1 + 2t + t^2) = 2 + 3t + t^2$.

Exercise 6 — Forced intersection

Let $U$ and $W$ be 3-dimensional subspaces of $\mathbb{R}^5$. Prove that $U \cap W \neq \{\mathbf{0}\}$.

Solution

$U + W \subseteq \mathbb{R}^5$, so $\dim(U + W) \le 5$. The dimension formula gives $\dim(U \cap W) = 3 + 3 - \dim(U + W) \ge 6 - 5 = 1$.

Exercise 7 — Proof practice

Prove that if $\mathbf{v}_1, \dots, \mathbf{v}_m$ is independent and $\mathbf{v} \notin \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_m)$, then $\mathbf{v}_1, \dots, \mathbf{v}_m, \mathbf{v}$ is independent.

Solution

Suppose $a_1\mathbf{v}_1 + \dots + a_m\mathbf{v}_m + a\mathbf{v} = \mathbf{0}$. If $a \neq 0$, then $\mathbf{v} = -\frac1a\sum a_i\mathbf{v}_i$ is in the span — a contradiction. So $a = 0$, and then all $a_i = 0$ by independence of the $\mathbf{v}_i$. (This is the step used in Chapter 4, part 4.)

---

Cheat-sheet

Idea	Key fact
Vector space	8 axioms over a field $F$; $0\mathbf{v} = \mathbf{0}$, $(-1)\mathbf{v} = -\mathbf{v}$
Subspace test	contains $\mathbf{0}$; closed under $+$ and scalars
Span	smallest subspace containing the list
Dependence lemma	some $\mathbf{v}_j$ is in the span of the earlier ones and can be removed
Basis	independent + spanning; unique coordinates
Steinitz	independent length $\le$ spanning length
Dimension	length of any basis; $\dim \mathcal{P}_n = n + 1$, $\dim M_{m \times n} = mn$
In dim $n$	$n$ independent or $n$ spanning vectors form a basis
$C(A)$ basis	pivot columns of $A$; dim $r$
$C(A^T)$ basis	nonzero rows of $R$; dim $r$
$N(A)$ basis	special solutions; dim $n - r$
$N(A^T)$ basis	last $m - r$ rows of $E$ in $EA = R$
Rank	row rank = column rank = number of pivots
Rank–nullity	$r + \dim N(A) = n$
Direct sum	$U \cap W = \{\mathbf{0}\}$ $\iff$ unique decomposition
Dimension formula	$\dim(U + W) = \dim U + \dim W - \dim(U \cap W)$

---

What's next

Linear Algebra 03 moves from spaces to maps between them. A linear map $T : V \to W$ is determined by what it does to a basis, so after choosing bases it becomes a matrix — and changing the bases changes the matrix to $Q^{-1}AP$ (or $P^{-1}AP$ for an operator). The post proves the full rank–nullity theorem for linear maps, defines isomorphism (why every $n$-dimensional space "is" $F^n$), and then builds the determinant from its defining properties, with its geometric meaning as a signed volume scale factor.

---

References

• Sheldon Axler, Linear Algebra Done Right, 4th edition, Springer (Undergraduate Texts in Mathematics), 2024 — Chapters 1–2 (vector spaces, subspaces, sums and direct sums, span, independence, bases, dimension, the linear dependence lemma). Open access at linear.axler.net.
• Kenneth Hoffman and Ray Kunze, Linear Algebra, 2nd edition, Prentice-Hall, 1971 — Chapter 2 (vector spaces, bases and dimension, coordinates, row-equivalence).
• Gilbert Strang, Introduction to Linear Algebra, 6th edition, Wellesley-Cambridge Press, 2023 — Chapter 3 (the four fundamental subspaces, rank, dimensions).
• Gilbert Strang, "The Fundamental Theorem of Linear Algebra", The American Mathematical Monthly 100(9), 1993, pp. 848–855 — the source of the four-subspace picture.
• David C. Lay, Steven R. Lay and Judi J. McDonald, Linear Algebra and Its Applications, 6th edition, Pearson, 2021 — Chapter 4 (vector spaces, null and column spaces, bases, coordinate systems, dimension, rank).
• MIT OpenCourseWare, 18.06 Linear Algebra, Spring 2010 (Gilbert Strang) — Lectures 5–10: vector spaces, column and null spaces, solving $A\mathbf{x} = \mathbf{0}$ and $A\mathbf{x} = \mathbf{b}$, independence, basis and dimension, the four fundamental subspaces.

Note: this post is in progress. Planned additions: quotient spaces $V/U$ and their dimension, a section on infinite-dimensional spaces (why $\mathcal{P}(F)$ has a countable basis but $C[0,1]$ is harder), and a worked example of the four subspaces over $\mathbb{F}_2$.