Contents / Linear Algebra / Vector Spaces

Chapter 5

Vector Spaces

Abstract vector spaces over a field, subspaces, bases, dimension, coordinates, and the four fundamental subspaces.

Introduction

Up to this point every vector in this course has been a list of numbers. That was a useful fiction. The theorems we proved about $R^{n}$ — span, independence, basis, dimension — never once used the fact that a vector is a list. They used only that vectors can be added and scaled, and that those two operations obey a short list of algebraic rules.

That observation is worth a great deal. Polynomials can be added and scaled. So can matrices of a fixed shape, functions on an interval, infinite sequences, solutions of a linear differential equation, and digital signals. Each of those is a vector space, and every theorem in this chapter applies to all of them at once. When you prove that any two bases of a space have the same size, you have proved it simultaneously for arrows in the plane, for cubic polynomials, and for the solution set of $y^{''} + y = 0$ .

This chapter builds that framework from the axioms. It defines a vector space over a field, collects the examples you will meet for the rest of your mathematical life, and then develops the four load-bearing ideas — span, independence, basis, dimension — in the general setting. It closes by coming back to matrices, where the abstract machinery pays for itself: the column space, row space and null space of a matrix are vector spaces, their dimensions are locked together by the Rank Theorem, and the whole structure of a linear system is readable off those numbers.

The chapter is proof-carrying. Almost every result here has a short argument, and the arguments are the content: they are what tells you why dimension is well defined rather than merely that it is.

5.1Vector spaces and fields

Before vectors, scalars. The numbers we multiply vectors by must themselves form a system in which we can add, subtract, multiply and divide. Such a system is called a field.

Definition 5.1 (Field). A field $F$ is a set with two operations, addition and multiplication, such that both are commutative and associative, multiplication distributes over addition, there are distinct identity elements $0$ and $1$ , every element $a$ has an additive inverse $- a$ , and every $a \neq = 0$ has a multiplicative inverse $a^{- 1}$ .

The three fields used in this course are the real numbers $R$ , the complex numbers $C$ , and the two-element field

F_{2} = {0, 1}, 1 + 1 = 0,

which is the arithmetic of a single bit and is the field underneath error-correcting codes. The rational numbers $Q$ are a field; the integers $Z$ are not, because $2$ has no multiplicative inverse in $Z$ . Unless a statement says otherwise, read $F$ below as $R$ ; nothing in this chapter changes if you swap in $C$ .

Definition 5.2 (Vector space). A vector space over a field $F$ is a set $V$ together with an addition $V \times V \to V$ and a scalar multiplication $F \times V \to V$ such that for all $u, v, w \in V$ and all $c, d \in F$ :

$u + v = v + u$ (commutativity);
$(u + v) + w = u + (v + w)$ (associativity);
there is a $0 \in V$ with $v + 0 = v$ for all $v$ (additive identity);
for each $v$ there is a $- v \in V$ with $v + (- v) = 0$ (additive inverse);
$1 v = v$ (unit scalar);
$c (d v) = (c d) v$ (compatibility of scalars);
$c (u + v) = c u + c v$ (distributivity over vector addition);
$(c + d) v = c v + d v$ (distributivity over scalar addition).

Elements of $V$ are called vectors; elements of $F$ are called scalars.

Two of the axioms are quietly hidden in the phrase "an addition $V \times V \to V$ ": the sum of two elements of $V$ must land back in $V$ , and likewise $c v \in V$ . These are the closure requirements, and in practice they are the conditions that fail most often.

Axiom 5 looks like a triviality. It is not: it is the axiom that ties the scalar $1$ to the vector operation, and without it you can build a perfectly consistent system that satisfies the other seven and is useless. The example at the end of this section does exactly that. Axioms 1–4 say that $V$ is a commutative group under addition, and 5–8 say the scalars act on it compatibly.

Intuition. A vector space is a set of things you are allowed to mix. You can take $3$ parts of one thing and $- \frac{1}{2}$ parts of another and add them, and the recipe you get is again a thing of the same kind. That is all. Nothing in the definition mentions length, angle, or coordinates — those are extra structure added in a later chapter. A vector space is just a mixing rule that never takes you outside the set.

The axioms are short enough that the first consequences can be squeezed out immediately, and they are worth seeing derived rather than assumed.

Proposition 5.3 (Elementary consequences of the axioms). In any vector space $V$ over $F$ :

the zero vector is unique, and each $v$ has exactly one additive inverse;
$0 v = 0$ for every $v \in V$ ;
$c 0 = 0$ for every $c \in F$ ;
$(- 1) v = - v$ ;
if $c v = 0$ then $c = 0$ or $v = 0$ .

Proof. (1) If $0$ and $0^{'}$ are both additive identities then $0 = 0 + 0^{'} = 0^{'}$ , using axiom 3 for each in turn. If $w$ and $w^{'}$ are both inverses of $v$ , then

w = w + 0 = w + (v + w^{'}) = (w + v) + w^{'} = 0 + w^{'} = w^{'} .

(2) By axiom 8, $0 v + 0 v = (0 + 0) v = 0 v$ . Add $- (0 v)$ to both sides to get $0 v = 0$ .

(3) By axiom 7, $c 0 + c 0 = c (0 + 0) = c 0$ ; add $- (c 0)$ to both sides.

(4) Using axioms 5 and 8, $v + (- 1) v = 1 v + (- 1) v = (1 + (- 1)) v = 0 v = 0$ by (2). So $(- 1) v$ is an additive inverse of $v$ , and by (1) it is the additive inverse.

(5) Suppose $c v = 0$ and $c \neq = 0$ . Then $c^{- 1}$ exists in $F$ , and

v = 1 v = (c^{- 1} c) v = c^{- 1} (c v) = c^{- 1} 0 = 0

by axioms 5 and 6 and part (3).∎

Notice where part (5) used the field: it needed $c^{- 1}$ . This is the one place in the elementary theory where "the scalars form a field" rather than merely a ring does real work, and it is the reason the whole subject is built over fields.

Now the examples. Learn these; they are the vector spaces that the rest of mathematics runs on.

Example 5.4 (The standard spaces). Verify that each of the following is a vector space over $R$ , and identify its zero vector: $R^{n}$ ; the space $P_{n}$ of polynomials of degree at most $n$ ; the space $M_{m \times n}$ of $m \times n$ real matrices; the space $F (S, R)$ of all functions from a set $S$ to $R$ .

Solution. $R^{n}$ with componentwise operations. Every axiom is the corresponding axiom of $R$ applied in each of the $n$ slots at once. Zero vector: $(0, 0, \dots, 0)$ .

$P_{n} = {a_{0} + a_{1} x + \dots + a_{n} x^{n} : a_{i} \in R}$ , with polynomials added coefficient by coefficient and scaled coefficient by coefficient. Closure holds because adding two polynomials of degree at most $n$ cannot raise the degree, and scaling cannot either. Zero vector: the zero polynomial, all of whose coefficients vanish.

The full space $P$ of polynomials of any degree is also a vector space; it is not contained in any $P_{n}$ , and is our first example of an infinite-dimensional space.

$M_{m \times n}$ with entrywise addition and scaling. The zero vector is the $m \times n$ zero matrix. Note that matrix multiplication plays no role here — it is not part of the vector space structure.

$F (S, R)$ , where $(f + g) (s) = f (s) + g (s)$ and $(c f) (s) = c f (s)$ . Each axiom is checked by evaluating both sides at an arbitrary $s \in S$ and citing the corresponding axiom in $R$ . For instance $(c (f + g)) (s) = c (f (s) + g (s)) = c f (s) + c g (s) = (c f + c g) (s)$ , and since two functions are equal exactly when they agree at every point, $c (f + g) = c f + c g$ . Zero vector: the function that is identically $0$ .

Sanity check on the pattern: in all four cases the operations are performed "slotwise" — per coordinate, per coefficient, per entry, per input value — and the axioms are inherited slotwise from $R$ .□

Two more families deserve names. $C [a, b]$ , the set of continuous real functions on $[a, b]$ , is a vector space because a sum of continuous functions is continuous and a scalar multiple of a continuous function is continuous. The set $R^{\infty}$ of all infinite real sequences $(a_{1}, a_{2}, a_{3}, \dots)$ is a vector space under termwise operations. And the smallest example of all, the zero space ${0}$ , satisfies every axiom trivially; it is the only vector space with finitely many elements when $F = R$ .

Example 5.5 (An exotic vector space). Let $V = R_{> 0}$ , the set of strictly positive reals, with operations

x \oplus y = x y, c ⊙ x = x^{c} .

Show $V$ is a vector space over $R$ and identify its zero vector and the additive inverse of $x$ .

Solution. Closure: a product of positive numbers is positive, and $x^{c} > 0$ for $x > 0$ and any real $c$ . So both operations land in $V$ .

Axioms 1 and 2 are commutativity and associativity of ordinary multiplication. For axiom 3 we need an element $z$ with $x \oplus z = x$ , that is $x z = x$ ; so $z = 1$ . The zero vector of this space is the number $1$ .

Axiom 4: we need $x \oplus w = 1$ , that is $x w = 1$ , so $w = 1/ x$ . The additive inverse of $x$ is its reciprocal.

Axiom 5: $1 ⊙ x = x^{1} = x$ . Axiom 6: $c ⊙ (d ⊙ x) = (x^{d})^{c} = x^{c d} = (c d) ⊙ x$ . Axiom 7: $c ⊙ (x \oplus y) = (x y)^{c} = x^{c} y^{c} = (c ⊙ x) \oplus (c ⊙ y)$ . Axiom 8: $(c + d) ⊙ x = x^{c + d} = x^{c} x^{d} = (c ⊙ x) \oplus (d ⊙ x)$ .

All eight hold, so $V$ is a vector space. Sanity check: the map $x \mapsto ln x$ turns $\oplus$ into ordinary addition and $⊙$ into ordinary scalar multiplication, so this space is a disguised copy of $R^{1}$ . That is why every axiom worked out — the logarithm was doing the work all along, and this space has dimension $1$ .□

Example 5.6 (Two non-examples). For each set below, find one axiom that fails. (a) The first quadrant $Q = {(x, y) \in R^{2} : x \geq 0, y \geq 0}$ with the usual operations. (b) $R^{2}$ with the usual addition but with scalar multiplication redefined as $c \cdot (x, y) = (c x, 0)$ .

Solution. (a) Axiom 4 fails. Take $(1, 1) \in Q$ . Its additive inverse would have to be $(- 1, - 1)$ , which is not in $Q$ , and by the uniqueness in the elementary-consequences proposition no other element can serve. Equivalently, $Q$ is not closed under multiplication by $- 1$ , so scalar multiplication does not map $R \times Q$ into $Q$ .

(b) Axiom 5 fails: $1 \cdot (x, y) = (x, 0) \neq = (x, y)$ whenever $y \neq = 0$ . It is worth checking how much does survive: axioms 1–4 are untouched since addition is unchanged; axiom 6 holds since $c \cdot (d \cdot (x, y)) = c \cdot (d x, 0) = (c d x, 0) = (c d) \cdot (x, y)$ ; axiom 7 and axiom 8 both hold by direct computation. So seven of the eight axioms hold and the system is still worthless — in it, $1 \cdot v$ forgets half of $v$ . That is precisely why axiom 5 is on the list.□

Pitfall. "It has an addition and a scalar multiplication, so it must be a vector space" is the single most common error here. The operations must satisfy all eight axioms with the operations you were given, not with the ones you expected. When you are handed a strange $\oplus$ and $⊙$ , resist the urge to read $0$ as "the number zero": the additive identity is whatever element the axiom demands, as the positive-reals example shows.

Exercises for §5.1 →

5.2Subspaces

Inside a vector space sit smaller vector spaces. Rather than re-checking eight axioms each time, we exploit the fact that most of them are inherited automatically.

Definition 5.7 (Subspace). A subset $U$ of a vector space $V$ over $F$ is a subspace of $V$ if $U$ is itself a vector space over $F$ under the addition and scalar multiplication it inherits from $V$ .

Theorem 5.8 (Subspace criterion). A subset $U \subseteq V$ is a subspace of $V$ if and only if

$0 \in U$ ;
$u + v \in U$ whenever $u, v \in U$ ;
$c u \in U$ whenever $c \in F$ and $u \in U$ .

Proof. If $U$ is a subspace it is a vector space, so it is closed under both operations, giving (2) and (3); and it has an additive identity $z \in U$ with $z + z = z$ , whence adding $- z$ (computed in $V$ ) gives $z = 0$ , which is (1).

Conversely suppose (1)–(3). Conditions (2) and (3) say exactly that the two operations of $V$ restrict to operations on $U$ . Axioms 1, 2, 5, 6, 7 and 8 are identities between elements; they hold for all elements of $V$ , so in particular for elements of $U$ — nothing needs re-checking. Axiom 3 is condition (1). For axiom 4, given $u \in U$ , condition (3) with $c = - 1$ puts $(- 1) u \in U$ , and $(- 1) u = - u$ by the elementary-consequences proposition. So all eight axioms hold in $U$ .∎

The proof is the reason the criterion is only three conditions rather than eight: identities descend to subsets for free, and only the existence claims — a zero, an inverse — and closure need attention. Condition (1) can be weakened to " $U$ is nonempty", because a nonempty $U$ closed under scaling contains $0 u = 0$ ; but checking $0 \in U$ directly is faster and rules out most impostors in one line.

Proposition 5.9 (One-step subspace test). A nonempty subset $U \subseteq V$ is a subspace if and only if $c u + d v \in U$ for all $u, v \in U$ and all $c, d \in F$ .

Proof. A subspace is closed under scaling and then addition, so the condition holds. Conversely, pick any $u \in U$ (possible since $U \neq = \emptyset$ ); taking $c = d = 0$ gives $0 \in U$ , taking $c = d = 1$ gives closure under addition, and taking $d = 0$ gives closure under scaling.∎

Here is the standard stock of subspaces. In $R^{3}$ : the zero space, every line through the origin, every plane through the origin, and $R^{3}$ itself — and, as we will prove once dimension is available, nothing else. In $P_{5}$ : the subspace $P_{3}$ , the polynomials with $p (2) = 0$ , the even polynomials. In $M_{n \times n}$ : the symmetric matrices, the upper-triangular matrices, the matrices of trace zero, the diagonal matrices. In $F (R, R)$ : the continuous functions, the differentiable functions, the polynomials, and the solution set of $y^{''} + 4 y = 0$ .

The last of these is worth pausing on. The reason linear differential equations are called linear is exactly that their solution sets are subspaces: if $y_{1}^{''} + 4 y_{1} = 0$ and $y_{2}^{''} + 4 y_{2} = 0$ then $(c y_{1} + d y_{2})^{''} + 4 (c y_{1} + d y_{2}) = 0$ by linearity of differentiation. The one-step test applies verbatim, and everything this chapter proves about dimension immediately becomes a statement about how many independent solutions such an equation has.

Non-examples are just as instructive. A line not through the origin fails condition (1). The set ${(x, y) : x y = 0}$ — the union of the two axes — contains $0$ and is closed under scaling but not addition: $(1, 0) + (0, 1) = (1, 1)$ is off both axes. The set ${(x, y) : x \geq 0}$ is closed under addition but not under multiplication by $- 1$ . The set of invertible $2 \times 2$ matrices fails at once, since it omits the zero matrix. Each non-example fails exactly one condition, and each of the three conditions is genuinely needed.

Intuition. Think of $V$ as a country and a subspace as a region you can never drive out of, no matter how you combine your moves, and which contains your starting point, the origin. A plane through the origin in $R^{3}$ is such a region: add two vectors lying in it, stretch either of them, and you are still in the plane. Tilt that plane up so it misses the origin and the region is no longer closed — scaling any point in it by $0$ drops you out.

Theorem 5.10 (Intersections of subspaces). If $U$ and $W$ are subspaces of $V$ , then $U \cap W$ is a subspace of $V$ . More generally the intersection of any family of subspaces of $V$ is a subspace.

Proof. $0$ lies in every subspace, hence in the intersection. If $u, v$ lie in every member of the family, then so does $c u + d v$ , since each member is closed under linear combinations. By the one-step test the intersection is a subspace.∎

Proposition 5.11 (Unions are almost never subspaces). If $U$ and $W$ are subspaces of $V$ , then $U \cup W$ is a subspace if and only if $U \subseteq W$ or $W \subseteq U$ .

Proof. If one contains the other the union is the larger one, which is a subspace. Conversely suppose $U \cup W$ is a subspace and neither containment holds. Choose $u \in U ∖ W$ and $w \in W ∖ U$ . Then $u + w$ lies in $U \cup W$ , so it lies in $U$ or in $W$ . If $u + w \in U$ then $w = (u + w) - u \in U$ , a contradiction; if $u + w \in W$ then $u \in W$ , also a contradiction.∎

Geometrically: two distinct lines through the origin in $R^{2}$ form an $\times$ shape, and adding one vector from each lands you off both lines. To get a subspace out of two subspaces you must not take their union but their sum, which is the subject of the next section.

Example 5.12 (Subspaces of a matrix space). Let $V = M_{2 \times 2} (R)$ . Decide which of these are subspaces: (a) the symmetric matrices $S = {A : A^{T} = A}$ ; (b) the matrices with $det A = 0$ ; (c) the matrices of trace $0$ .

Solution. (a) The zero matrix is symmetric. If $A^{T} = A$ and $B^{T} = B$ then $(c A + d B)^{T} = c A^{T} + d B^{T} = c A + d B$ , using that transposition is linear. So $S$ passes the one-step test and is a subspace.

(b) Not a subspace. Both

A = (1000), B = (0001)

have determinant $0$ , but $A + B = I$ has determinant $1$ . Closure under addition fails. (The set does contain $0$ and is closed under scaling, so only one condition fails — which is enough.)

(c) The zero matrix has trace $0$ , and $tr (c A + d B) = c tr A + d tr B = 0$ , since the trace is a linear function of the entries. So the trace-zero matrices form a subspace.

Sanity check: (a) and (c) are each cut out by linear equations in the entries ( $a_{12} = a_{21}$ ; $a_{11} + a_{22} = 0$ ), while (b) is cut out by the quadratic equation $a_{11} a_{22} - a_{12} a_{21} = 0$ . Solution sets of homogeneous linear equations are always subspaces; solution sets of nonlinear ones essentially never are.□

Example 5.13 (A subspace inside a function space). Let $V = F (R, R)$ and let $U = {f \in V : f (3) = 0}$ and $W = {f \in V : f (3) = 1}$ . Which is a subspace?

Solution. $U$ : the zero function satisfies $f (3) = 0$ . If $f (3) = g (3) = 0$ then $(c f + d g) (3) = c f (3) + d g (3) = 0$ . So $U$ is a subspace.

$W$ : the zero function has $f (3) = 0 \neq = 1$ , so $0 \in / W$ and $W$ is not a subspace. It also fails closure: if $f (3) = g (3) = 1$ then $(f + g) (3) = 2$ .

Sanity check: $U$ is defined by a homogeneous condition, $W$ by an inhomogeneous one. The same dichotomy governs $A x = 0$ versus $A x = b$ .□

Pitfall. The condition defining a subspace must be homogeneous and linear. " $x + y + z = 0$ " gives a subspace; " $x + y + z = 1$ " does not (no zero vector); " $x^{2} = y^{2}$ " does not (not closed under addition: $(1, 1)$ and $(1, - 1)$ sum to $(2, 0)$ ); " $x \geq 0$ " does not (not closed under negative scaling).

Exercises for §5.2 →

5.3Sums and direct sums

Since the union of two subspaces is a blunt instrument, we take instead the smallest subspace containing both.

Definition 5.14 (Sum of subspaces). If $U$ and $W$ are subspaces of $V$ , their sum is

U + W = {u + w : u \in U, w \in W} .

Proposition 5.15 (The sum is the smallest subspace containing both). $U + W$ is a subspace of $V$ containing both $U$ and $W$ , and it is contained in every subspace of $V$ that contains both.

Proof. $0 = 0 + 0 \in U + W$ . Given $u_{1} + w_{1}$ and $u_{2} + w_{2}$ in the sum and scalars $c, d$ ,

c (u_{1} + w_{1}) + d (u_{2} + w_{2}) = (c u_{1} + d u_{2}) + (c w_{1} + d w_{2}),

where the first bracket lies in $U$ and the second in $W$ . So $U + W$ is a subspace. Taking $w = 0$ shows $U \subseteq U + W$ , and similarly $W \subseteq U + W$ . Finally if $X$ is a subspace with $U \subseteq X$ and $W \subseteq X$ , then for $u \in U$ and $w \in W$ both lie in $X$ , so $u + w \in X$ ; hence $U + W \subseteq X$ .∎

A vector of $U + W$ can usually be written as $u + w$ in many ways. In $R^{2}$ , let $U$ be the $x$ -axis, $W$ the $y$ -axis, and $X$ the line $y = x$ . Then $U + W = R^{2}$ and also $U + X = R^{2}$ ; but the vector $(3, 1)$ is $(3, 0) + (0, 1)$ in the first decomposition and $(2, 0) + (1, 1)$ in the second — and in each case that is the only decomposition. Contrast $U + W + X = R^{2}$ , where $(3, 1) = (3, 0) + (0, 1) + (0, 0) = (2, 0) + (0, 0) + (1, 1)$ and uniqueness is gone. Uniqueness is the property worth naming.

Definition 5.16 (Direct sum). The sum $U + W$ is called direct, written $U \oplus W$ , if every vector of $U + W$ can be written as $u + w$ with $u \in U$ and $w \in W$ in exactly one way. If $V = U \oplus W$ we call $W$ a complement of $U$ in $V$ .

Theorem 5.17 (Criterion for a direct sum). For subspaces $U, W$ of $V$ , the sum $U + W$ is direct if and only if $U \cap W = {0}$ . Equivalently, it is direct if and only if the only way to write $0 = u + w$ with $u \in U, w \in W$ is $u = w = 0$ .

Proof. Suppose the sum is direct and let $v \in U \cap W$ . Then

0 = v + (- v) = 0 + 0,

and the first expression has its $U$ -part equal to $v$ while the second has $U$ -part $0$ . Uniqueness of the decomposition of $0$ forces $v = 0$ .

Conversely suppose $U \cap W = {0}$ and that $u_{1} + w_{1} = u_{2} + w_{2}$ with $u_{i} \in U$ , $w_{i} \in W$ . Rearranging,

u_{1} - u_{2} = w_{2} - w_{1} .

The left side lies in $U$ and the right side lies in $W$ , so both lie in $U \cap W = {0}$ . Hence $u_{1} = u_{2}$ and $w_{1} = w_{2}$ , which is uniqueness.∎

The criterion is startlingly cheap to check: intersect two subspaces and see whether anything but $0$ survives. Note the asymmetry with three or more summands — for $U_{1} + U_{2} + U_{3}$ pairwise trivial intersections are not enough, as the three lines $U, W, X$ above show: they meet pairwise only at the origin, yet the sum is not direct. The correct general condition is that the only decomposition of $0$ is the all-zero one.

Intuition. A direct sum is a filing system with no ambiguity. Splitting $R^{3}$ into the $x y$ -plane and the $z$ -axis, every vector has one and only one horizontal part and one vertical part — a unique filing. Splitting it into the $x y$ -plane and the $x z$ -plane instead, the vector $(1, 0, 0)$ can be filed under either, or half under each, and the system is useless for bookkeeping. The intersection of the two drawers, the $x$ -axis, is exactly the ambiguity.

Example 5.18 (Symmetric plus antisymmetric). In $V = M_{n \times n} (R)$ , let $S$ be the symmetric matrices and $K$ the antisymmetric ones ( $A^{T} = - A$ ). Show $V = S \oplus K$ .

Solution. First, $S$ and $K$ are subspaces (each is cut out by linear conditions on the entries; the argument for $S$ was given earlier and the one for $K$ is identical).

$V = S + K$ : given any $A$ , write

A = \in S \frac{1}{2} (A + A^{T}) + \in K \frac{1}{2} (A - A^{T}),

and check the memberships: $(\frac{1}{2} (A + A^{T}))^{T} = \frac{1}{2} (A^{T} + A)$ , so the first summand is symmetric, and $(\frac{1}{2} (A - A^{T}))^{T} = \frac{1}{2} (A^{T} - A)$ , the negative of the second summand.

The sum is direct: if $A \in S \cap K$ then $A = A^{T} = - A$ , so $2 A = 0$ and $A = 0$ . By the direct-sum criterion, $V = S \oplus K$ .

Sanity check with $n = 2$ on $A = (1243)$ : the symmetric part is $(1333)$ and the antisymmetric part is $(0 - 1 10)$ , and they do sum to $A$ .□

Example 5.19 (Deciding whether a sum is direct). In $R^{4}$ let $U = span {(1, 0, 0, 0), (0, 1, 0, 0)}$ and $W = {(x, y, z, w) : x = y and z = w}$ . Is $U + W$ direct, and what is $U + W$ ?

Solution. A vector of $W$ has the form $(s, s, t, t)$ , so $W = span {(1, 1, 0, 0), (0, 0, 1, 1)}$ .

Intersection: a vector in $U$ has last two coordinates $0$ , so if it also lies in $W$ then $t = 0$ and the vector is $(s, s, 0, 0)$ ; being in $U$ imposes nothing further, so $(1, 1, 0, 0) \in U \cap W$ and the intersection is not trivial. The sum is not direct.

What is $U + W$ ? It is spanned by $(1, 0, 0, 0), (0, 1, 0, 0), (1, 1, 0, 0), (0, 0, 1, 1)$ . The third is the sum of the first two and can be dropped, leaving three vectors which are visibly independent, so $dim (U + W) = 3$ ; in fact $U + W = {(x, y, z, w) : z = w}$ .

Sanity check against the dimension formula proved later: $dim U + dim W - dim (U \cap W) = 2 + 2 - 1 = 3$ , matching.□

Pitfall. $U \oplus W$ is not a different set from $U + W$ — it is the same set, with a promise attached. Writing $\oplus$ asserts that the intersection is trivial; if you have not checked that, write $+$ .

Exercises for §5.3 →

5.4Linear combinations and span

Definition 5.20 (Linear combination and span). Let $v_{1}, \dots, v_{k}$ be vectors in a vector space $V$ over $F$ . A linear combination of them is any vector of the form

c_{1} v_{1} + c_{2} v_{2} + \dots + c_{k} v_{k}, c_{i} \in F .

Their span is the set of all such combinations,

span {v_{1}, \dots, v_{k}} = {c_{1} v_{1} + \dots + c_{k} v_{k} : c_{i} \in F} .

By convention $span \emptyset = {0}$ . For an infinite set $S \subseteq V$ , $span S$ means the set of all finite linear combinations of elements of $S$ . If $span S = V$ we say $S$ spans $V$ , and $V$ is finite-dimensional if some finite set spans it.

The restriction to finite combinations is not a technicality to skip over: an infinite sum has no meaning in a bare vector space, where there is no notion of limit. That is why $P$ , the space of all polynomials, is spanned by ${1, x, x^{2}, \dots}$ — every polynomial is a finite combination — while the function $e^{x}$ , whose power series needs infinitely many terms, is not in that span.

Theorem 5.21 (The span is the smallest subspace containing the vectors). For any $v_{1}, \dots, v_{k} \in V$ , the set $span {v_{1}, \dots, v_{k}}$ is a subspace of $V$ containing each $v_{i}$ , and it is contained in every subspace of $V$ containing all the $v_{i}$ .

Proof. Taking all $c_{i} = 0$ gives $0$ , so the span is nonempty. Given two combinations and scalars $a, b$ ,

a i \sum c_{i} v_{i} + b i \sum d_{i} v_{i} = i \sum (a c_{i} + b d_{i}) v_{i},

again a linear combination of the same vectors; by the one-step test the span is a subspace. Taking $c_{i} = 1$ and the rest $0$ shows $v_{i}$ is in the span. Finally, a subspace $X$ containing every $v_{i}$ is closed under scaling and addition, so by induction on $k$ it contains every $c_{1} v_{1} + \dots + c_{k} v_{k}$ ; hence it contains the span.∎

The "smallest" clause is what makes span a useful construction rather than a mere abbreviation: $span S$ is the subspace generated by $S$ , and any argument that needs "the least subspace containing these vectors" can use it.

Intuition. Two colours of paint, red and blue, span every purple you can mix from them, in every proportion, including pure red and pure blue. Yellow is not in the span — no amount of mixing gets you there. Adding yellow to your set does not merely add one colour; it opens up a whole new plane of mixtures. That jump is what a new independent direction does.

Proposition 5.22 (Redundant vectors can be dropped). If $v_{k} \in span {v_{1}, \dots, v_{k - 1}}$ , then

span {v_{1}, \dots, v_{k}} = span {v_{1}, \dots, v_{k - 1}} .

Proof. The right side is contained in the left, since a combination of the first $k - 1$ vectors is a combination of all $k$ with last coefficient $0$ . For the other direction write $v_{k} = \sum_{i < k} a_{i} v_{i}$ . Then

i < k \sum c_{i} v_{i} + c_{k} v_{k} = i < k \sum (c_{i} + c_{k} a_{i}) v_{i},

which lies in the right side.∎

In $R^{n}$ , testing membership in a span is a linear system, and this is the computational face of the whole chapter.

Method 5.23 (Testing membership in a span in $R^{n}$ ). To decide whether $b \in span {v_{1}, \dots, v_{k}}$ :

Form the augmented matrix $[v_{1} \dots v_{k} ∣ b]$ , the $v_{i}$ as columns.
Row-reduce.
If a row of the form $[0 \dots 0 ∣ c]$ with $c \neq = 0$ appears, the system is inconsistent and $b$ is not in the span. Otherwise it is, and any solution gives coefficients.

In other spaces the same idea works after translating to coordinates: a question about polynomials becomes a question about their coefficient lists, a question about $2 \times 2$ matrices becomes a question about four-entry lists. That translation is made precise in the section on coordinates.

Example 5.24 (Span membership in $R^{3}$ ). Is $b = (1, 5, 3)$ in $span {(1, 1, 1), (0, 2, 1)}$ ?

Solution. Row-reduce the augmented matrix:

111021153 \to 100021142 \to 100010120 .

The system is consistent with $c_{1} = 1$ , $c_{2} = 2$ . Check: $1 (1, 1, 1) + 2 (0, 2, 1) = (1, 5, 3)$ . Yes, $b$ is in the span.□

Example 5.25 (Spanning in a polynomial space). Does ${1 + x, 1 - x, x^{2}}$ span $P_{2}$ ?

Solution. We must hit an arbitrary $a + b x + c x^{2}$ . Write

α (1 + x) + β (1 - x) + γ x^{2} = (α + β) + (α - β) x + γ x^{2} .

Two polynomials are equal exactly when their coefficients agree, so we need $α + β = a$ , $α - β = b$ , $γ = c$ . Solving, $α = \frac{a + b}{2}$ , $β = \frac{a - b}{2}$ , $γ = c$ — always solvable. So the three polynomials span $P_{2}$ .

Sanity check on $p (x) = 3 + x + 5 x^{2}$ : $α = 2$ , $β = 1$ , $γ = 5$ , and indeed $2 (1 + x) + 1 (1 - x) + 5 x^{2} = 3 + x + 5 x^{2}$ .□

Example 5.26 (A span that misses). In $M_{2 \times 2}$ , describe $span {E_{11}, E_{22}}$ where $E_{ij}$ is the matrix with a $1$ in position $(i, j)$ and zeros elsewhere. Is $(1001)$ in it? Is $(0010)$ ?

Solution. A combination $a E_{11} + b E_{22}$ is the diagonal matrix $diag (a, b)$ , so the span is exactly the set of diagonal $2 \times 2$ matrices.

The identity is $diag (1, 1)$ , so yes, it is in the span, with $a = b = 1$ .

The matrix $E_{12}$ has a nonzero off-diagonal entry, and every element of the span has zeros off the diagonal, so it is not in the span. The span is a subspace of $M_{2 \times 2}$ of dimension $2$ , sitting inside a space of dimension $4$ .□

Pitfall. "Span" is a set, not a number, and "spans" is a verb with a target. The sentence "these vectors span $3$ " is meaningless; either they span a specific space, or their span has dimension $3$ . Also: a set can span $V$ while being wildly redundant. Spanning says nothing about independence.

Exercises for §5.4 →

5.5Linear independence

Definition 5.27 (Linear independence). Vectors $v_{1}, \dots, v_{k}$ in $V$ are linearly independent if the only scalars with

c_{1} v_{1} + \dots + c_{k} v_{k} = 0

are $c_{1} = c_{2} = \dots = c_{k} = 0$ . Otherwise they are linearly dependent, and any choice of scalars not all zero satisfying the equation is called a dependence relation.

The definition is about the only solution being trivial. There is always the trivial solution; independence says there is no other. An equivalent formulation makes the meaning plainer.

Proposition 5.28 (Independence as unique representation). The vectors $v_{1}, \dots, v_{k}$ are independent if and only if every vector in their span is a linear combination of them in exactly one way.

Proof. Suppose they are independent and $\sum c_{i} v_{i} = \sum d_{i} v_{i}$ . Subtracting, $\sum (c_{i} - d_{i}) v_{i} = 0$ , so every $c_{i} - d_{i} = 0$ and the representations coincide. Conversely, if representations are unique then in particular $0$ has only the representation with all coefficients $0$ , which is independence.∎

Lemma 5.29 (Linear dependence lemma). Suppose $v_{1}, \dots, v_{k}$ are linearly dependent and $v_{1} \neq = 0$ . Then there is an index $j \geq 2$ with

v_{j} \in span {v_{1}, \dots, v_{j - 1}},

and removing $v_{j}$ from the list does not change the span.

Proof. Take a dependence relation $c_{1} v_{1} + \dots + c_{k} v_{k} = 0$ with the $c_{i}$ not all zero, and let $j$ be the largest index with $c_{j} \neq = 0$ . If $j = 1$ the relation reads $c_{1} v_{1} = 0$ with $c_{1} \neq = 0$ , forcing $v_{1} = 0$ , contrary to hypothesis. So $j \geq 2$ , and solving for $v_{j}$ ,

v_{j} = - \frac{c _{1}}{c _{j}} v_{1} - \dots - \frac{c _{j - 1}}{c _{j}} v_{j - 1},

which puts $v_{j}$ in the span of its predecessors. The span is unchanged by the redundancy proposition of the previous section (applied after reordering so that $v_{j}$ comes last).∎

This lemma is the engine of the chapter: it is what turns any spanning set into a basis, and it is the inductive step in the exchange lemma. Note how it uses division by $c_{j}$ — the field again.

Some facts fall straight out of the definition. Any list containing $0$ is dependent, since $1 \cdot 0$ together with zero coefficients elsewhere is a nontrivial relation. A single vector $v$ is independent exactly when $v \neq = 0$ . Two vectors are dependent exactly when one is a scalar multiple of the other. Any sublist of an independent list is independent, and any list containing a dependent sublist is dependent.

Intuition. Independence is the absence of redundancy in a set of instructions. "Go $3$ km east, then $2$ km north, then $4$ km northeast" is a redundant set of moves: the third is achievable with the first two, so you did not need it in your toolkit. If no instruction can be simulated by the others, the set is independent — each one buys you a genuinely new direction of travel.

Method 5.30 (Testing independence in $R^{n}$ ). Place the vectors as the columns of a matrix $A$ and row-reduce.

Independent $⟺$ every column is a pivot column $⟺$ $Null (A) = {0}$ $⟺$ $rank A = k$ .
If $A$ is square, independent $⟺$ $det A \neq = 0$ .
Any dependence relation is read off from a nonzero null-space vector.

Example 5.31 (Dependence in $R^{3}$ , with the relation). Are $v_{1} = (1, 0, 2)$ , $v_{2} = (0, 1, 3)$ , $v_{3} = (2, 1, 7)$ independent? If not, exhibit a dependence relation.

Solution. Row-reduce the matrix with these as columns:

102013217 \to 100013213 \to 100010210 .

Only two pivots, so the columns are dependent. The third column is free; setting $x_{3} = 1$ gives $x_{2} = - 1$ , $x_{1} = - 2$ , so $- 2 v_{1} - v_{2} + v_{3} = 0$ , i.e.

v_{3} = 2 v_{1} + v_{2} .

Check: $2 (1, 0, 2) + (0, 1, 3) = (2, 1, 7)$ ✓.□

Example 5.32 (Independence in $P_{2}$ ). Show that ${1, x, x^{2}}$ is linearly independent in $P_{2}$ , without appealing to coordinates.

Solution. Suppose $a + b x + c x^{2} = 0$ as a function, i.e. for every real $x$ . Evaluate at three points:

x = 0 : a = 0; x = 1 : a + b + c = 0; x = - 1 : a - b + c = 0.

From the first, $a = 0$ . Adding the last two gives $2 c = 0$ , so $c = 0$ ; subtracting gives $2 b = 0$ , so $b = 0$ . All coefficients vanish, so the set is independent.

The evaluation trick generalises: a nonzero polynomial of degree $\leq n$ has at most $n$ roots, so if it vanishes at $n + 1$ distinct points it is the zero polynomial. That single fact proves ${1, x, \dots, x^{n}}$ independent in $P_{n}$ in one line.□

Example 5.33 (Independence of exponentials). Show ${e^{x}, e^{2 x}}$ is independent in $F (R, R)$ .

Solution. Suppose $a e^{x} + b e^{2 x} = 0$ for all $x$ . Two arguments, either suffices.

Evaluation. At $x = 0$ : $a + b = 0$ . At $x = ln 2$ : $2 a + 4 b = 0$ . From the first $a = - b$ , so $- 2 b + 4 b = 0$ , giving $b = 0$ and then $a = 0$ .

Growth. Divide by $e^{2 x}$ to get $a e^{- x} + b = 0$ for all $x$ ; letting $x \to \infty$ gives $b = 0$ , and then $a e^{x} = 0$ forces $a = 0$ .

Either way the only relation is trivial. The same growth argument shows ${e^{λ_{1} x}, \dots, e^{λ_{k} x}}$ is independent for distinct exponents $λ_{i}$ — a fact that underlies the solution theory of linear differential equations.□

Remark (The Wronskian). For differentiable functions $f_{1}, \dots, f_{k}$ one can also differentiate the relation $\sum c_{i} f_{i} = 0$ repeatedly to get a linear system with coefficient matrix the Wronskian

W (x) = f_{1} (x) f_{1}^{'} (x) ⋮ f_{1}^{(k - 1)} (x) \dots \dots \dots f_{k} (x) f_{k}^{'} (x) ⋮ f_{k}^{(k - 1)} (x) .

If $det W (x_{0}) \neq = 0$ for even one point $x_{0}$ , the only solution is $c = 0$ and the functions are independent. For $f_{1} = e^{x}$ , $f_{2} = e^{2 x}$ the Wronskian at $x = 0$ is $det (1112) = 1 \neq = 0$ , confirming the example. The converse fails: a vanishing Wronskian does not prove dependence.

Pitfall. Independence in a function space means the relation holds for every input, not at one convenient point. The functions $x$ and $x^{2}$ agree at $x = 0$ and at $x = 1$ , yet ${x, x^{2}}$ is independent — a relation $a x + b x^{2} = 0$ must hold identically, and evaluating at $x = 1$ and $x = 2$ forces $a = b = 0$ .

Exercises for §5.5 →

5.6Bases

Definition 5.34 (Basis). A list $B = (b_{1}, \dots, b_{n})$ of vectors in $V$ is a basis of $V$ if it is linearly independent and spans $V$ .

Theorem 5.35 (Unique representation). $B = (b_{1}, \dots, b_{n})$ is a basis of $V$ if and only if every $v \in V$ can be written

v = c_{1} b_{1} + \dots + c_{n} b_{n}

for exactly one choice of scalars $c_{1}, \dots, c_{n}$ .

Proof. If $B$ is a basis, spanning gives at least one representation and independence gives at most one, by the unique-representation proposition. Conversely, existence of a representation for every $v$ is spanning, and uniqueness applied to $v = 0$ gives independence.∎

This theorem is why a basis is called a coordinate system: choosing $B$ attaches to each vector an unambiguous list of numbers. A basis is simultaneously the smallest spanning set and the largest independent set, which the next two theorems make precise.

Here are the bases to memorise.

Notation (Standard bases).

$R^{n}$ : the standard basis $e_{1}, \dots, e_{n}$ , where $e_{i}$ has a $1$ in slot $i$ and zeros elsewhere. Size $n$ .
$P_{n}$ : the monomial basis $1, x, x^{2}, \dots, x^{n}$ . Size $n + 1$ , not $n$ .
$M_{m \times n}$ : the matrix units $E_{ij}$ , a single $1$ in position $(i, j)$ . Size $mn$ .
${0}$ : the empty list. Size $0$ .
$P$ , $C [a, b]$ , $R^{\infty}$ : no finite basis exists; these spaces are infinite-dimensional.

Intuition. A basis is the shortest possible set of building blocks that still builds everything. Lego bricks of one shape can build a wall but not a roof — not spanning. Throwing in a duplicate shape adds nothing — not independent. A basis is the catalogue with no gaps and no duplicates, and the unique-representation theorem says the build instructions for any object are then unambiguous.

Theorem 5.36 (Spanning sets contain bases). Every finite spanning list of a vector space $V$ can be reduced to a basis of $V$ by deleting some (possibly no) of its vectors. Consequently every finite-dimensional vector space has a basis.

Proof. Let $v_{1}, \dots, v_{m}$ span $V$ . Run through the list from left to right. At step $j$ , delete $v_{j}$ if $v_{j} \in span {the vectors kept so far}$ ; otherwise keep it. (In particular $v_{1}$ is deleted precisely when it is $0$ , since the span of the empty list is ${0}$ .)

Each deletion removes a vector lying in the span of the retained predecessors, so by the redundancy proposition the span of the retained list together with the not-yet-processed vectors is unchanged at every step. After the last step the retained list still spans $V$ .

The retained list is independent: if it were dependent, the linear dependence lemma would produce a retained vector lying in the span of the retained vectors before it — but such a vector was deleted, not retained. (The lemma applies because the first retained vector is nonzero.) So the retained list is an independent spanning list, i.e. a basis.∎

Theorem 5.37 (Every independent list extends to a basis). Let $V$ be finite-dimensional and let $u_{1}, \dots, u_{k}$ be linearly independent in $V$ . Then there are vectors $w_{1}, \dots, w_{r} \in V$ such that $u_{1}, \dots, u_{k}, w_{1}, \dots, w_{r}$ is a basis of $V$ .

Proof. Since $V$ is finite-dimensional it has a finite spanning list $v_{1}, \dots, v_{m}$ . Consider the combined list

u_{1}, \dots, u_{k}, v_{1}, \dots, v_{m},

which certainly spans $V$ . Apply the reduction procedure of the previous theorem to it. No $u_{j}$ is ever deleted: at the moment $u_{j}$ is processed, the retained vectors are exactly $u_{1}, \dots, u_{j - 1}$ , and if $u_{j}$ lay in their span the list $u_{1}, \dots, u_{j}$ would be dependent, contradicting independence. So the resulting basis contains all the $u_{j}$ together with some of the $v_{i}$ .∎

Example 5.38 (Reducing a spanning set). The list $v_{1} = (1, 1, 0)$ , $v_{2} = (2, 2, 0)$ , $v_{3} = (0, 1, 1)$ , $v_{4} = (1, 2, 1)$ spans a subspace $U$ of $R^{3}$ . Reduce it to a basis and give $dim U$ .

Solution. Process left to right. Keep $v_{1}$ , which is nonzero. Next, $v_{2} = 2 v_{1}$ lies in the span of what is kept, so delete it. Next, $v_{3}$ is not a multiple of $v_{1}$ (look at the third coordinate), so keep it. Finally $v_{4} = (1, 2, 1) = v_{1} + v_{3}$ , so delete it.

Basis: ${(1, 1, 0), (0, 1, 1)}$ , and $dim U = 2$ .

Sanity check by the column method: put the four vectors as columns and row-reduce; the pivots land in columns $1$ and $3$ , agreeing with the vectors retained. $U$ is the plane through the origin spanned by these two vectors.□

Example 5.39 (Extending an independent set). Extend ${(1, 1, 0, 0), (0, 1, 1, 0)}$ to a basis of $R^{4}$ .

Solution. Append the standard basis and reduce: consider $(1, 1, 0, 0), (0, 1, 1, 0), e_{1}, e_{2}, e_{3}, e_{4}$ .

Keep the first two (independent, as neither is a multiple of the other). Is $e_{1} = (1, 0, 0, 0)$ in their span? A combination $a (1, 1, 0, 0) + b (0, 1, 1, 0)$ has third coordinate $b$ , so $b = 0$ ; then the second coordinate is $a = 0$ , and the first is $0 \neq = 1$ . Not in the span — keep $e_{1}$ .

Now $e_{2} = (1, 1, 0, 0) - e_{1}$ is in the span, so delete it. Likewise $e_{3} = (0, 1, 1, 0) - (1, 1, 0, 0) + e_{1}$ is in the span, so delete it. Finally $e_{4}$ has a nonzero fourth coordinate while everything kept so far has fourth coordinate $0$ , so keep it.

Basis: ${(1, 1, 0, 0), (0, 1, 1, 0), e_{1}, e_{4}}$ . Sanity check: four vectors in $R^{4}$ , and the matrix with these as columns has determinant $\pm 1 \neq = 0$ .□

Example 5.40 (A basis for a matrix subspace). Find a basis for the space $S$ of symmetric $2 \times 2$ real matrices and for the space $T$ of trace-zero $2 \times 2$ real matrices.

Solution. A symmetric matrix is $(a b b c) = a (1000) + b (0110) + c (0001)$ , so those three matrices span $S$ . They are independent: if the combination is the zero matrix, then reading off the $(1, 1)$ , $(1, 2)$ and $(2, 2)$ entries gives $a = b = c = 0$ . So $dim S = 3$ .

A trace-zero matrix is $(a c b - a) = a (10 0 - 1) + b (0010) + c (0100)$ , and the same entry-reading argument gives independence. So $dim T = 3$ .

Sanity check: each space is cut out of the $4$ -dimensional space $M_{2 \times 2}$ by one linear equation ( $b = c$ ; $a_{11} + a_{22} = 0$ ), and one equation costs one dimension.□

Pitfall. $P_{n}$ has dimension $n + 1$ , not $n$ . The basis $1, x, \dots, x^{n}$ has $n + 1$ members because the constants count. This off-by-one is the most reliable source of lost marks in the subject.

Exercises for §5.6 →

5.7Dimension

Everything so far has quietly assumed that "the number of vectors in a basis" is a property of the space rather than of the basis. That needs proof, and the proof rests on one counting lemma.

Lemma 5.41 (Steinitz exchange lemma). In a vector space $V$ , suppose $u_{1}, \dots, u_{k}$ are linearly independent and $w_{1}, \dots, w_{m}$ span $V$ . Then $k \leq m$ .

Proof. We show by induction on $j = 0, 1, \dots, k$ that after reordering the $w$ 's, the list

u_{1}, \dots, u_{j}, w_{j + 1}, \dots, w_{m}

spans $V$ . In particular $j \leq m$ at every stage, which for $j = k$ gives the claim.

The case $j = 0$ is the hypothesis that the $w$ 's span. Suppose the statement holds for some $j < k$ . Then $u_{j + 1}$ lies in the span of $u_{1}, \dots, u_{j}, w_{j + 1}, \dots, w_{m}$ , so there is a relation

u_{j + 1} = a_{1} u_{1} + \dots + a_{j} u_{j} + b_{j + 1} w_{j + 1} + \dots + b_{m} w_{m} .

Not every $b_{i}$ can be zero: otherwise $u_{j + 1}$ would be a combination of $u_{1}, \dots, u_{j}$ , contradicting the independence of the $u$ 's. In particular there is at least one $w$ left, so $j + 1 \leq m$ . Reorder so that $b_{j + 1} \neq = 0$ and solve:

w_{j + 1} = \frac{1}{b _{j + 1}} (u_{j + 1} - i \leq j \sum a_{i} u_{i} - i > j + 1 \sum b_{i} w_{i}) .

So $w_{j + 1}$ lies in the span of $u_{1}, \dots, u_{j + 1}, w_{j + 2}, \dots, w_{m}$ ; adjoining it to that list therefore does not enlarge the span, and the enlarged list spans $V$ by the inductive hypothesis. Hence $u_{1}, \dots, u_{j + 1}, w_{j + 2}, \dots, w_{m}$ spans $V$ , completing the induction.∎

Read the lemma as a slogan: an independent list is never longer than a spanning list. Every counting theorem below is a corollary of that one sentence.

Theorem 5.42 (Dimension is well defined). Any two bases of a finite-dimensional vector space $V$ have the same number of vectors. That common number is the dimension $dim V$ .

Proof. Let $B$ and $C$ be bases with $∣ B ∣ = k$ and $∣ C ∣ = m$ . Since $B$ is independent and $C$ spans, the exchange lemma gives $k \leq m$ . Swapping the roles gives $m \leq k$ . Hence $k = m$ .∎

From the standard bases listed earlier we read off

dim R^{n} = n, dim P_{n} = n + 1, dim M_{m \times n} = mn, dim {0} = 0,

and $dim C$ is $1$ as a complex vector space but $2$ as a real one — the field of scalars is part of the data, and the basis ${1, i}$ over $R$ shows why.

Corollary 5.43 (Counting shortcuts). Let $dim V = n$ . Then:

any list of more than $n$ vectors in $V$ is dependent;
any list of fewer than $n$ vectors fails to span $V$ ;
an independent list of exactly $n$ vectors is a basis;
a spanning list of exactly $n$ vectors is a basis.

Proof. (1) and (2) are the exchange lemma applied against a basis, which is both independent and spanning of size $n$ .

(3) Let $u_{1}, \dots, u_{n}$ be independent. Extend it to a basis by the extension theorem; the resulting basis has size $n$ by the dimension theorem, so nothing was added and the original list was already a basis.

(4) Let $w_{1}, \dots, w_{n}$ span $V$ . Reduce it to a basis by the reduction theorem; the resulting basis has size $n$ , so nothing was deleted.∎

Parts (3) and (4) are enormous labour-savers: to check that $n$ specific vectors form a basis of an $n$ -dimensional space, verify either independence or spanning, never both.

Theorem 5.44 (Dimension of a subspace). Let $V$ be finite-dimensional and $U$ a subspace of $V$ . Then $U$ is finite-dimensional, $dim U \leq dim V$ , and $dim U = dim V$ if and only if $U = V$ .

Proof. Any independent list in $U$ is an independent list in $V$ , so by the exchange lemma it has length at most $dim V$ . Build an independent list in $U$ greedily: start with the empty list and, as long as the current independent list $u_{1}, \dots, u_{j}$ does not span $U$ , pick $u_{j + 1} \in U$ outside its span; the extended list is still independent, because a relation involving $u_{j + 1}$ with a nonzero coefficient would place $u_{j + 1}$ in the span of the others. The process must stop after at most $dim V$ steps, and when it stops the list spans $U$ and is independent — a basis of $U$ of size at most $dim V$ . Hence $U$ is finite-dimensional with $dim U \leq dim V$ .

If $U = V$ the dimensions agree. Conversely if $dim U = dim V = n$ , take a basis of $U$ ; it is an independent list of $n$ vectors in $V$ , hence a basis of $V$ by the counting corollary, so $V = span (basis of U) = U$ .∎

The last clause deserves emphasis: a subspace of the same dimension is the whole space. It converts a dimension count into a set equality and is used constantly — for instance to prove two subspaces equal when one obviously sits inside the other.

This also finally justifies the classification of subspaces of $R^{3}$ : a subspace has dimension $0$ , $1$ , $2$ or $3$ , and these are the zero space, lines through the origin, planes through the origin, and $R^{3}$ itself. There is nothing else, and no counting was needed beyond the theorem above.

Theorem 5.45 (Dimension of a sum). If $U$ and $W$ are finite-dimensional subspaces of a vector space $V$ , then

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

Proof. Let $x_{1}, \dots, x_{p}$ be a basis of $U \cap W$ , so $dim (U \cap W) = p$ . Since $U \cap W$ is a subspace of $U$ , extend that list to a basis

x_{1}, \dots, x_{p}, u_{1}, \dots, u_{q}

of $U$ , so $dim U = p + q$ ; and extend it also to a basis $x_{1}, \dots, x_{p}, w_{1}, \dots, w_{r}$ of $W$ , so $dim W = p + r$ . We claim

L = (x_{1}, \dots, x_{p}, u_{1}, \dots, u_{q}, w_{1}, \dots, w_{r})

is a basis of $U + W$ ; its length is $p + q + r = (p + q) + (p + r) - p$ , which is the formula.

Spanning. Any element of $U + W$ is $u + w$ ; expand $u$ in the basis of $U$ and $w$ in the basis of $W$ , and every term appearing is in $L$ .

Independence. Suppose

i \sum a_{i} x_{i} + j \sum b_{j} u_{j} + k \sum c_{k} w_{k} = 0 .

Set $z = \sum_{k} c_{k} w_{k}$ . Then $z = - \sum a_{i} x_{i} - \sum b_{j} u_{j} \in U$ , and also $z \in W$ , so $z \in U \cap W$ and therefore $z = \sum_{i} d_{i} x_{i}$ for some scalars $d_{i}$ . Comparing the two expressions for $z$ ,

k \sum c_{k} w_{k} - i \sum d_{i} x_{i} = 0,

a relation among the basis $x_{1}, \dots, x_{p}, w_{1}, \dots, w_{r}$ of $W$ ; hence every $c_{k} = 0$ (and every $d_{i} = 0$ ). The original relation now reads $\sum a_{i} x_{i} + \sum b_{j} u_{j} = 0$ , a relation among a basis of $U$ , so all $a_{i}$ and $b_{j}$ vanish too.∎

Corollary 5.46 (Dimension of a direct sum). If the sum is direct then $dim (U \oplus W) = dim U + dim W$ . Conversely, if $U, W$ are finite-dimensional and $dim (U + W) = dim U + dim W$ , the sum is direct.

Proof. Both directions follow from the formula: the sum is direct exactly when $U \cap W = {0}$ , which for finite-dimensional subspaces is exactly $dim (U \cap W) = 0$ .∎

Intuition. The sum formula is inclusion–exclusion for dimensions. Two planes through the origin in $R^{3}$ each have dimension $2$ , and $2 + 2 = 4$ exceeds $3$ — so they must overlap in at least one dimension. They do: two distinct planes through the origin always meet in a line. The formula turns "counting twice" into a geometric prediction.

Example 5.47 (Two planes in $R^{4}$ ). In $R^{4}$ , let $U = span {(1, 0, 0, 0), (0, 1, 0, 0)}$ and $W = span {(0, 1, 0, 0), (0, 0, 1, 0)}$ . Compute $dim (U \cap W)$ , $dim (U + W)$ , and decide whether the sum is direct.

Solution. A vector of $U$ is $(a, b, 0, 0)$ and a vector of $W$ is $(0, c, d, 0)$ . For these to coincide we need $a = 0$ and $d = 0$ , leaving $(0, b, 0, 0)$ . So $U \cap W = span {(0, 1, 0, 0)}$ and $dim (U \cap W) = 1$ .

By the formula, $dim (U + W) = 2 + 2 - 1 = 3$ . Indeed $U + W = {(x, y, z, 0)}$ , which is $3$ -dimensional.

The sum is not direct, since the intersection is not trivial — equivalently $3 \neq = 2 + 2$ .□

Example 5.48 (Forcing a nontrivial intersection). Let $U$ and $W$ be subspaces of $R^{7}$ with $dim U = 4$ and $dim W = 5$ . What is the smallest possible value of $dim (U \cap W)$ ?

Solution. $U + W$ is a subspace of $R^{7}$ , so $dim (U + W) \leq 7$ . By the sum formula,

dim (U \cap W) = dim U + dim W - dim (U + W) \geq 4 + 5 - 7 = 2.

So the intersection has dimension at least $2$ , and this is attained: take $U = span {e_{1}, e_{2}, e_{3}, e_{4}}$ and $W = span {e_{3}, e_{4}, e_{5}, e_{6}, e_{7}}$ , whose intersection is $span {e_{3}, e_{4}}$ . Minimum: $2$ .□

Example 5.49 (Dimension of a polynomial subspace). Let $U = {p \in P_{3} : p (1) = 0}$ . Find $dim U$ .

Solution. $U$ is a subspace (the condition is linear and homogeneous). A polynomial of degree at most $3$ vanishing at $1$ factors as $p (x) = (x - 1) q (x)$ with $de g q \leq 2$ , and conversely every such product lies in $U$ . The map $q \mapsto (x - 1) q$ therefore carries $P_{2}$ onto $U$ , and it sends the basis $1, x, x^{2}$ to

x - 1, x^{2} - x, x^{3} - x^{2},

which span $U$ and are independent (their degrees are $1, 2, 3$ , so a nontrivial relation would have a nonzero leading coefficient in its top degree). Hence $dim U = 3$ .

Sanity check: $U$ is cut out of the $4$ -dimensional space $P_{3}$ by one nontrivial linear condition, which costs exactly one dimension. And $U \neq = P_{3}$ because $dim U = 3 < 4$ , consistent with $p (x) = 1$ lying outside $U$ .□

Exercises for §5.7 →

5.8Coordinates and the coordinate isomorphism

Unique representation turns a basis into a dictionary between an abstract space and a concrete list of numbers.

Definition 5.50 (Coordinate vector). Let $B = (b_{1}, \dots, b_{n})$ be a basis of $V$ over $F$ . For $v \in V$ write $v = c_{1} b_{1} + \dots + c_{n} b_{n}$ , which by the unique-representation theorem determines the $c_{i}$ uniquely. The coordinate vector of $v$ relative to $B$ is

[v]_{B} = c_{1} ⋮ c_{n} \in F^{n} .

A basis is an ordered list precisely because coordinates are: reordering the basis permutes the entries of every coordinate vector.

Theorem 5.51 (The coordinate map is an isomorphism). Let $B$ be a basis of an $n$ -dimensional space $V$ over $F$ . The map $Φ : V \to F^{n}$ , $Φ (v) = [v]_{B}$ , is a bijection satisfying

[u + v]_{B} = [u]_{B} + [v]_{B}, [c v]_{B} = c [v]_{B} .

Consequently $V ≅ F^{n}$ : every $n$ -dimensional space over $F$ is a relabelled copy of $F^{n}$ .

Proof. Linearity: if $u = \sum a_{i} b_{i}$ and $v = \sum c_{i} b_{i}$ then $u + v = \sum (a_{i} + c_{i}) b_{i}$ , and by uniqueness this is the representation of $u + v$ , so its coordinate vector is the sum of the coordinate vectors. The same argument with $c v = \sum (c a_{i}) b_{i}$ gives the second identity.

Injective: if $[v]_{B} = 0$ then $v = \sum 0 \cdot b_{i} = 0$ ; combined with linearity, $Φ (u) = Φ (v)$ implies $Φ (u - v) = 0$ and so $u = v$ .

Surjective: given $(c_{1}, \dots, c_{n}) \in F^{n}$ , the vector $\sum c_{i} b_{i} \in V$ has exactly those coordinates.∎

Corollary 5.52 (Structure transfers through coordinates). With $B$ fixed, vectors $v_{1}, \dots, v_{k} \in V$ are linearly independent if and only if their coordinate vectors $[v_{1}]_{B}, \dots, [v_{k}]_{B}$ are independent in $F^{n}$ ; they span $V$ if and only if their coordinate vectors span $F^{n}$ ; and $v \in span {v_{i}}$ if and only if $[v]_{B} \in span {[v_{i}]_{B}}$ .

Proof. $Φ$ carries the linear combination $\sum c_{i} v_{i}$ to $\sum c_{i} [v_{i}]_{B}$ , and $Φ (x) = 0$ only for $x = 0$ . So a relation on one side corresponds to a relation on the other with the same coefficients, and a representation on one side to a representation on the other.∎

This is what the abstraction buys. Any question about independence, span, basis or dimension in any $n$ -dimensional space — polynomials, matrices, solutions of a differential equation — becomes, after a choice of basis, a question about columns of a matrix in $F^{n}$ , answerable by row reduction. No new machinery is ever needed.

Intuition. A basis is a language, and the coordinate map is a translator. The polynomial $3 + 2 x - x^{2}$ and the column $(3, 2, - 1)$ are the same idea in two languages; the dictionary is the monomial basis. Switching to a different basis is switching to a different language about the same object, and the object does not change — only its spelling does.

Example 5.53 (Coordinates in a polynomial space). Find $[p]_{B}$ for $p (x) = 5 - 3 x + 2 x^{2}$ relative to (a) the monomial basis $M = (1, x, x^{2})$ and (b) the basis $B = (1, 1 + x, 1 + x + x^{2})$ of $P_{2}$ .

Solution. (a) Immediate: $[p]_{M} = (5, - 3, 2)$ .

(b) Solve $a (1) + b (1 + x) + c (1 + x + x^{2}) = 5 - 3 x + 2 x^{2}$ . Comparing coefficients from the top down:

x^{2} : c = 2; x^{1} : b + c = - 3 \Rightarrow b = - 5; x^{0} : a + b + c = 5 \Rightarrow a = 8.

So $[p]_{B} = (8, - 5, 2)$ .

Check: $8 + (- 5) (1 + x) + 2 (1 + x + x^{2}) = (8 - 5 + 2) + (- 5 + 2) x + 2 x^{2} = 5 - 3 x + 2 x^{2}$ ✓. Note that the same vector has different coordinates in different bases; the coordinates are a property of the pair (vector, basis).□

Example 5.54 (Independence decided by coordinates). Are the matrices $A_{1} = (1021)$ , $A_{2} = (0110)$ , $A_{3} = (2 - 2 32)$ independent in $M_{2 \times 2}$ ?

Solution. Use the basis $(E_{11}, E_{12}, E_{21}, E_{22})$ , so that a matrix corresponds to the column of its entries read $a_{11}, a_{12}, a_{21}, a_{22}$ :

[A_{1}] = (1, 2, 0, 1), [A_{2}] = (0, 1, 1, 0), [A_{3}] = (2, 3, - 2, 2) .

Look for a relation. Trying $A_{3} = α A_{1} + β A_{2}$ : the first entry gives $α = 2$ , the third gives $β = - 2$ , and then the second entry is $2 (2) + (- 2) (1) = 2 \neq = 3$ . So no such relation, and the general relation $c_{1} [A_{1}] + c_{2} [A_{2}] + c_{3} [A_{3}] = 0$ reduces by the first and third coordinates to $c_{1} = - 2 c_{3}$ , $c_{2} = 2 c_{3}$ , and then the second coordinate gives $- 4 c_{3} + 2 c_{3} + 3 c_{3} = c_{3} = 0$ , hence all $c_{i} = 0$ .

The matrices are independent, and $span {A_{1}, A_{2}, A_{3}}$ is a $3$ -dimensional subspace of the $4$ -dimensional space $M_{2 \times 2}$ .□

Definition 5.55 (Change-of-coordinates matrix). Let $B = (b_{1}, \dots, b_{n})$ and $C$ be bases of the same space $V$ . The change-of-coordinates matrix from $B$ to $C$ is the $n \times n$ matrix

P_{C \leftarrow B} = [[b_{1}]_{C} [b_{2}]_{C} \dots [b_{n}]_{C}],

whose columns are the $C$ -coordinates of the $B$ -basis vectors.

Theorem 5.56 (Change of coordinates). For every $v \in V$ ,

[v]_{C} = P_{C \leftarrow B} [v]_{B} .

The matrix $P_{C \leftarrow B}$ is invertible, with inverse $P_{B \leftarrow C}$ .

Proof. Write $v = \sum_{i} c_{i} b_{i}$ with $(c_{i}) = [v]_{B}$ . Applying the coordinate map for $C$ and using its linearity,

[v]_{C} = i \sum c_{i} [b_{i}]_{C},

which is exactly the matrix $P_{C \leftarrow B}$ times the column $(c_{i})$ .

For invertibility, the same identity with the roles of $B$ and $C$ swapped gives $[v]_{B} = P_{B \leftarrow C} [v]_{C} = P_{B \leftarrow C} P_{C \leftarrow B} [v]_{B}$ for every $v$ . As $[v]_{B}$ ranges over all of $F^{n}$ , the product $P_{B \leftarrow C} P_{C \leftarrow B}$ fixes every column vector and is therefore $I_{n}$ .∎

Method 5.57 (Computing a change of coordinates in $R^{n}$ ). If $B = (b_{i})$ and $C = (c_{i})$ are bases of $R^{n}$ , let $B = [b_{1} \dots b_{n}]$ and $C = [c_{1} \dots c_{n}]$ be the matrices with those columns. Then $v = B [v]_{B} = C [v]_{C}$ , so

P_{C \leftarrow B} = C^{- 1} B .

In practice, row-reduce $[C ∣ B]$ to $[I ∣ C^{- 1} B]$ .

Example 5.58 (Changing basis in $R^{2}$ ). Let $B = ((1, 1), (1, - 1))$ and $C = ((1, 0), (1, 2))$ be bases of $R^{2}$ . Find $P_{C \leftarrow B}$ and use it to find $[v]_{C}$ for the vector $v$ with $[v]_{B} = (3, 1)$ .

Solution. Express each $B$ -vector in $C$ . For $(1, 1) = a (1, 0) + b (1, 2)$ : the second coordinate gives $2 b = 1$ , so $b = \frac{1}{2}$ , and then $a + \frac{1}{2} = 1$ , so $a = \frac{1}{2}$ . For $(1, - 1) = a (1, 0) + b (1, 2)$ : $2 b = - 1$ gives $b = - \frac{1}{2}$ , then $a = \frac{3}{2}$ . Hence

P_{C \leftarrow B} = (\frac{1}{2} \frac{1}{2} \frac{3}{2} - \frac{1}{2}) .

Then

[v]_{C} = (\frac{1}{2} \frac{1}{2} \frac{3}{2} - \frac{1}{2}) (31) = (31) .

Sanity check directly: $[v]_{B} = (3, 1)$ means $v = 3 (1, 1) + 1 (1, - 1) = (4, 2)$ ; and $3 (1, 0) + 1 (1, 2) = (4, 2)$ ✓. The coincidence that both coordinate vectors equal $(3, 1)$ is an accident of these particular bases, not a general phenomenon.□

Pitfall. Read the arrow. $P_{C \leftarrow B}$ takes $B$ -coordinates in and produces $C$ -coordinates out, and its columns are the $B$ -vectors written in $C$ . Building the matrix the other way round is the standard error; the cure is to check it on a single basis vector, where the answer must be a standard basis column.

Exercises for §5.8 →

5.9Column space, row space and null space

Every matrix carries three subspaces with it, and almost every question about a linear system is a question about one of them.

Definition 5.59 (The subspaces of a matrix). Let $A$ be an $m \times n$ matrix over $F$ . Its

column space $Col (A) = span {columns of A} = {A x : x \in F^{n}} \subseteq F^{m}$ ;
row space $Row (A) = span {rows of A} = Col (A^{T}) \subseteq F^{n}$ ;
null space $Null (A) = {x \in F^{n} : A x = 0} \subseteq F^{n}$ .

Proposition 5.60 (All three are subspaces). $Col (A)$ is a subspace of $F^{m}$ ; $Row (A)$ and $Null (A)$ are subspaces of $F^{n}$ .

Proof. Column and row spaces are spans, hence subspaces by the span theorem. For the null space: $A 0 = 0$ , and if $A x = A y = 0$ then $A (c x + d y) = c A x + d A y = 0$ by linearity of matrix multiplication. The one-step test applies.∎

The identity $Col (A) = {A x}$ is worth unwinding, since it is the bridge between the two ways of reading a matrix: $A x$ is by definition $x_{1} a_{1} + \dots + x_{n} a_{n}$ where $a_{i}$ are the columns, so the set of all $A x$ is exactly the set of all combinations of columns. Two consequences are immediate and constantly used:

A x = b is consistent ⟺ b \in Col (A),

A x = b has at most one solution ⟺ Null (A) = {0} .

For the second: if $A x_{1} = A x_{2} = b$ then $x_{1} - x_{2} \in Null (A)$ , and conversely adding a null vector to a solution gives another solution. So the full solution set of a consistent system is a single particular solution plus the whole null space — a translate of a subspace, which is why it is a subspace precisely when $b = 0$ .

Intuition. Picture $A$ as a machine. The column space is the set of outputs the machine can actually produce — its reachable catalogue. The null space is the set of inputs it destroys, mapping them to nothing. A machine with a big null space is throwing information away; a machine whose null space is just $0$ keeps every distinction between its inputs.

Theorem 5.61 (Row operations preserve the row space and the null space). If $B$ is obtained from $A$ by elementary row operations, then $Row (B) = Row (A)$ and $Null (B) = Null (A)$ . The column space, by contrast, generally changes.

Proof. Each elementary operation replaces the rows of $A$ by linear combinations of them, so every row of $B$ lies in $Row (A)$ and hence $Row (B) \subseteq Row (A)$ ; since each operation is reversible by another elementary operation, the reverse inclusion holds too.

For the null space, row operations do not change the solution set of $A x = 0$ , which is the definition of $Null (A)$ — the operations correspond to left multiplication by an invertible matrix $E$ , and $E A x = 0$ has the same solutions as $A x = 0$ .

That the column space changes is shown by an example: $A = (11)$ row-reduces to $B = (10)$ , and $Col (A)$ is the line $y = x$ while $Col (B)$ is the $x$ -axis. What is preserved is which columns are pivot columns, and hence the dimension of the column space, as the next theorem records.∎

Method 5.62 (Bases for the three subspaces). Row-reduce $A$ to an echelon form $R$ .

Column space: take the columns of the original $A$ in the pivot positions. Never the columns of $R$ .
Row space: take the nonzero rows of $R$ .
Null space: solve $R x = 0$ , write the general solution with one free variable at a time, and read off the resulting vectors.

Proof. For the column space: the dependence relations among the columns are precisely the vectors of $Null (A)$ , and row reduction does not change $Null (A)$ ; so a set of columns of $A$ is independent exactly when the corresponding columns of $R$ are. In $R$ the pivot columns are independent and every non-pivot column is a combination of the pivot columns to its left. Transporting both facts back to $A$ shows the pivot columns of $A$ are independent and span $Col (A)$ .

For the row space: $Row (R) = Row (A)$ by the previous theorem, and the nonzero rows of an echelon matrix are independent — in any relation, look at the leftmost pivot position occurring among the rows with nonzero coefficient; only one row is nonzero in that column, so its coefficient must be $0$ , and induction finishes it.

For the null space: setting one free variable to $1$ and the others to $0$ produces vectors whose free-variable slots form the standard basis, so they are independent, and every solution is the corresponding combination of them.∎

Example 5.63 (All three subspaces of one matrix). For

A = 101213314

find bases for $Col (A)$ , $Row (A)$ and $Null (A)$ , and their dimensions.

Solution. Row-reduce. Row $3$ minus row $1$ gives $(0, 1, 1)$ ; subtracting row $2$ makes it zero. Clearing above the second pivot:

R = 100010110 .

Pivots in columns $1$ and $2$ , so $rank A = 2$ .

$Col (A)$ : the original columns $1$ and $2$ , namely $(1, 0, 1)$ and $(2, 1, 3)$ . Dimension $2$ .

$Row (A)$ : the nonzero rows of $R$ , namely $(1, 0, 1)$ and $(0, 1, 1)$ . Dimension $2$ .

$Null (A)$ : column $3$ is free. With $x_{3} = t$ , the equations $x_{1} + x_{3} = 0$ and $x_{2} + x_{3} = 0$ give $x_{1} = x_{2} = - t$ , so the solution is $t (- 1, - 1, 1)$ and ${(- 1, - 1, 1)}$ is a basis. Dimension $1$ .

Check: $A (- 1, - 1, 1)$ has entries $- 1 - 2 + 3 = 0$ , $0 - 1 + 1 = 0$ , $- 1 - 3 + 4 = 0$ ✓. Also $2 + 1 = 3$ , the number of columns, as the Rank Theorem below demands.□

Example 5.64 (Reading a column space off a consistency question). For which $b$ is $(1, 2, b)$ in the column space of $A = 101011$ ?

Solution. $Col (A)$ is the span of $(1, 0, 1)$ and $(0, 1, 1)$ . Asking whether $(1, 2, b)$ lies in it is asking whether $c_{1} (1, 0, 1) + c_{2} (0, 1, 1) = (1, 2, b)$ has a solution. The first two coordinates force $c_{1} = 1$ and $c_{2} = 2$ , and the third then reads $b = c_{1} + c_{2} = 3$ .

So $b = 3$ , and for any other $b$ the system $A x = (1, 2, b)$ is inconsistent. Geometrically $Col (A)$ is the plane $x + y = z$ in $R^{3}$ , and $(1, 2, 3)$ lies on it.□

Pitfall. A basis for $Col (A)$ comes from the columns of $A$ , but a basis for $Row (A)$ comes from the rows of the reduced matrix. The asymmetry is not arbitrary: row operations preserve the row space but move the column space, so the reduced rows are still in the row space while the reduced columns need not be in the column space.

Exercises for §5.9 →

5.10Rank, nullity and the four fundamental subspaces

Definition 5.65 (Rank and nullity). For an $m \times n$ matrix $A$ , the rank is $rank A = dim Col (A)$ and the nullity is $nullity A = dim Null (A)$ .

Theorem 5.66 (Rank Theorem). For any $m \times n$ matrix $A$ ,

rank A + nullity A = n .

Proof. Row-reduce $A$ to an echelon form $R$ with $r$ pivots. By the basis recipe, $dim Col (A) = r$ , since the pivot columns of $A$ form a basis. Also by the recipe, $dim Null (A)$ equals the number of free variables, one basis vector per free column. Every one of the $n$ columns is either a pivot column or a free column, and never both, so $r + (n - r) = n$ , which is the claim.∎

Theorem 5.67 (Row rank equals column rank). For any matrix $A$ , $dim Row (A) = dim Col (A)$ ; equivalently $rank A^{T} = rank A$ .

Proof. Row-reduce $A$ to echelon form $R$ with $r$ pivots. The nonzero rows of $R$ form a basis of $Row (R) = Row (A)$ , and there are exactly $r$ of them, so $dim Row (A) = r$ . The pivot columns of $A$ form a basis of $Col (A)$ , and there are also exactly $r$ of them. Both dimensions equal the number of pivots, hence each other.∎

This is a genuinely surprising theorem. The row space and the column space usually live in different spaces — $R^{n}$ and $R^{m}$ — and consist of entirely different vectors; there is no reason from the outside that they should have the same dimension. The number of pivots is a single quantity that both computations happen to count, and the rank is best thought of as that number: the number of genuinely independent equations in the system, which is simultaneously the number of genuinely independent output directions.

Corollary 5.68 (The four fundamental subspaces). Let $A$ be $m \times n$ of rank $r$ . Then

dim Col (A) = r, dim Row (A) = r, dim Null (A) = n - r, dim Null (A^{T}) = m - r .

The row space and null space live in $F^{n}$ and their dimensions add to $n$ ; the column space and left null space live in $F^{m}$ and their dimensions add to $m$ .

Proof. The first three are the two previous theorems. For the fourth, apply the Rank Theorem to $A^{T}$ , which has $m$ columns: $rank A^{T} + nullity A^{T} = m$ , and $rank A^{T} = r$ by the row-rank theorem.∎

Theorem 5.69 (Fundamental theorem of linear algebra, orthogonality part). For a real $m \times n$ matrix $A$ ,

Null (A) = Row (A)^{⊥} in R^{n}, Null (A^{T}) = Col (A)^{⊥} in R^{m} .

Proof. $A x = 0$ says exactly that each row of $A$ has dot product zero with $x$ , that is, $x$ is orthogonal to every row, hence (by bilinearity of the dot product) to every combination of rows. Conversely a vector orthogonal to all rows satisfies $A x = 0$ . So $Null (A) = Row (A)^{⊥}$ . Applying this to $A^{T}$ , whose rows are the columns of $A$ , gives the second identity.∎

Combined with the dimension count, this says $R^{n} = Row (A) \oplus Null (A)$ and $R^{m} = Col (A) \oplus Null (A^{T})$ : each ambient space splits into a part the matrix handles faithfully and a part it annihilates. The orthogonality is developed properly in the chapter on orthogonality; the dimension bookkeeping above needs nothing beyond this chapter.

Intuition. A matrix of rank $r$ is, at bottom, an $r$ -dimensional machine wearing an $m \times n$ costume. It takes an $n$ -dimensional input, immediately discards an $(n - r)$ -dimensional slice of it (the null space), passes the surviving $r$ dimensions through faithfully, and deposits them in an $r$ -dimensional slice of the $m$ -dimensional output space. Everything else in $R^{m}$ — the other $m - r$ dimensions — is simply unreachable.

Theorem 5.70 (The Invertible Matrix Theorem, extended). For an $n \times n$ matrix $A$ the following are equivalent:

$A$ is invertible;
$A x = 0$ has only the trivial solution;
the columns of $A$ are linearly independent;
the columns of $A$ span $F^{n}$ ;
the columns of $A$ form a basis of $F^{n}$ ;
$Col (A) = F^{n}$ ;
$Row (A) = F^{n}$ ;
$rank A = n$ ;
$nullity A = 0$ ;
$det A \neq = 0$ .

Proof. (2) $⟺$ (3) is the definition of independence applied to the columns, since $A x$ is the combination of columns with coefficients $x_{i}$ . (2) $⟺$ (9) is the definition of nullity. (9) $⟺$ (8) is the Rank Theorem with $n$ columns. (8) $⟺$ (6): $Col (A)$ is a subspace of $F^{n}$ of dimension $rank A$ , and a subspace has full dimension if and only if it is the whole space. (6) $⟺$ (4) is the definition of the column space, and (3) with (4) is (5). (7) $⟺$ (8) by the row-rank theorem and the same full-dimension argument in $F^{n}$ . Finally (1) $⟺$ (2) and (1) $⟺$ (10) were proved in the chapters on matrix inverses and determinants.∎

Notice how much of that proof is pure dimension counting. The clause "a subspace of full dimension is the whole space" is used three times, and it is exactly the subspace-dimension theorem proved earlier in this chapter.

Example 5.71 (Rank and nullity from a shape). $A$ is a $4 \times 7$ matrix whose null space has dimension $4$ . Find $rank A$ , $dim Row (A)$ , $dim Null (A^{T})$ , and decide whether $A x = b$ is consistent for every $b \in R^{4}$ .

Solution. Rank Theorem with $n = 7$ columns: $rank A = 7 - 4 = 3$ .

$dim Row (A) = rank A = 3$ , by row rank equals column rank.

dim Null (A^{T}) = m - r = 4 - 3 = 1

Consistency for every $b$ would require $Col (A) = R^{4}$ , i.e. rank $4$ . The rank is $3$ , so $Col (A)$ is a $3$ -dimensional subspace of $R^{4}$ and there exist $b$ for which the system is inconsistent.□

Example 5.72 (Rank of a product and of an outer product). Let $u \in R^{m}$ and $v \in R^{n}$ be nonzero. What is $rank (u v^{T})$ , and what is the nullity of $u v^{T}$ ?

Solution. The matrix $A = u v^{T}$ is $m \times n$ with $j$ -th column $v_{j} u$ . Every column is a multiple of $u$ , so $Col (A) \subseteq span {u}$ , giving $rank A \leq 1$ . Since some $v_{j} \neq = 0$ and $u \neq = 0$ , some column is nonzero, so $rank A = 1$ .

By the Rank Theorem the nullity is $n - 1$ . Concretely, $A x = u (v^{T} x) = (v \cdot x) u$ , which vanishes exactly when $x ⊥ v$ — the hyperplane orthogonal to $v$ , of dimension $n - 1$ ✓.□

Example 5.73 (Using dimension to prove an equality of spaces). Let $A$ be $5 \times 5$ with $rank A = 5$ and let $U = Col (A)$ . Prove $U = R^{5}$ without computing anything, and deduce that $A x = b$ has exactly one solution for every $b$ .

Solution. $U$ is a subspace of $R^{5}$ with $dim U = rank A = 5 = dim R^{5}$ . By the subspace-dimension theorem, a subspace of equal dimension is the whole space, so $U = R^{5}$ . Hence every $b$ lies in $Col (A)$ and the system is consistent.

For uniqueness, the Rank Theorem gives $nullity A = 5 - 5 = 0$ , so $Null (A) = {0}$ and any two solutions differ by a null vector, hence coincide. Exactly one solution for every $b$ — which is statement (1) of the Invertible Matrix Theorem in disguise.□

Summary. For an $m \times n$ matrix $A$ of rank $r$ : $Col (A)$ and $Null (A^{T})$ are subspaces of $F^{m}$ of dimensions $r$ and $m - r$ ; $Row (A)$ and $Null (A)$ are subspaces of $F^{n}$ of dimensions $r$ and $n - r$ . The system $A x = b$ is consistent for all $b$ iff $r = m$ , and has at most one solution iff $r = n$ .

Exercises for §5.10 →

Common Mistakes

Checking closure but not the zero vector, or vice versa. A subspace needs $0 \in U$ and closure under both operations. The fastest disqualifier is almost always the missing zero vector.
Assuming a set with an addition is a vector space. All eight axioms must hold for the operations you were handed. Axiom 5, $1 v = v$ , is the one that fails in the deceptive examples, and the additive identity need not be the number $0$ .
Writing $dim P_{n} = n$ . It is $n + 1$ : the basis $1, x, \dots, x^{n}$ has $n + 1$ elements.
Confusing spanning with independence. A spanning set may be redundant; an independent set may be too small. A basis is exactly both at once, and "I found $k$ independent vectors, so the dimension is $k$ " is only valid once you know they span, or once you know $dim V = k$ already.
Taking a basis for $Col (A)$ from the reduced matrix. Use the pivot positions to select columns of the original $A$ . The row space is the opposite: use the nonzero rows of the reduced matrix.
Calling $U + W$ a direct sum without checking $U \cap W = {0}$ . And with three or more summands, pairwise trivial intersections are not enough.
Forgetting that coordinates depend on the basis. $[v]_{B}$ is a statement about a pair, not about $v$ alone, and $P_{C \leftarrow B}$ has the $B$ -vectors written in $C$ as its columns, not the other way round.
Treating independence in a function space pointwise. $\sum c_{i} f_{i} = 0$ must hold at every point of the domain; agreement at one convenient point proves nothing.
Thinking a union of subspaces is a subspace. It is one only in the degenerate case where one contains the other.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed. This chapter also has a printable problem set: proofs, sketches and find-the-error work to do on paper, with full solutions on a separate page.

Practice this chapter Printable problem set