6. Vector Spaces
Chapters 2 to 5 treated vectors as lists of numbers in $\mathbb{R}^n$. This chapter keeps only the rules those lists obey, adding and scaling, and calls any set that obeys them a vector space. Polynomials, matrices, functions, signals, and bit strings can then be handled with the same tools as arrows in the plane. It develops subspaces, linear independence, bases, dimension, and coordinates. It ends with the four fundamental subspaces of a matrix, which give a complete structural picture of what $A\mathbf{x} = \mathbf{b}$ can and cannot do.
<a id="61-abstract-vector-spaces"></a>
6.1 Abstract Vector Spaces
This subchapter defines a vector space by a short list of axioms and surveys the standard examples. It then derives the first facts that follow from the axioms alone, and explains what changes when the scalars come from $\mathbb{C}$ or from another field.
Vector Space Axioms
Why it matters. Section 2.2 listed the algebraic rules for adding and scaling vectors in $\mathbb{R}^n$, and Section 4.1 observed that matrices obey exactly the same rules. So do polynomials, real-valued functions, infinite sequences, audio signals, and the solutions of a homogeneous differential equation. Proving "a set of $n + 1$ vectors in an $n$-dimensional space is dependent" separately for each of these would be wasteful. Instead, we name the rules, prove theorems using only the rules, and every object that obeys them inherits every theorem at once.
Analogy. Section 1.2 compared a field to a programming interface. A vector space is another interface, with two methods: add(u, v) and scale(c, v). $\mathbb{R}^n$, polynomials, and matrices are implementations. Any algorithm that calls only these two methods, such as forming linear combinations, Gaussian elimination on coordinates, or computing a span, works with every implementation. The axioms are the contract each implementation must honor.
Definition. Let $F$ be a field (Section 1.2), whose elements are called scalars. In this book $F$ is usually $\mathbb{R}$. A vector space over $F$ is a set $V$, whose elements are called vectors, together with two operations:
- addition, which takes $\mathbf{u}, \mathbf{v} \in V$ to a vector $\mathbf{u} + \mathbf{v} \in V$;
- scalar multiplication, which takes $c \in F$ and $\mathbf{v} \in V$ to a vector $c\mathbf{v} \in V$.
The operations must satisfy the following axioms for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ and all $a, b \in F$:
| Label | Axiom | Name |
|---|---|---|
| C1 | $\mathbf{u} + \mathbf{v} \in V$ | Closure under addition |
| C2 | $a\mathbf{u} \in V$ | Closure under scalar multiplication |
| A1 | $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ | Commutativity |
| A2 | $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$ | Associativity |
| A3 | There is a vector $\mathbf{0} \in V$ with $\mathbf{u} + \mathbf{0} = \mathbf{u}$ | Zero vector |
| A4 | For each $\mathbf{u}$ there is $-\mathbf{u} \in V$ with $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$ | Additive inverse |
| S1 | $a(\mathbf{u} + \mathbf{v}) = a\mathbf{u} + a\mathbf{v}$ | Distributivity over vector addition |
| S2 | $(a + b)\mathbf{u} = a\mathbf{u} + b\mathbf{u}$ | Distributivity over scalar addition |
| S3 | $a(b\mathbf{u}) = (ab)\mathbf{u}$ | Compatibility of multiplications |
| S4 | $1\mathbf{u} = \mathbf{u}$ | Scalar identity |
C1 and C2 are part of saying that the operations land in $V$. Many texts fold them into the word "operation" and list only the eight axioms A1 to S4. When you check a candidate space, closure is the axiom that fails most often, so it is listed explicitly here.
a vector space V over a field F
+----------------------------------------------------+
| add: V x V -> V (u, v) -> u + v |
| scale: F x V -> V (c, v) -> c v |
| zero: 0 in V neg: v -> -v |
| + the eight axioms A1-A4, S1-S4 |
+----------------------------------------------------+
^ ^ ^ ^
| | | |
R^n polynomials matrices functions R -> R
What the axioms do not say. The axioms mention no product of two vectors, no length, no angle, and no components. A vector is simply an element of a vector space. It need not be an arrow or a list of numbers. Lengths and angles return in Chapter 9 as additional structure (an inner product). Components return in Section 6.5, but only after a basis is chosen.
Every axiom does work. Each axiom rules out some "fake" vector space. For example, take $\mathbb{R}^2$ with the usual addition but the scalar multiplication $c(x, y) = (cx, 0)$. Every axiom holds except S4: $1(x, y) = (x, 0) \ne (x, y)$. Without S4, scaling could destroy information, and theorems such as "$c\mathbf{v} = \mathbf{0}$ implies $c = 0$ or $\mathbf{v} = \mathbf{0}$" would fail.
A surprising example. Let $V = \mathbb{R}_{>0}$, the positive real numbers, with
$$\mathbf{u} \oplus \mathbf{v} = uv, \qquad c \odot \mathbf{u} = u^c.$$
This is a vector space over $\mathbb{R}$. Its zero vector is the number $1$, since $u \oplus 1 = u$, and the "negative" of $u$ is $1/u$. Axiom S2 becomes $u^{a+b} = u^a u^b$, and S3 becomes $(u^b)^a = u^{ab}$. These are the laws of exponents. The logarithm turns this space into ordinary $\mathbb{R}$, which is why slide rules could multiply by adding lengths. The example shows that "vector", "zero", and "addition" are roles defined by the axioms, not particular objects.
How to check a candidate.
- Identify the set and the two operations precisely.
- Check closure (C1, C2). This is the most common failure.
- Find the zero vector and the additive inverses, and check A3 and A4.
- Check the remaining identities, usually by reducing them to known facts about numbers.
A single counterexample to any axiom disproves the claim. A proof must cover all vectors and scalars.
import math
import random
random.seed(0)
def close(u, v):
return all(math.isclose(x, y, rel_tol=1e-9, abs_tol=1e-9) for x, y in zip(u, v))
def check_axioms(add, scale, zero, neg, sample, trials=500):
"""Randomly test A1-A4 and S1-S4. A failure disproves an axiom; passing is evidence, not proof."""
failed = set()
for _ in range(trials):
u, v, w = sample(), sample(), sample()
a, b = random.uniform(-3, 3), random.uniform(-3, 3)
checks = {
"A1": close(add(u, v), add(v, u)),
"A2": close(add(add(u, v), w), add(u, add(v, w))),
"A3": close(add(u, zero), u),
"A4": close(add(u, neg(u)), zero),
"S1": close(scale(a, add(u, v)), add(scale(a, u), scale(a, v))),
"S2": close(scale(a + b, u), add(scale(a, u), scale(b, u))),
"S3": close(scale(a, scale(b, u)), scale(a * b, u)),
"S4": close(scale(1, u), u),
}
failed |= {name for name, ok in checks.items() if not ok}
return sorted(failed) or "all passed"
# Ordinary R^2
r2 = dict(add=lambda u, v: (u[0] + v[0], u[1] + v[1]),
scale=lambda c, u: (c * u[0], c * u[1]),
zero=(0.0, 0.0), neg=lambda u: (-u[0], -u[1]),
sample=lambda: (random.uniform(-5, 5), random.uniform(-5, 5)))
print(check_axioms(**r2)) # all passed
# Positive reals: "addition" is multiplication, "scaling" is exponentiation, zero vector is 1
pos = dict(add=lambda u, v: (u[0] * v[0],),
scale=lambda c, u: (u[0] ** c,),
zero=(1.0,), neg=lambda u: (1 / u[0],),
sample=lambda: (random.uniform(0.1, 5),))
print(check_axioms(**pos)) # all passed
# R^2 with the broken scaling c(x, y) = (cx, 0)
broken = dict(r2, scale=lambda c, u: (c * u[0], 0.0))
print(check_axioms(**broken)) # ['S4']: only the scalar identity fails
Key takeaways
- A vector space is a set with addition and scalar multiplication satisfying closure and eight axioms (A1 to A4, S1 to S4).
- "Vector" means "element of a vector space": polynomials, matrices, and functions qualify.
- The axioms say nothing about length, angle, products of vectors, or components.
- To disprove, find one failing axiom (usually closure); to prove, verify every axiom for all inputs.
- Unusual operations can still form a vector space, as with $(\mathbb{R}_{>0}, \cdot, \text{powers})$, whose zero vector is $1$.
🧪 Practice
- On $\mathbb{R}^2$, keep the usual addition but define $c(x, y) = (cx, y)$. Find an axiom that fails and give explicit numbers that violate it.
- For the positive reals with $u \oplus v = uv$ and $c \odot u = u^c$, verify axioms A4, S1, and S4 directly, and compute $2 \odot 3 \oplus (-1) \odot 6$.
- Is the set of $2 \times 2$ real matrices with determinant $0$, under the usual operations, a vector space? Justify your answer with a specific example.
- Interview: A teammate writes a randomized test harness, like the one above, for a new
Vectorclass, and all eight axioms pass on 10,000 random inputs. They conclude the class implements a vector space. What can and cannot be concluded, and what would you check in addition? Hint: random tests can only disprove; the harness never tests closure, and floating-point arithmetic satisfies A2 only approximately (Section 2.2).
Examples: R^n, Polynomials, Matrices, Functions
Why it matters. The definition only pays off if many familiar objects satisfy it. Recognizing a vector space when you meet one is a skill in its own right. Once you see that the solutions of $y'' + y = 0$ form a vector space, you know that two independent solutions describe all of them (Section 6.4). Once you see that grayscale images form a vector space, averaging and blending images become linear algebra.
The standard catalogue. In every example below, the operations are the "obvious" ones: componentwise, coefficientwise, entrywise, or pointwise.
| Space | Elements | $\mathbf{u} + \mathbf{v}$ and $c\mathbf{u}$ | Zero vector | Dimension (Section 6.4) |
|---|---|---|---|---|
| $\mathbb{R}^n$ | $n$-tuples $(x_1, \dots, x_n)$ | componentwise | $(0, \dots, 0)$ | $n$ |
| $\mathbb{P}_n$ | polynomials of degree $\le n$ | add/scale coefficients | the zero polynomial | $n + 1$ |
| $\mathbb{P}$ | all polynomials | add/scale coefficients | the zero polynomial | infinite |
| $\mathbb{R}^{m \times n}$ | $m \times n$ matrices | entrywise | $O_{m \times n}$ | $mn$ |
| $\mathcal{F}(S)$ | all functions $S \to \mathbb{R}$ | pointwise | the function $x \mapsto 0$ | $\lvert S \rvert$ if $S$ is finite |
| $C[a, b]$ | continuous functions on $[a, b]$ | pointwise | the function $x \mapsto 0$ | infinite |
| $\mathbb{R}^\infty$ | sequences $(x_1, x_2, \dots)$ | termwise | $(0, 0, \dots)$ | infinite |
| ${\mathbf{0}}$ | a single vector | $\mathbf{0} + \mathbf{0} = \mathbf{0}$, $c\mathbf{0} = \mathbf{0}$ | $\mathbf{0}$ | $0$ |
Polynomials. $\mathbb{P}_n$ consists of $p(x) = a_0 + a_1 x + \cdots + a_n x^n$, with real coefficients, where some or all $a_i$ may be zero. The phrase "degree at most $n$" matters. The polynomials of degree exactly $2$ do not form a vector space: $(x^2 + x) + (-x^2) = x$ has degree 1, and the zero polynomial is missing. Adding two polynomials adds their coefficient lists, so $\mathbb{P}_n$ behaves exactly like $\mathbb{R}^{n+1}$, a fact made precise in Section 6.5.
Matrices. $\mathbb{R}^{m \times n}$ with entrywise operations is a vector space (Section 4.1). Matrix multiplication is extra structure that the vector space axioms ignore. For vector space purposes, a $2 \times 3$ matrix is just six numbers arranged in a rectangle.
Functions. For any set $S$, the functions $f : S \to \mathbb{R}$ form a vector space under the pointwise operations
$$(f + g)(x) = f(x) + g(x), \qquad (cf)(x) = c,f(x).$$
Each axiom holds because it holds for the numbers $f(x), g(x)$ at every point $x$. This one example contains the others:
- $\mathbb{R}^n$ is $\mathcal{F}({1, \dots, n})$: a vector $\mathbf{x}$ is the function $i \mapsto x_i$.
- $\mathbb{R}^{m \times n}$ is $\mathcal{F}({1, \dots, m} \times {1, \dots, n})$: a matrix is the function $(i, j) \mapsto a_{ij}$.
- $\mathbb{R}^\infty$ is $\mathcal{F}({1, 2, 3, \dots})$.
So a vector in $\mathbb{R}^n$ is "a function sampled at $n$ points". This is the bridge between continuous signals and the finite arrays a computer stores.
a function f in F([0, 1]) the same function sampled: a vector in R^5
f(x) index i: 1 2 3 4 5
| .-''-. x_i: 0 0.25 0.5 0.75 1
| .' '. f(x_i): 0.0 0.7 1.0 0.7 0.0
| .' '.
| .' '. adding functions pointwise = adding samples
+-'------------------'---> x scaling a function = scaling its samples
0 1
Solution spaces of homogeneous equations. If $y_1$ and $y_2$ solve $y'' + y = 0$, then so does $c_1 y_1 + c_2 y_2$, because differentiation respects sums and scalar multiples. The solution set is a vector space, a subspace of the twice-differentiable functions (Section 6.2). This is the same reason the null space of a matrix is a vector space (Section 3.4). The equation $y'' + y = 1$ is not homogeneous, and its solution set is not closed under addition.
import numpy as np
import sympy as sp
from numpy.polynomial import Polynomial as P
# P_2: polynomials are added and scaled through their coefficient lists (constant term first)
p = P([1, 2, 3]) # 1 + 2x + 3x^2
q = P([0, -1, -3]) # -x - 3x^2
print((p + q).coef, (2 * p).coef) # [1. 1.] [2. 4. 6.]: the x^2 terms cancel
# Functions R -> R: build f + g and c f pointwise with closures
def add(f, g):
return lambda x: f(x) + g(x)
def scale(c, f):
return lambda x: c * f(x)
h = add(np.sin, scale(2, np.cos)) # h = sin + 2 cos, a new vector in C(R)
xs = np.linspace(0, np.pi, 5) # sampling at 5 points turns h into a vector in R^5
print(np.round(h(xs), 3)) # [ 2. 2.121 1. -0.707 -2. ]
print(np.allclose(h(xs), np.sin(xs) + 2 * np.cos(xs))) # True: sampling respects + and scaling
# Solutions of y'' + y = 0 are closed under linear combinations
x, c1, c2 = sp.symbols('x c1 c2')
y = c1 * sp.sin(x) + c2 * sp.cos(x)
print(sp.simplify(sp.diff(y, x, 2) + y)) # 0: every combination is a solution
# Solutions of y'' + y = 1 are not: 1 and 1 + sin(x) are solutions, their sum is not
y_sum = 1 + (1 + sp.sin(x))
print(sp.simplify(sp.diff(y_sum, x, 2) + y_sum)) # 2, not 1
Key takeaways
- $\mathbb{R}^n$, $\mathbb{P}_n$, $\mathbb{R}^{m \times n}$, function spaces, and sequence spaces are all vector spaces under the natural operations.
- $\mathbb{P}_n$ means degree at most $n$; "degree exactly $n$" is not closed under addition and lacks the zero polynomial.
- $\mathbb{R}^n$ is the space of functions on ${1, \dots, n}$; sampling a function produces a vector in $\mathbb{R}^n$.
- Solutions of homogeneous linear equations (algebraic or differential) form vector spaces; solutions of non-homogeneous ones do not.
🧪 Practice
- Decide which of the following are vector spaces under the usual operations: (a) polynomials of degree exactly 3; (b) $2 \times 2$ upper triangular matrices; (c) functions $f : \mathbb{R} \to \mathbb{R}$ with $f(0) = 1$; (d) real sequences that converge to $0$.
- Show that the solutions of $y'' - 3y' + 2y = 0$ form a vector space, and check that $e^x$ and $e^{2x}$ belong to it.
- Describe a correspondence between $\mathbb{R}^{2 \times 3}$ and $\mathbb{R}^6$ that turns matrix addition and scaling into vector addition and scaling.
- Interview: In machine learning, a $64 \times 64$ RGB image is often called "a vector". In which vector space does it live, and what do addition and scalar multiplication mean for images? If pixel values must stay in $[0, 255]$, is the set of valid images a vector space? Hint: $\mathbb{R}^{64 \times 64 \times 3} \cong \mathbb{R}^{12288}$; check closure under scaling by $-1$ and by $2$.
Elementary Consequences of the Axioms
Why it matters. Facts such as "$0\mathbf{v} = \mathbf{0}$" or "$(-1)\mathbf{v} = -\mathbf{v}$" look too obvious to need proof, but they are not among the axioms. In the positive-reals space they are not obvious at all: there, $0 \odot u = u^0 = 1$, and $1$ is the zero vector of that space. Proving these facts once from the axioms guarantees they hold in every vector space, including those where the operations look nothing like ordinary arithmetic. The proofs are also good practice in the axiomatic reasoning that the rest of the chapter relies on.
Theorem (basic properties). In any vector space $V$ over a field $F$, for all $\mathbf{u}, \mathbf{v}, \mathbf{w} \in V$ and $c \in F$:
| # | Property | In words |
|---|---|---|
| 1 | The zero vector is unique | There is only one $\mathbf{0}$ |
| 2 | Each $\mathbf{v}$ has a unique additive inverse | $-\mathbf{v}$ is well defined |
| 3 | $\mathbf{u} + \mathbf{w} = \mathbf{v} + \mathbf{w} \implies \mathbf{u} = \mathbf{v}$ | Cancellation |
| 4 | $0\mathbf{v} = \mathbf{0}$ | Scalar zero gives the zero vector |
| 5 | $c\mathbf{0} = \mathbf{0}$ | Scaling the zero vector gives zero |
| 6 | $(-1)\mathbf{v} = -\mathbf{v}$ | Negation is scaling by $-1$ |
| 7 | $c\mathbf{v} = \mathbf{0} \implies c = 0$ or $\mathbf{v} = \mathbf{0}$ | No zero divisors |
Proofs. Each step cites the axiom it uses.
(1) Uniqueness of zero. Suppose $\mathbf{0}$ and $\mathbf{0}'$ both satisfy A3. Then $\mathbf{0} = \mathbf{0} + \mathbf{0}'$ (A3 for $\mathbf{0}'$) $= \mathbf{0}' + \mathbf{0}$ (A1) $= \mathbf{0}'$ (A3 for $\mathbf{0}$). $\blacksquare$
(2) Uniqueness of inverses. If $\mathbf{v} + \mathbf{w} = \mathbf{0}$ and $\mathbf{v} + \mathbf{w}' = \mathbf{0}$, then $\mathbf{w} = \mathbf{w} + \mathbf{0} = \mathbf{w} + (\mathbf{v} + \mathbf{w}') = (\mathbf{w} + \mathbf{v}) + \mathbf{w}' = \mathbf{0} + \mathbf{w}' = \mathbf{w}'$, using A3, A2, A1, and A3. $\blacksquare$
(3) Cancellation. Add $-\mathbf{w}$ to both sides and use A2, A4, and A3. $\blacksquare$
(4) $0\mathbf{v} = \mathbf{0}$. This proof is the model for the others:
| Step | Statement | Reason |
|---|---|---|
| 1 | $0\mathbf{v} = (0 + 0)\mathbf{v}$ | $0 + 0 = 0$ in $F$ |
| 2 | $(0 + 0)\mathbf{v} = 0\mathbf{v} + 0\mathbf{v}$ | S2 |
| 3 | $0\mathbf{v} + \mathbf{0} = 0\mathbf{v} + 0\mathbf{v}$ | Steps 1 and 2, and A3 on the left |
| 4 | $\mathbf{0} = 0\mathbf{v}$ | Cancel $0\mathbf{v}$ (property 3) and use A1 |
$\blacksquare$
(5) $c\mathbf{0} = \mathbf{0}$. The same argument with $c\mathbf{0} = c(\mathbf{0} + \mathbf{0}) = c\mathbf{0} + c\mathbf{0}$, using A3 and S1. $\blacksquare$
(6) $(-1)\mathbf{v} = -\mathbf{v}$. $\mathbf{v} + (-1)\mathbf{v} = 1\mathbf{v} + (-1)\mathbf{v} = (1 + (-1))\mathbf{v} = 0\mathbf{v} = \mathbf{0}$, using S4, S2, and property 4. So $(-1)\mathbf{v}$ is an additive inverse of $\mathbf{v}$, and by property 2 it is the inverse. $\blacksquare$
(7) No zero divisors. Suppose $c\mathbf{v} = \mathbf{0}$ and $c \ne 0$. Since $F$ is a field, $c^{-1}$ exists, and $\mathbf{v} = 1\mathbf{v} = (c^{-1}c)\mathbf{v} = c^{-1}(c\mathbf{v}) = c^{-1}\mathbf{0} = \mathbf{0}$, using S4, S3, and property 5. $\blacksquare$
Where the field matters. Property 7 is the only one that divides by a scalar. If the scalars come from a number system without division, such as the integers modulo 6, it fails: $2 \cdot 3 = 0$ in $\mathbb{Z}_6$, although neither factor is zero. Structures that satisfy the axioms with scalars from such a ring are called modules (Section 13.4). They behave differently from vector spaces; for example, Gaussian elimination cannot always rescale a pivot to $1$.
Notation earned. Because of properties 2 and 6, we may write $\mathbf{u} - \mathbf{v}$ for $\mathbf{u} + (-\mathbf{v})$ without ambiguity. Because of A2, sums of many vectors need no parentheses.
# Check the theorems in the "exotic" space of positive reals,
# where u (+) v = u * v, c (.) u = u ** c, and the zero vector is 1
add = lambda u, v: u * v
scale = lambda c, u: u ** c
zero = 1.0
u = 5.0
print(scale(0, u)) # 1.0: 0 u = 0 (the zero vector of this space is 1)
print(scale(7.5, zero)) # 1.0: c 0 = 0
print(scale(-1, u), 1 / u) # 0.2 0.2: (-1) u is the additive inverse of u
print(add(u, scale(-1, u)) == zero) # True: u + (-u) = 0
# Property 7 needs a field. In Z_6 (not a field) a nonzero scalar can kill a nonzero vector:
c, v = 2, 3
print((c * v) % 6) # 0, although c != 0 and v != 0
Key takeaways
- The zero vector and additive inverses are unique, and cancellation holds in every vector space.
- $0\mathbf{v} = \mathbf{0}$, $c\mathbf{0} = \mathbf{0}$, and $(-1)\mathbf{v} = -\mathbf{v}$ are theorems, not axioms.
- $c\mathbf{v} = \mathbf{0}$ forces $c = 0$ or $\mathbf{v} = \mathbf{0}$; the proof needs $c^{-1}$, so it relies on the scalars forming a field.
- Proofs from axioms cite one axiom per step; this habit makes every later proof in the chapter checkable.
🧪 Practice
- Prove $c\mathbf{0} = \mathbf{0}$, citing an axiom for each step.
- Prove that $-(-\mathbf{v}) = \mathbf{v}$ and that $(-c)\mathbf{v} = -(c\mathbf{v})$.
- Prove that if $\mathbf{u} + \mathbf{v} = \mathbf{u}$ for a single vector $\mathbf{u}$, then $\mathbf{v} = \mathbf{0}$. Interpret the result in the positive-reals space.
- Interview: Why does the proof of "$c\mathbf{v} = \mathbf{0}$ implies $c = 0$ or $\mathbf{v} = \mathbf{0}$" break down when scalars are integers modulo 6, and what problem does that create for running Gaussian elimination modulo 6? Hint: try to scale a row whose pivot is $2$ so that the pivot becomes $1$.
Vector Spaces over Complex and General Fields
Why it matters. Nothing in the axioms requires real scalars. Complex scalars are essential in quantum mechanics, in signal processing (the discrete Fourier transform, Section 13.3), and for eigenvalues (Chapter 8), since a real rotation matrix has complex eigenvalues. Scalars from the finite field $\mathbb{F}_2 = {0, 1}$ turn bit strings into vectors, which is the basis of error-correcting codes, RAID storage, and parts of cryptography. All the machinery of Chapters 3 to 5, including elimination, rank, inverses, and determinants, uses only $+, -, \times, \div$, so it works over any field.
Complex vector spaces. $\mathbb{C}^n$ is the set of $n$-tuples of complex numbers, with componentwise operations and complex scalars. For example, in $\mathbb{C}^2$,
$$i,(1, i) = (i, i^2) = (i, -1).$$
The matrices $\mathbb{C}^{m \times n}$ and the complex polynomials are complex vector spaces in the same way.
The field is part of the definition. The same set with a different field of scalars is a different vector space. The most important case is $\mathbb{C}$ itself:
| Set | Scalars | Example of a basis (Section 6.4) | Dimension |
|---|---|---|---|
| $\mathbb{C}$ | $\mathbb{C}$ | ${1}$ | 1 |
| $\mathbb{C}$ | $\mathbb{R}$ | ${1, i}$ | 2 |
| $\mathbb{C}^n$ | $\mathbb{C}$ | ${\mathbf{e}_1, \dots, \mathbf{e}_n}$ | $n$ |
| $\mathbb{C}^n$ | $\mathbb{R}$ | ${\mathbf{e}_1, i\mathbf{e}_1, \dots, \mathbf{e}_n, i\mathbf{e}_n}$ | $2n$ |
| $\mathbb{R}$ | $\mathbb{Q}$ | none can be written down explicitly | infinite |
| $\mathbb{R}^n$ | $\mathbb{C}$ | not a vector space: $i,\mathbf{e}_1 \notin \mathbb{R}^n$ |
Viewed over $\mathbb{R}$, the complex number $a + bi$ behaves exactly like the vector $(a, b) \in \mathbb{R}^2$. This is the complex plane of Section 1.2. Over $\mathbb{C}$, the vectors $(1, i)$ and $(i, -1)$ are multiples of each other, because $(i, -1) = i,(1, i)$. Over $\mathbb{R}$ they are not, since no real $c$ gives $c(1, i) = (i, -1)$.
Vector spaces over finite fields. $\mathbb{F}_2^n$ (also written $\mathbb{Z}_2^n$) is the set of bit strings of length $n$. Addition is componentwise modulo 2, which is bitwise XOR, and the only scalars are $0$ and $1$. Some consequences:
- The space is finite: $\mathbb{F}_p^n$ has exactly $p^n$ vectors.
- Every vector is its own negative: $\mathbf{v} + \mathbf{v} = 2\mathbf{v} = \mathbf{0}$.
- There is no notion of length or "small", and no ordering of scalars.
A linear code is a subspace of $\mathbb{F}_2^n$ (Section 6.2). The simplest example is the even-parity code in $\mathbb{F}_2^3$, the bit strings with an even number of ones: ${000, 011, 101, 110}$. XOR of two even-weight strings is again even-weight, so the set is closed under addition. A single flipped bit produces an odd-weight string, which reveals the error.
What carries over, and what does not.
| Topic | Over any field | Needs $\mathbb{R}$ or $\mathbb{C}$ specifically |
|---|---|---|
| Elimination, rank, inverses, determinants | Yes | |
| Span, independence, basis, dimension (this chapter) | Yes | |
| Length, angle, orthogonality | Yes (Chapter 9); over $\mathbb{C}$ the inner product needs conjugates | |
| Every polynomial has a root, so every matrix has an eigenvalue | Only over $\mathbb{C}$ (Chapter 8) | |
| Counting arguments ("how many vectors?") | Only over finite fields |
from itertools import product
import numpy as np
# C^2 over C: scalars may be complex
v = np.array([1, 1j])
print(1j * v) # [ 0.+1.j -1.+0.j]: i (1, i) = (i, -1)
# C viewed over R behaves like R^2: z = a + bi <-> (a, b)
as_r2 = lambda z: np.array([z.real, z.imag])
z, w = 3 + 4j, -1 + 2j
print(as_r2(z + w), as_r2(z) + as_r2(w)) # [2. 6.] [2. 6.]
print(as_r2(2.5 * z), 2.5 * as_r2(z)) # [ 7.5 10. ] [ 7.5 10. ]
# F_2^3: bit vectors, addition is XOR (addition mod 2)
code = [np.array(b) for b in product([0, 1], repeat=3) if sum(b) % 2 == 0] # even-weight words
print([''.join(map(str, c)) for c in code]) # ['000', '011', '101', '110']
closed = all(any(np.array_equal((a + b) % 2, c) for c in code) for a in code for b in code)
print(closed) # True: XOR of two codewords is a codeword
print((code[1] + code[1]) % 2) # [0 0 0]: every vector is its own negative
print(len(list(product(range(3), repeat=4)))) # 81 = 3^4 vectors in F_3^4
Key takeaways
- A vector space is defined over a field; changing the field changes the space and its dimension ($\mathbb{C}$ has dimension 1 over $\mathbb{C}$ but 2 over $\mathbb{R}$).
- $\mathbb{C}^n$ uses complex scalars; over $\mathbb{C}$, $(i, -1)$ is a multiple of $(1, i)$.
- $\mathbb{F}_2^n$ is the space of bit strings with XOR as addition; it is finite and every vector is its own negative.
- Everything that uses only $+, -, \times, \div$ works over any field; geometry and the existence of eigenvalues depend on the field.
🧪 Practice
- List all vectors of $\mathbb{F}_2^2$ and write out its addition table. How many vectors does $\mathbb{F}_5^3$ contain?
- In $\mathbb{C}^2$, is $(2, 1 + i)$ a complex multiple of $(1 - i, 1)$? Is it a real multiple? Find the scalar where one exists.
- Explain why $\mathbb{R}^2$ with complex scalars and the rule $c(x, y) = (cx, cy)$ is not a vector space over $\mathbb{C}$.
- Interview: RAID-5 storage keeps, next to $k$ data blocks $\mathbf{d}_1, \dots, \mathbf{d}_k$, a parity block $\mathbf{p} = \mathbf{d}_1 \oplus \cdots \oplus \mathbf{d}_k$ (bitwise XOR). Explain why this is linear algebra over $\mathbb{F}_2$, and show how any single lost block is recovered. Hint: in $\mathbb{F}_2^n$, $\mathbf{v} + \mathbf{v} = \mathbf{0}$, so subtraction is the same as addition.
<a id="62-subspaces"></a>
6.2 Subspaces
Most vector spaces met in practice sit inside a larger one: a plane through the origin inside $\mathbb{R}^3$, the polynomials of degree at most 2 inside all polynomials, the null space of a matrix inside $\mathbb{R}^n$. This subchapter gives a quick test for when a subset inherits the vector space structure, and shows how to combine subspaces by intersection, sum, and span.
Definition and Subspace Test
Why it matters. Checking ten axioms every time is tedious, and for a subset of a known vector space it is also unnecessary. Identities such as $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ hold for all vectors of the big space, so in particular for those in the subset. What can fail is that an operation leads out of the subset. The subspace test reduces the work to three checks, and it is the tool used throughout the rest of the course to recognize null spaces, column spaces, eigenspaces, and solution spaces.
Definition. A subset $W$ of a vector space $V$ is a subspace of $V$ if $W$ is itself a vector space under the addition and scalar multiplication of $V$.
Theorem (subspace test). A subset $W \subseteq V$ is a subspace if and only if
- $\mathbf{0} \in W$;
- $\mathbf{u}, \mathbf{v} \in W \implies \mathbf{u} + \mathbf{v} \in W$ (closed under addition);
- $\mathbf{u} \in W$, $c \in F \implies c\mathbf{u} \in W$ (closed under scalar multiplication).
Proof. If $W$ is a subspace, it has a zero vector $\mathbf{0}_W$. Then $\mathbf{0}_W + \mathbf{0}_W = \mathbf{0}_W$ holds in $V$, and cancellation (Section 6.1) gives $\mathbf{0}_W = \mathbf{0}$. Conditions 2 and 3 are the closure axioms.
Conversely, assume 1 to 3. Closure gives C1 and C2. Axioms A1, A2, and S1 to S4 are identities that hold for all vectors of $V$, so they hold in $W$. A3 holds by condition 1. For A4, if $\mathbf{u} \in W$, then $-\mathbf{u} = (-1)\mathbf{u} \in W$ by condition 3 and property 6 of Section 6.1. $\blacksquare$
One-line version. Conditions 1 to 3 are equivalent to: $W$ is nonempty, and $a\mathbf{u} + b\mathbf{v} \in W$ whenever $\mathbf{u}, \mathbf{v} \in W$ and $a, b \in F$. A subspace is a nonempty set closed under linear combinations.
Check the zero vector first. Condition 1 is the fastest way to reject a candidate. If $\mathbf{0} \notin W$, stop: $W$ is not a subspace. This immediately rules out lines and planes that miss the origin, the solution set of $A\mathbf{x} = \mathbf{b}$ with $\mathbf{b} \ne \mathbf{0}$, and polynomials with $p(0) = 1$. Containing $\mathbf{0}$ is necessary but not sufficient.
Analogy. A subspace is like a room with no exits for the two operations: start inside, add or scale as often as you like, and you never leave. A line through the origin is such a room. A line that misses the origin is not, because doubling a point on it lands off the line.
four subsets of R^2, and the first condition each one fails
(a) line through 0 (b) line y = x + 1 (c) union of the axes (d) first quadrant
| / | / | |
| / | / w * * u+w |
| / |/ | | * u
|/ / | |
---------0--------- --------/0--------- ---------0---*----- ---------0---------
/| / | | u |
/ | / | | -u * |
subspace 0 is not on it u + w is on neither -u is outside
(condition 1) axis (condition 2) (condition 3)
Example. $W = {(x, y, z) \in \mathbb{R}^3 : x - 2y + z = 0}$, a plane through the origin.
- $0 - 0 + 0 = 0$, so $\mathbf{0} \in W$.
- If $x_1 - 2y_1 + z_1 = 0$ and $x_2 - 2y_2 + z_2 = 0$, adding gives $(x_1 + x_2) - 2(y_1 + y_2) + (z_1 + z_2) = 0$.
- Multiplying $x - 2y + z = 0$ by $c$ gives $(cx) - 2(cy) + (cz) = 0$.
So $W$ is a subspace. It is $\operatorname{Nul}\begin{bmatrix} 1 & -2 & 1 \end{bmatrix}$, and null spaces are always subspaces (Section 3.4). The plane $x - 2y + z = 1$ fails condition 1.
import numpy as np
rng = np.random.default_rng(0)
def find_violation(member, sample, dim, trials=2000):
"""Search for a counterexample to the subspace test.
Finding one proves W is not a subspace; finding none is only evidence."""
if not member(np.zeros(dim)):
return "condition 1 fails: 0 is not in W"
for _ in range(trials):
u, v, c = sample(), sample(), rng.normal() * 5
if not member(u + v):
return f"condition 2 fails: u = {np.round(u, 2)}, v = {np.round(v, 2)}"
if not member(c * u):
return f"condition 3 fails: c = {c:.2f}, u = {np.round(u, 2)}"
return "no violation found"
def plane_point(): # a random point on x - 2y + z = 0
x, y = rng.normal(size=2)
return np.array([x, y, 2 * y - x])
plane = lambda p: np.isclose(p[0] - 2 * p[1] + p[2], 0)
shifted = lambda p: np.isclose(p[0] - 2 * p[1] + p[2], 1)
axes = lambda p: np.isclose(p[0], 0) or np.isclose(p[1], 0)
quadrant = lambda p: p[0] >= 0 and p[1] >= 0
def axis_point(): # a random point on one of the two axes
t = rng.normal()
return np.array([t, 0.0]) if rng.random() < 0.5 else np.array([0.0, t])
print(find_violation(plane, plane_point, 3)) # no violation found
print(find_violation(shifted, plane_point, 3)) # condition 1 fails: 0 is not in W
print(find_violation(axes, axis_point, 2).split(':')[0]) # condition 2 fails
print(find_violation(quadrant, lambda: np.abs(rng.normal(size=2)), 2).split(':')[0]) # condition 3 fails
Key takeaways
- A subspace is a subset that is a vector space under the inherited operations.
- Subspace test: contains $\mathbf{0}$, closed under addition, closed under scalar multiplication.
- Equivalently: nonempty and closed under linear combinations $a\mathbf{u} + b\mathbf{v}$.
- Check $\mathbf{0} \in W$ first; failing it ends the test, passing it proves nothing on its own.
- Null spaces of matrices are subspaces; solution sets of $A\mathbf{x} = \mathbf{b}$ with $\mathbf{b} \ne \mathbf{0}$ are not.
🧪 Practice
- Which of these subsets of $\mathbb{R}^3$ are subspaces? (a) ${\mathbf{x} : x_1 = 2x_3}$; (b) ${\mathbf{x} : x_1 x_2 = 0}$; (c) ${\mathbf{x} : x_1 + x_2 + x_3 \le 1}$; (d) ${\mathbf{x} : x_1 = x_2 = x_3}$. Give a failing condition with numbers for each non-subspace.
- Prove that the symmetric $n \times n$ matrices form a subspace of $\mathbb{R}^{n \times n}$. Do the invertible $n \times n$ matrices form one?
- Prove that the solution set of $A\mathbf{x} = \mathbf{b}$ is a subspace of $\mathbb{R}^n$ if and only if $\mathbf{b} = \mathbf{0}$.
- Interview: Give a subset of $\mathbb{R}^2$ that contains $\mathbf{0}$ and is closed under addition but is not a subspace, and one that contains $\mathbf{0}$ and is closed under scalar multiplication but is not a subspace. What does this say about which conditions of the test can be skipped? Hint: think of integer points, and of the union of two lines.
Examples and Non-Examples
Why it matters. Running the subspace test on many examples builds a reliable instinct. Sets defined by homogeneous linear conditions ("some linear expression equals $0$") are subspaces. Sets defined by inhomogeneous conditions ("$= 1$"), inequalities, products, or words like "exactly" and "invertible" almost never are. With this instinct, you can usually predict the answer before running the test.
All subspaces of $\mathbb{R}^2$ and $\mathbb{R}^3$. A subspace containing a nonzero vector $\mathbf{v}$ contains every multiple $c\mathbf{v}$, so it contains a whole line through the origin. Continuing this argument (made rigorous by dimension in Section 6.4) gives a complete list:
dimension subspaces of R^3
3 R^3 itself
2 planes through the origin (infinitely many)
1 lines through the origin (infinitely many)
0 {0}
R^2 is the same picture without the planes: {0}, lines through 0, and R^2.
A line or plane that misses the origin is never a subspace.
A catalogue.
| Set | Inside | Subspace? | Reason |
|---|---|---|---|
| ${\mathbf{0}}$ and $V$ itself | any $V$ | Yes | The trivial subspaces |
| $\operatorname{Nul} A = {\mathbf{x} : A\mathbf{x} = \mathbf{0}}$ | $\mathbb{R}^n$ | Yes | Homogeneous linear equations |
| ${\mathbf{x} : A\mathbf{x} = \mathbf{b}}$, $\mathbf{b} \ne \mathbf{0}$ | $\mathbb{R}^n$ | No | $\mathbf{0}$ is not a solution |
| ${\mathbf{x} : x_i \ge 0}$ | $\mathbb{R}^n$ | No | $-\mathbf{x}$ leaves the set |
| Probability vectors ($x_i \ge 0$, $\sum x_i = 1$) | $\mathbb{R}^n$ | No | $\mathbf{0}$ is missing; sums add to 2 |
| $\mathbb{Z}^n$ (integer vectors) | $\mathbb{R}^n$ | No | $\tfrac12\mathbf{e}_1 \notin \mathbb{Z}^n$ |
| $\mathbb{P}_2$ | $\mathbb{P}$ | Yes | Degree $\le 2$ is preserved |
| ${p \in \mathbb{P}_n : p(1) = 0}$ | $\mathbb{P}_n$ | Yes | $p \mapsto p(1)$ is linear |
| ${p \in \mathbb{P}_n : p(1) = 1}$ | $\mathbb{P}_n$ | No | Zero polynomial missing |
| Polynomials of degree exactly $n$ | $\mathbb{P}$ | No | $x^n + (-x^n) = 0$ |
| Symmetric, skew-symmetric, diagonal, upper triangular matrices | $\mathbb{R}^{n \times n}$ | Yes | Defined by linear equations on entries |
| Matrices with trace $0$ | $\mathbb{R}^{n \times n}$ | Yes | Trace is linear |
| Invertible matrices | $\mathbb{R}^{n \times n}$ | No | $O$ is not invertible; $I + (-I) = O$ |
| Singular matrices | $\mathbb{R}^{n \times n}$ | No | $\operatorname{diag}(1, 0) + \operatorname{diag}(0, 1) = I$ |
| $C[a, b]$, differentiable functions | $\mathcal{F}([a, b])$ | Yes | Sums and multiples stay continuous or differentiable |
| ${f : f(0) = 0}$ | $\mathcal{F}(\mathbb{R})$ | Yes | Homogeneous condition |
| Solutions of $y'' + y = 0$ | $C^2(\mathbb{R})$ | Yes | Homogeneous linear ODE |
| Nonnegative functions | $\mathcal{F}(\mathbb{R})$ | No | $-f$ leaves the set |
The pattern. Every "Yes" row is the set of vectors on which some linear expressions vanish, such as $A\mathbf{x}$, $p(1)$, $\operatorname{tr}A$, $A - A^T$, or $y'' + y$. Chapter 7 names this pattern: the kernel of a linear map is always a subspace. Red flags for a "No":
| Red flag | Example | Usually fails |
|---|---|---|
| Right-hand side not zero | $p(1) = 1$ | $\mathbf{0} \in W$ |
| Inequality | $x_i \ge 0$ | Scaling by $-1$ |
| Product or nonlinear function of the entries | $x_1 x_2 = 0$, $\det A = 0$ | Addition |
| "Exactly", "nonzero", "invertible" | degree exactly $n$ | $\mathbf{0} \in W$ |
| Integer or discrete values | $\mathbb{Z}^n$ | Scaling by non-integers |
import sympy as sp
a = sp.symbols('a0:4')
b = sp.symbols('b0:4')
c = sp.symbols('c')
A, B = sp.Matrix(2, 2, a), sp.Matrix(2, 2, b)
# Trace-zero matrices: the defining expression is linear, so it survives sums and multiples
print(sp.expand((A + B).trace() - (A.trace() + B.trace()))) # 0
print(sp.expand((c * A).trace() - c * A.trace())) # 0
# Singular matrices: the defining expression (det) is not linear
D1, D2 = sp.diag(1, 0), sp.diag(0, 1)
print(D1.det(), D2.det(), (D1 + D2).det()) # 0 0 1: the sum escapes
# Polynomials with p(1) = 0 are closed under sums and multiples; p(1) = 1 is not
x = sp.symbols('x')
p, q = x**2 - 1, 3*x - 3 # both vanish at x = 1
print((p + q).subs(x, 1), (5 * p).subs(x, 1)) # 0 0
p1, q1 = x**2, x # both equal 1 at x = 1
print((p1 + q1).subs(x, 1)) # 2
Key takeaways
- The subspaces of $\mathbb{R}^3$ are exactly ${\mathbf{0}}$, lines through $\mathbf{0}$, planes through $\mathbf{0}$, and $\mathbb{R}^3$.
- Sets cut out by homogeneous linear conditions are subspaces; this covers null spaces, symmetric matrices, trace-zero matrices, and solution spaces of homogeneous ODEs.
- Inhomogeneous conditions, inequalities, nonlinear conditions, and "exactly/invertible" conditions are red flags.
- Invertible matrices and singular matrices both fail to be subspaces, for different reasons.
🧪 Practice
- Classify each set as a subspace or not, with a one-line reason: (a) ${A \in \mathbb{R}^{2 \times 2} : a_{11} = a_{22}}$; (b) ${A \in \mathbb{R}^{2 \times 2} : A^2 = A}$; (c) ${p \in \mathbb{P}_3 : p'(0) = p(2)}$; (d) ${f \in C[0, 1] : \int_0^1 f(x),dx = 0}$.
- Show that a subspace of $\mathbb{R}^2$ containing two non-parallel vectors must be all of $\mathbb{R}^2$.
- Find a subset of $\mathbb{R}^2$ that is closed under scalar multiplication, contains $\mathbf{0}$, contains infinitely many lines, and is still not a subspace.
- Interview: A product team stores "valid probability distributions over $n$ outcomes" and wants to blend them as $a\mathbf{p} + b\mathbf{q}$. Which weights $(a, b)$ always give another valid distribution? Why is the set not a subspace, and what kind of set is it? Hint: compare linear combinations with convex combinations ($a, b \ge 0$, $a + b = 1$).
Intersections and Sums of Subspaces
Why it matters. There are two natural ways to combine subspaces. Imposing the constraints of both gives the intersection. Pooling the generators of both gives the sum. Solving a system of homogeneous equations is an intersection, one hyperplane per equation. Merging two feature sets is a sum. The obvious third option, the union, almost never works, and seeing why is instructive.
Intersection. If $U$ and $W$ are subspaces of $V$, then $U \cap W$ is a subspace.
Proof. $\mathbf{0}$ lies in both. If $\mathbf{u}, \mathbf{v} \in U \cap W$, then $\mathbf{u} + \mathbf{v}$ and $c\mathbf{u}$ lie in $U$ (as $U$ is a subspace) and in $W$ (as $W$ is). $\blacksquare$
The same proof works for the intersection of any number of subspaces, even infinitely many. For example, $\operatorname{Nul} A$ is the intersection of the $m$ hyperplanes ${\mathbf{x} : \mathbf{r}_i \cdot \mathbf{x} = 0}$, one for each row $\mathbf{r}_i$ of $A$.
Union. $U \cup W$ is a subspace only if one of them contains the other.
Proof. Suppose neither contains the other. Pick $\mathbf{u} \in U \setminus W$ and $\mathbf{w} \in W \setminus U$. If $\mathbf{u} + \mathbf{w} \in U$, then $\mathbf{w} = (\mathbf{u} + \mathbf{w}) - \mathbf{u} \in U$, a contradiction. Similarly $\mathbf{u} + \mathbf{w} \notin W$. So $\mathbf{u} + \mathbf{w} \notin U \cup W$. $\blacksquare$
The union of the $x$-axis and the $y$-axis contains $(1, 0)$ and $(0, 1)$, but not their sum $(1, 1)$.
Sum. The sum of $U$ and $W$ is
$$U + W = {\mathbf{u} + \mathbf{w} : \mathbf{u} \in U,\ \mathbf{w} \in W}.$$
It is a subspace, and it is the smallest subspace containing $U \cup W$. Any subspace containing both $U$ and $W$ contains every sum $\mathbf{u} + \mathbf{w}$. If $U = \operatorname{Span}(S)$ and $W = \operatorname{Span}(T)$, then $U + W = \operatorname{Span}(S \cup T)$.
| Operation | Meaning | Always a subspace? | In terms of matrices |
|---|---|---|---|
| $U \cap W$ | satisfy the constraints of both | Yes | stack the constraint rows: $\operatorname{Nul}\begin{bmatrix} A \ B \end{bmatrix}$ |
| $U + W$ | combine the generators of both | Yes | place the generators side by side: $\operatorname{Col},[,A ;; B,]$ |
| $U \cup W$ | either one | Only if $U \subseteq W$ or $W \subseteq U$ | no useful formula |
Example. In $\mathbb{R}^3$, let $U$ be the $xy$-plane ($z = 0$) and $W = \operatorname{Span}{(0, 1, 1), (1, 0, 1)}$, the plane $x + y - z = 0$.
- $U \cap W$: the conditions $z = 0$ and $x + y - z = 0$ give $x = -y$, $z = 0$. This is the line $\operatorname{Span}{(1, -1, 0)}$. Two distinct planes through the origin meet in a line.
- $U + W$: the four generators $(1, 0, 0), (0, 1, 0), (0, 1, 1), (1, 0, 1)$ include three independent ones, so $U + W = \mathbb{R}^3$.
Computing an intersection from generators. If $U = \operatorname{Col} A$ and $W = \operatorname{Col} B$, a vector lies in both exactly when $A\mathbf{x} = B\mathbf{y}$ for some $\mathbf{x}, \mathbf{y}$. That is,
$$\begin{bmatrix} A & -B \end{bmatrix}\begin{bmatrix} \mathbf{x} \ \mathbf{y} \end{bmatrix} = \mathbf{0}.$$
Each null space vector $(\mathbf{x}, \mathbf{y})$ gives a common vector $A\mathbf{x} = B\mathbf{y}$.
import sympy as sp
A = sp.Matrix([[1, 0], [0, 1], [0, 0]]) # columns span U = the xy-plane
B = sp.Matrix([[0, 1], [1, 0], [1, 1]]) # columns span W = the plane x + y - z = 0
# Sum: U + W is spanned by all generators together
print(A.row_join(B).rank()) # 3: U + W = R^3
# Intersection: solve A x = B y, i.e. [A | -B] (x, y) = 0
for n in A.row_join(-B).nullspace():
x = n[:A.cols, :] # the weights on the columns of A
print((A * x).T) # Matrix([[1, -1, 0]]): U ∩ W = Span{(1, -1, 0)}
# Union: (1, 0, 0) is in U and (0, 1, 1) is in W, but their sum is in neither
s = sp.Matrix([1, 1, 1])
print(s[2] == 0, s[0] + s[1] - s[2] == 0) # False False
Key takeaways
- $U \cap W$ (constraints of both) and $U + W$ (generators of both) are always subspaces.
- $U \cup W$ is a subspace only when one contains the other; in general $\mathbf{u} + \mathbf{w}$ escapes.
- $U + W$ is the smallest subspace containing both: $\operatorname{Span}(S) + \operatorname{Span}(T) = \operatorname{Span}(S \cup T)$.
- With generator matrices, $U + W = \operatorname{Col},[,A ;; B,]$, and $U \cap W$ comes from $\operatorname{Nul},[,A ;; -B,]$.
🧪 Practice
- In $\mathbb{R}^3$, find $U \cap W$ and $U + W$ for $U = {x + y + z = 0}$ and $W = \operatorname{Span}{(1, 1, 1)}$. Then do the same for $W' = \operatorname{Span}{(1, -1, 0)}$.
- Prove that $U + W$ is a subspace and that every subspace containing $U \cup W$ also contains $U + W$.
- Find two subspaces $U, W$ of $\mathbb{R}^4$, each of dimension 2, with $U \cap W = {\mathbf{0}}$. Can this happen in $\mathbb{R}^3$?
- Interview: Two teams each produce a set of features for the same data. As vectors in $\mathbb{R}^n$, team 1's features span $U = \operatorname{Col} A$ and team 2's span $W = \operatorname{Col} B$. How do you compute which directions both teams capture, and how many genuinely new directions merging the teams adds over team 1 alone? Hint: $\operatorname{Nul},[,A ;; -B,]$ for the overlap; $\operatorname{rank},[,A ;; B,] - \operatorname{rank} A$ for the gain.
Direct Sums
Why it matters. Many useful decompositions split a vector into parts in a unique way. Every function is an even part plus an odd part. Every square matrix is a symmetric part plus a skew-symmetric part. Every signal is a low-frequency part plus a high-frequency part. The decomposition is unique exactly when the two subspaces overlap only in $\mathbf{0}$. That situation is called a direct sum, and it underlies projections (Chapter 7), eigenspace decompositions (Chapter 8), and orthogonal decompositions (Chapter 9).
Definition. $V$ is the direct sum of subspaces $U$ and $W$, written $V = U \oplus W$, if
$$V = U + W \quad\text{and}\quad U \cap W = {\mathbf{0}}.$$
$W$ is then called a complement of $U$ in $V$.
Theorem (unique decomposition). $V = U \oplus W$ if and only if every $\mathbf{v} \in V$ can be written as $\mathbf{v} = \mathbf{u} + \mathbf{w}$ with $\mathbf{u} \in U$ and $\mathbf{w} \in W$ in exactly one way.
Proof. Existence of a decomposition is the statement $V = U + W$. For uniqueness, suppose $\mathbf{u} + \mathbf{w} = \mathbf{u}' + \mathbf{w}'$. Then $\mathbf{u} - \mathbf{u}' = \mathbf{w}' - \mathbf{w}$. The left side lies in $U$ and the right side in $W$, so both lie in $U \cap W = {\mathbf{0}}$, giving $\mathbf{u} = \mathbf{u}'$ and $\mathbf{w} = \mathbf{w}'$. Conversely, if $\mathbf{x} \ne \mathbf{0}$ lies in $U \cap W$, then $\mathbf{0} = \mathbf{0} + \mathbf{0} = \mathbf{x} + (-\mathbf{x})$ gives two different decompositions of $\mathbf{0}$. $\blacksquare$
Standard examples.
| Space | Decomposition | Formula for the parts |
|---|---|---|
| $\mathbb{R}^{n \times n}$ | symmetric $\oplus$ skew-symmetric | $A = \tfrac12(A + A^T) + \tfrac12(A - A^T)$ |
| $\mathcal{F}(\mathbb{R})$ | even $\oplus$ odd | $f(x) = \tfrac12\big(f(x) + f(-x)\big) + \tfrac12\big(f(x) - f(-x)\big)$ |
| $\mathbb{P}_n$ | even-degree terms $\oplus$ odd-degree terms | split the coefficient list |
| $\mathbb{R}^3$ | plane through $\mathbf{0}$ $\oplus$ line through $\mathbf{0}$ not in the plane | solve a $3 \times 3$ system |
For matrices, the intersection is trivial: if $A = A^T$ and $A = -A^T$, then $A = -A$, so $A = O$. For $f(x) = e^x$, the even and odd parts are $\cosh x$ and $\sinh x$.
Complements are not unique. In $\mathbb{R}^2$, let $U$ be the $x$-axis. Every line through the origin other than $U$ is a complement of $U$, and the $U$-part of a vector depends on which complement is used. Decompose $\mathbf{v} = (3, 2)$:
with W1 = y-axis: v = (3, 0) + (0, 2) U-part (3, 0)
with W2 = line y = x: v = (1, 0) + (2, 2) U-part (1, 0)
W1| W2 (y = x)
| /
| /
| / * v = (3, 2)
| / /:
| / / :
| / / :
| / / :
|/ / :
--------0--*-----+---------- U (x-axis)
| 1 3
|
':' runs parallel to W1 and ends at the U-part (3, 0);
the short '/' runs parallel to W2 and ends at the U-part (1, 0).
"The component of $\mathbf{v}$ in $U$" therefore makes sense only after a complement is chosen. Chapter 9 picks the perpendicular complement, which is unique, and the result is the orthogonal projection.
More than two summands. $V = U_1 \oplus \cdots \oplus U_k$ means $V = U_1 + \cdots + U_k$ and every vector has a unique decomposition. It is not enough that the subspaces meet pairwise only in $\mathbf{0}$. Three distinct lines through the origin in $\mathbb{R}^2$ meet pairwise in ${\mathbf{0}}$, yet $\mathbf{e}_1 + \mathbf{e}_2 - (1, 1) = \mathbf{0}$ is a nontrivial decomposition of $\mathbf{0}$. The correct condition is that each $U_i$ meets the sum of the others only in $\mathbf{0}$. Equivalently (Section 6.4), $\dim(U_1 + \cdots + U_k) = \dim U_1 + \cdots + \dim U_k$.
import numpy as np
import sympy as sp
# Symmetric + skew-symmetric decomposition
M = np.array([[1., 2.], [6., 3.]])
S, K = (M + M.T) / 2, (M - M.T) / 2
print(S.tolist(), K.tolist()) # [[1.0, 4.0], [4.0, 3.0]] [[0.0, -2.0], [2.0, 0.0]]
print(np.allclose(S + K, M)) # True
# Even + odd decomposition of e^x
x = sp.symbols('x')
f = sp.exp(x)
even, odd = (f + f.subs(x, -x)) / 2, (f - f.subs(x, -x)) / 2
print(sp.simplify(even - sp.cosh(x)), sp.simplify(odd - sp.sinh(x))) # 0 0
# The U-part depends on the complement: U = x-axis, v = (3, 2)
u = np.array([1., 0.])
for name, w in [("W1 = y-axis", np.array([0., 1.])), ("W2 = y = x", np.array([1., 1.]))]:
c = np.linalg.solve(np.column_stack([u, w]), [3., 2.]) # v = c0 u + c1 w, unique since U ⊕ W = R^2
print(name, "U-part:", c[0] * u, "W-part:", c[1] * w)
# W1 = y-axis U-part: [3. 0.] W-part: [0. 2.]
# W2 = y = x U-part: [1. 0.] W-part: [2. 2.]
# Three lines in R^2 meet pairwise in {0}, but their sum is not direct
L = np.array([[1., 0., 1.],
[0., 1., 1.]]) # columns span the x-axis, the y-axis, and y = x
print(np.linalg.matrix_rank(L), L.shape[1]) # 2 3: the dimensions add to 3 > 2
Key takeaways
- $V = U \oplus W$ means $V = U + W$ and $U \cap W = {\mathbf{0}}$; equivalently, every vector splits uniquely into a $U$-part and a $W$-part.
- Standard direct sums: symmetric $\oplus$ skew-symmetric matrices, even $\oplus$ odd functions.
- A subspace has many complements, and the $U$-part of a vector depends on which complement is used.
- For three or more summands, pairwise trivial intersections are not enough; each summand must meet the sum of the others only in $\mathbf{0}$.
🧪 Practice
- Write $A = \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{bmatrix}$ as a symmetric matrix plus a skew-symmetric matrix.
- Show that $\mathbb{P}_3$ is the direct sum of the even polynomials and the odd polynomials, and decompose $1 + 2x - x^2 + 4x^3$.
- Is $\mathbb{R}^3 = U \oplus W$ for $U = {z = 0}$ and $W = \operatorname{Span}{(1, 1, 1)}$? If so, decompose $(2, 3, 4)$.
- Interview: A colleague has three subspaces of $\mathbb{R}^n$ whose pairwise intersections are all ${\mathbf{0}}$ and concludes their sum is direct. Give a counterexample, and state a test that actually works when each subspace is given by a basis. Hint: three lines in a plane; put all the basis vectors into one matrix and compare its rank with the number of columns.
Span of a Set as a Subspace
Why it matters. There are two ways to describe a subspace. The implicit description lists equations that its vectors satisfy, as with a null space. The explicit description lists generators whose combinations produce it, which is a span. Each makes different tasks easy. Testing whether a vector satisfies some equations is easy, while producing all solutions takes work. Producing elements from generators is easy, while testing membership takes work. Converting between the two descriptions is a core skill, and the span is the explicit one.
Definition. For vectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $V$,
$$\operatorname{Span}{\mathbf{v}_1, \dots, \mathbf{v}_k} = {c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k : c_1, \dots, c_k \in F}.$$
For an infinite set $S$, $\operatorname{Span}(S)$ is the set of all finite linear combinations of vectors in $S$. By convention, $\operatorname{Span}(\varnothing) = {\mathbf{0}}$. Sections 2.2 and 3.2 used spans in $\mathbb{R}^n$; the definition is the same in any vector space.
Theorem. $\operatorname{Span}(S)$ is a subspace of $V$, and it is the smallest subspace containing $S$: every subspace that contains $S$ also contains $\operatorname{Span}(S)$.
Proof. $\mathbf{0} = 0\mathbf{v}_1$ is a combination. The sum of two combinations is a combination, with the weights added, and a multiple of a combination is a combination, with the weights scaled. So $\operatorname{Span}(S)$ is a subspace. A subspace containing $S$ is closed under linear combinations, so it contains every combination of vectors in $S$. $\blacksquare$
We say $S$ spans $W$, or generates $W$, if $\operatorname{Span}(S) = W$.
Converting between descriptions.
| Direction | Method |
|---|---|
| Equations $\to$ generators | Solve the homogeneous system. The parametric vector form (Section 3.4) writes $\operatorname{Nul} A = \operatorname{Span}{\dots}$ |
| Generators $\to$ equations | Put the generators in the columns of $V$. A vector $\mathbf{b}$ is in the span exactly when $[,V \mid \mathbf{b},]$ is consistent. Row reduce with symbolic $\mathbf{b}$: each zero row of the $V$-part forces one equation on $\mathbf{b}$ |
| Membership test | $\mathbf{b} \in \operatorname{Span}$ $\iff$ $\operatorname{rank} V = \operatorname{rank},[,V \mid \mathbf{b},]$ |
| Same span? | $\operatorname{Span}(\text{cols of } V) = \operatorname{Span}(\text{cols of } W)$ $\iff$ $\operatorname{rank} V = \operatorname{rank} W = \operatorname{rank},[,V ;; W,]$ |
Example. Find equations for $W = \operatorname{Span}{(1, 2, 0, 1), (0, 1, 1, 1)}$ in $\mathbb{R}^4$. A vector $\mathbf{b}$ lies in $W$ when $c_1(1, 2, 0, 1) + c_2(0, 1, 1, 1) = (b_1, b_2, b_3, b_4)$:
$$c_1 = b_1, \quad 2c_1 + c_2 = b_2, \quad c_2 = b_3, \quad c_1 + c_2 = b_4.$$
The first and third equations determine $c_1$ and $c_2$. The other two must then hold automatically, which gives the two equations
$$2b_1 - b_2 + b_3 = 0, \qquad b_1 + b_3 - b_4 = 0.$$
So the same plane in $\mathbb{R}^4$ has the explicit description "span of 2 vectors" and the implicit description "solutions of 2 equations". Four dimensions minus two equations leaves a 2-dimensional subspace.
Analogy. A span is everything you can cook from a set of ingredients. Adding an ingredient that is already a mixture of the others, such as orange juice when you already have oranges and water, adds no new dishes. Spans grow only when you add something genuinely new, which is the idea behind linear independence (Section 6.3).
import sympy as sp
V = sp.Matrix([[1, 0],
[2, 1],
[0, 1],
[1, 1]]) # columns v1 = (1, 2, 0, 1), v2 = (0, 1, 1, 1)
b = sp.Matrix(sp.symbols('b1:5'))
# Generators -> equations: each y with y^T V = 0 gives one equation y . b = 0
# (these y form the left null space of V, Section 6.6)
for y in V.T.nullspace():
print(sp.Eq((y.T * b)[0], 0))
# Eq(2*b1 - b2 + b3, 0)
# Eq(b1 - b2 + b4, 0)
# Membership test by ranks
for target in [(1, 3, 1, 2), (1, 1, 1, 1)]:
t = sp.Matrix(target)
print(target, V.rank() == V.row_join(t).rank())
# (1, 3, 1, 2) True
# (1, 1, 1, 1) False
# Same span? {v1, v2} versus {v1 + v2, v1 - v2}
W = sp.Matrix.hstack(V[:, 0] + V[:, 1], V[:, 0] - V[:, 1])
print(V.rank(), W.rank(), V.row_join(W).rank()) # 2 2 2: the same subspace
The code's second equation, $b_1 - b_2 + b_4 = 0$, differs from the hand-derived $b_1 + b_3 - b_4 = 0$. Both systems describe the same subspace: subtracting one equation from another gives an equivalent system, just as row operations do.
Key takeaways
- $\operatorname{Span}(S)$, the set of all finite linear combinations, is the smallest subspace containing $S$.
- Subspaces have implicit descriptions (equations) and explicit descriptions (generators); null spaces are implicit, spans are explicit.
- Equations to generators: solve the system. Generators to equations: find the consistency conditions of $[,V \mid \mathbf{b},]$.
- $\mathbf{b} \in \operatorname{Span}$ exactly when appending $\mathbf{b}$ does not raise the rank.
🧪 Practice
- Describe $\operatorname{Span}{(1, 1, 0), (0, 1, 1)} \subseteq \mathbb{R}^3$ by a single equation, and check that $(2, 3, 1)$ satisfies it.
- In $\mathbb{P}_2$, is $x^2 + 1$ in $\operatorname{Span}{x^2 + x,\ x - 1,\ x + 1}$? If so, find the weights.
- Prove that $\operatorname{Span}{\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3} = \operatorname{Span}{\mathbf{v}_1, \mathbf{v}_2}$ if and only if $\mathbf{v}_3 \in \operatorname{Span}{\mathbf{v}_1, \mathbf{v}_2}$.
- Interview: You are given two sets of 300 vectors each in $\mathbb{R}^{1000}$, as columns of $V$ and $W$. How would you check programmatically whether they span the same subspace? What changes when the data are noisy floating-point measurements? Hint: compare $\operatorname{rank} V$, $\operatorname{rank} W$, and $\operatorname{rank},[,V ;; W,]$; with noise, rank needs a tolerance on singular values (Chapter 11).
<a id="63-linear-independence"></a>
6.3 Linear Independence
A spanning set can contain redundant vectors that add nothing to the span. Linear independence is the precise meaning of "no redundancy". Together with spanning, it gives the definition of a basis in Section 6.4. This subchapter defines independence, turns it into a row-reduction test, reads off the redundancies when they exist, and adapts the test to function spaces.
Linear Combinations and Span
Why it matters. Section 2.2 introduced linear combinations in $\mathbb{R}^n$. In an abstract vector space they mean exactly the same thing, but they are now the only tool available, since there are no components until a basis is chosen. Every question in this chapter has the form "which linear combinations of these vectors produce that one?". That question always becomes a linear system, solvable by Chapter 3. This topic also tracks how a span grows as vectors are added, which leads directly to the definition of independence.
Linear combinations in any space. For $\mathbf{v}_1, \dots, \mathbf{v}_k \in V$ and scalars $c_1, \dots, c_k$, the vector $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k$ is a linear combination. To decide whether a target $\mathbf{b}$ is a combination, write out $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{b}$ and compare "components" in whatever form the space provides: coefficients of polynomials, entries of matrices, values of functions.
Example in $\mathbb{P}_2$. Is $3 + x^2$ a combination of $1 + x$, $x + x^2$, and $1 - x^2$? Collect the coefficients of $1$, $x$, and $x^2$ in $a(1 + x) + b(x + x^2) + c(1 - x^2) = 3 + x^2$:
$$a + c = 3, \qquad a + b = 0, \qquad b - c = 1.$$
From the second equation, $a = -b$, so the first gives $c - b = 3$, which contradicts $b - c = 1$. The system is inconsistent, so $3 + x^2$ is not in the span. The same three polynomials do produce $2 + 3x + x^2$, and in infinitely many ways: $a = 2 - c$, $b = 1 + c$, with $c$ free. A target that is reachable in infinitely many ways is a symptom of redundancy. Indeed $1 - x^2 = (1 + x) - (x + x^2)$.
Spanning sets. A set $S$ spans $V$ if $\operatorname{Span}(S) = V$, so that every vector of $V$ is reachable. In $\mathbb{R}^m$, Section 3.2 gives a test: the columns of an $m \times n$ matrix $A$ span $\mathbb{R}^m$ if and only if $A$ has a pivot in every row, that is, $\operatorname{rank} A = m$. Since there are at most $n$ pivots, at least $m$ vectors are needed to span $\mathbb{R}^m$.
How a span grows. Adding a vector $\mathbf{v}$ to a set $S$ either enlarges the span or leaves it unchanged:
$$\operatorname{Span}(S \cup {\mathbf{v}}) = \operatorname{Span}(S) \iff \mathbf{v} \in \operatorname{Span}(S).$$
set its span what the newest vector added
--------------------- --------------------------- ------------------------------------------
{v1} a line through 0 a new direction
{v1, v2} a plane through 0 a new direction: v2 is off the line
{v1, v2, v3} the same plane nothing: v3 lies in the plane (redundant)
{v1, v2, v3, v4} all of R^3 a new direction: v4 is off the plane
{v1}: a line {v1, v2, v3}: a plane {v1, v2, v3, v4}: R^3
^ v4
|
/ v1 +------------+ +--|---------+
/ /v3 ^ v2 / / | /
/ / \| / / | /
/ / 0--> v1/ / 0--> v1/
/ / / / /
0 +------------+ +------------+
A vector that leaves the span unchanged is redundant. Linear independence (next topic) means that no vector in the set is redundant.
import numpy as np
import sympy as sp
x, a, b, c = sp.symbols('x a b c')
gens = [1 + x, x + x**2, 1 - x**2]
def weights(target):
"""Solve a*g0 + b*g1 + c*g2 = target by matching coefficients of 1, x, x^2."""
combo = sp.expand(a * gens[0] + b * gens[1] + c * gens[2] - target)
equations = sp.Poly(combo, x).all_coeffs() # every coefficient must vanish
return sp.solve(equations, [a, b, c], dict=True)
print(weights(3 + x**2)) # []: not in the span
print(weights(2 + 3*x + x**2)) # [{a: 2 - c, b: c + 1}]: infinitely many weights, c is free
# Spanning R^m: do the columns have a pivot in every row (rank m)?
A = np.array([[1, 4, 7],
[2, 5, 8],
[3, 6, 9]])
B = np.array([[1, 4, 7],
[2, 5, 8],
[3, 6, 10]])
print(np.linalg.matrix_rank(A), np.linalg.matrix_rank(B)) # 2 3: only B's columns span R^3
Key takeaways
- In any vector space, "is $\mathbf{b}$ a combination of $\mathbf{v}_1, \dots, \mathbf{v}_k$?" becomes a linear system once components (coefficients, entries, values) are compared.
- $S$ spans $V$ when every vector is a combination; columns of $A$ span $\mathbb{R}^m$ exactly when $\operatorname{rank} A = m$.
- At least $m$ vectors are needed to span $\mathbb{R}^m$.
- Adding $\mathbf{v}$ enlarges $\operatorname{Span}(S)$ exactly when $\mathbf{v} \notin \operatorname{Span}(S)$; a vector that adds nothing is redundant.
🧪 Practice
- Do $(1, 2, 3)$, $(4, 5, 6)$, $(7, 8, 9)$ span $\mathbb{R}^3$? If not, describe their span geometrically and find one vector outside it.
- Show that ${1,\ 1 + x,\ 1 + x + x^2}$ spans $\mathbb{P}_2$, and write $5 - x + 2x^2$ as a combination of these polynomials.
- Explain, without computation, why no two vectors can span $\mathbb{R}^3$, and why three vectors may or may not.
- Interview: A synthesizer can mix $k$ base waveforms, each sampled as a vector in $\mathbb{R}^m$, with arbitrary real weights. What condition on the base waveforms lets it reproduce every target in $\mathbb{R}^m$ exactly, and how would you check it quickly? Hint: rank of the $m \times k$ matrix of waveforms; a necessary condition on $k$.
Linear Independence and Dependence
Why it matters. Redundant vectors are wasteful, and they also make representations ambiguous. If a target can be built from a set of vectors in two different ways, there is no well-defined "amount" of each vector in it. Linear independence is the condition that removes this ambiguity. In data analysis, dependent features make regression coefficients non-unique. In numerical work, nearly dependent vectors make computations unstable. In theory, independence is half of the definition of a basis.
Definition. Vectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ in $V$ are linearly independent if the only solution of
$$c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$$
is the trivial one, $c_1 = c_2 = \cdots = c_k = 0$. They are linearly dependent if some nontrivial choice of weights (not all zero) gives $\mathbf{0}$. Such an equation is called a dependence relation.
An infinite set is independent if every finite subset is independent.
Theorem (equivalent forms). For vectors $\mathbf{v}_1, \dots, \mathbf{v}_k$ the following are equivalent:
- They are linearly independent.
- No $\mathbf{v}_j$ is a linear combination of the others; no vector is redundant.
- Every vector in their span has exactly one set of weights.
- (In $\mathbb{R}^n$.) The matrix $A = [,\mathbf{v}_1 \ \cdots \ \mathbf{v}_k,]$ satisfies $\operatorname{Nul} A = {\mathbf{0}}$, so $A\mathbf{x} = \mathbf{0}$ has only the trivial solution.
Proof of 1 $\Leftrightarrow$ 2. If $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$ with some $c_j \ne 0$, divide by $c_j$ to solve for $\mathbf{v}_j$ in terms of the others. Conversely, $\mathbf{v}j = \sum{i \ne j} d_i\mathbf{v}_i$ rearranges to a relation with coefficient $-1 \ne 0$ on $\mathbf{v}_j$.
Proof of 1 $\Leftrightarrow$ 3. If $\sum c_i\mathbf{v}_i = \sum d_i\mathbf{v}_i$, then $\sum (c_i - d_i)\mathbf{v}_i = \mathbf{0}$, so independence forces $c_i = d_i$. Conversely, a dependence relation gives two different weight vectors for $\mathbf{0}$: the relation and all zeros. $\blacksquare$
Quick facts.
| Situation | Independent? | Why |
|---|---|---|
| A single vector $\mathbf{v}$ | Yes $\iff$ $\mathbf{v} \ne \mathbf{0}$ | $c\mathbf{v} = \mathbf{0}$ forces $c = 0$ when $\mathbf{v} \ne \mathbf{0}$ (Section 6.1) |
| Two vectors | Yes $\iff$ neither is a multiple of the other | Form 2 |
| Any set containing $\mathbf{0}$ | No | $1 \cdot \mathbf{0} = \mathbf{0}$ is a nontrivial relation |
| More than $n$ vectors in $\mathbb{R}^n$ | No | More unknowns than equations in $A\mathbf{x} = \mathbf{0}$ (Section 3.4) |
| A subset of an independent set | Yes | A relation in the subset is a relation in the whole set |
| A superset of a dependent set | No | The same relation, with zero weights on the new vectors |
| Nonzero, mutually orthogonal vectors in $\mathbb{R}^n$ | Yes | Dot the relation with $\mathbf{v}_j$: $c_j\lVert\mathbf{v}_j\rVert^2 = 0$ |
Pitfall: "no two are parallel" is not enough. For three or more vectors, dependence can involve all of them at once. The vectors $(1, 0, 0)$, $(0, 1, 0)$, and $(1, 1, 0)$ are pairwise non-parallel but dependent, because all three lie in the plane $z = 0$.
independent in R^3 dependent: no two parallel, all three in one plane
v3 v2
^ ^ v3
| v2 | /
| / | /
| / |/
+--------> v1 +-----------> v1
three genuinely different directions v3 = v1 + v2 adds no new direction
Analogy. Think of a committee where each member reports a measurement. The committee is independent if no member's report can be predicted exactly from the others'. A dependent committee has at least one member who could be dismissed without losing any information. Unlike real committees, which one you dismiss is often a free choice.
import numpy as np
def is_independent(*vectors):
A = np.column_stack(vectors)
return np.linalg.matrix_rank(A) == A.shape[1] # no free variables in A x = 0
e1, e2 = np.array([1, 0, 0]), np.array([0, 1, 0])
print(is_independent(e1, e2)) # True
print(is_independent(e1, e2, e1 + e2)) # False: pairwise non-parallel, still dependent
print(is_independent(e1, np.zeros(3))) # False: any set containing 0
print(is_independent(e1, e2, np.array([0, 0, 1]), np.array([1, 2, 3]))) # False: 4 vectors in R^3
# Unique weights: with dependent vectors, the same target has many representations
v1, v2, v3 = e1, e2, e1 + e2
target = np.array([2, 3, 0])
for w in [(2, 3, 0), (0, 1, 2), (1, 2, 1)]:
print(w, np.array_equal(w[0] * v1 + w[1] * v2 + w[2] * v3, target)) # all True
Key takeaways
- Independent: the only combination giving $\mathbf{0}$ is the trivial one. Dependent: some nontrivial combination gives $\mathbf{0}$.
- Independence $\iff$ no vector is redundant $\iff$ every vector in the span has unique weights.
- Any set containing $\mathbf{0}$, or with more than $n$ vectors in $\mathbb{R}^n$, is dependent.
- For three or more vectors, pairwise non-parallel does not imply independent.
- Nonzero orthogonal vectors are always independent.
🧪 Practice
- Decide independence: (a) $(1, 2, 3), (2, 4, 6)$; (b) $(1, 0, 1), (0, 1, 1), (1, 1, 0)$; (c) $(1, 2), (3, 4), (5, 6)$.
- Prove that if ${\mathbf{u}, \mathbf{v}, \mathbf{w}}$ is independent in a real vector space, then so is ${\mathbf{u} + \mathbf{v},\ \mathbf{v} + \mathbf{w},\ \mathbf{u} + \mathbf{w}}$. Does the proof still work over $\mathbb{F}_2$?
- Prove that nonzero mutually orthogonal vectors in $\mathbb{R}^n$ are linearly independent.
- Interview: In a linear regression with design matrix $X$, two feature columns are exactly collinear (say, temperature in Celsius and in Fahrenheit). What happens to the fitted coefficients, and why can no solver give a unique answer? Hint: dependent columns mean $\operatorname{Nul} X \ne {\mathbf{0}}$; add any null vector to a solution.
Testing Independence via Row Reduction
Why it matters. The definition says to solve $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$. In $\mathbb{R}^n$ that is the homogeneous system $A\mathbf{c} = \mathbf{0}$, which Chapter 3 solves by elimination. Spaces of polynomials or matrices can be reduced to the same computation by listing coefficients or entries. The result is one algorithm for every finite-dimensional space. For floating-point data, the same test needs a tolerance, and "nearly dependent" becomes an important practical notion.
The test. To test $\mathbf{v}_1, \dots, \mathbf{v}_k \in \mathbb{R}^n$:
- Form $A = [,\mathbf{v}_1 \ \cdots \ \mathbf{v}_k,]$ with the vectors as columns.
- Row reduce $A$ to echelon form.
- The vectors are independent $\iff$ every column is a pivot column $\iff$ $\operatorname{rank} A = k$.
A non-pivot column gives a free variable and hence a nontrivial solution of $A\mathbf{c} = \mathbf{0}$. For $k = n$ (a square matrix), independence is equivalent to $\det A \ne 0$ and to every other statement of the Invertible Matrix Theorem (Section 4.3).
Example. Test $\mathbf{v}_1 = (1, 2, 0, 1)$, $\mathbf{v}_2 = (2, 4, 1, 3)$, $\mathbf{v}_3 = (0, 0, 1, 1)$, $\mathbf{v}_4 = (1, 1, 1, 1)$:
$$A = \begin{bmatrix} 1 & 2 & 0 & 1 \ 2 & 4 & 0 & 1 \ 0 & 1 & 1 & 1 \ 1 & 3 & 1 & 1 \end{bmatrix} ;\longrightarrow; R = \begin{bmatrix} 1 & 0 & -2 & 0 \ 0 & 1 & 1 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 0 & 0 \end{bmatrix}.$$
Column 3 has no pivot, so the vectors are dependent. The rank is 3, so the span is a 3-dimensional subspace of $\mathbb{R}^4$. This matrix is the running example for the rest of this subchapter and for Section 6.4.
Other spaces: test the coordinates. List each vector's coefficients with respect to a fixed spanning list, such as monomials or matrix entries. Then test those coefficient vectors. Section 6.5 justifies this: the coefficient map preserves linear combinations.
| Space | Turn each vector into |
|---|---|
| $\mathbb{P}_n$ | its coefficient vector $(a_0, a_1, \dots, a_n) \in \mathbb{R}^{n+1}$ |
| $\mathbb{R}^{m \times n}$ | its entries in a fixed order, a vector in $\mathbb{R}^{mn}$ |
| $\mathbb{C}^n$ over $\mathbb{C}$ | itself; row reduce with complex arithmetic |
| $\mathbb{F}_2^n$ | itself; row reduce with arithmetic mod 2 |
For example, $1 + x$, $x + x^2$, $1 - x^2$ become the columns $(1, 1, 0)$, $(0, 1, 1)$, $(1, 0, -1)$. The $3 \times 3$ determinant is $0$, so they are dependent, which matches the previous topic.
Floating point: nearly dependent. With measured or computed data, exact zeros rarely occur, and rank is decided by a tolerance. NumPy's matrix_rank counts the singular values (Chapter 11) above a threshold of roughly $\max(m, n) \cdot \varepsilon_{\text{mach}} \cdot \sigma_{\max}$. Vectors that are independent in exact arithmetic but very nearly dependent behave like dependent ones: coefficients become huge and sensitive to noise. The smallest singular value measures how close a set is to dependence.
import numpy as np
import sympy as sp
# Exact test with sympy: vectors as columns, then RREF
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 0, 1],
[0, 1, 1, 1],
[1, 3, 1, 1]]) # columns v1, v2, v3, v4
R, pivots = A.rref()
print(pivots, len(pivots) == A.cols) # (0, 1, 3) False: v3 is not a pivot column, so dependent
# Polynomials: test their coefficient vectors
x = sp.symbols('x')
polys = [1 + x, x + x**2, 1 - x**2]
C = sp.Matrix([[sp.Poly(p, x).coeff_monomial(x**k) for p in polys] for k in range(3)])
print(C.T.tolist(), C.det()) # [[1, 1, 0], [0, 1, 1], [1, 0, -1]] 0: dependent
# Matrices: flatten each into R^4
Ms = [np.array([[1, 0], [0, 1]]), np.array([[0, 1], [1, 0]]), np.array([[1, 1], [1, 1]])]
print(np.linalg.matrix_rank(np.column_stack([M.ravel() for M in Ms]))) # 2: the third is the sum of the first two
# Nearly dependent vectors in floating point
rng = np.random.default_rng(1)
v1, v2 = rng.normal(size=5), rng.normal(size=5)
for eps in [1e-2, 1e-8, 1e-15]:
M = np.column_stack([v1, v2, v1 + v2 + eps * rng.normal(size=5)])
smallest = np.linalg.svd(M, compute_uv=False)[-1]
print(f"eps={eps:.0e} rank={np.linalg.matrix_rank(M)} smallest singular value={smallest:.1e}")
# eps=1e-02 rank=3 smallest singular value=3.1e-03
# eps=1e-08 rank=3 smallest singular value=5.3e-09
# eps=1e-15 rank=2 smallest singular value=1.5e-15: numerically dependent
Key takeaways
- Put the vectors in the columns of $A$; they are independent exactly when every column is a pivot column ($\operatorname{rank} A = k$).
- For $k = n$, independence is equivalent to $\det A \ne 0$.
- Polynomials and matrices are tested through their coefficient or entry vectors.
- In floating point, rank depends on a tolerance; a tiny smallest singular value signals near-dependence.
🧪 Practice
- Test $(1, 1, 1, 1)$, $(1, 2, 3, 4)$, $(1, 4, 9, 16)$, $(1, 8, 27, 64)$ for independence. Which special kind of matrix (Section 3.5) do they form?
- For which $h$ are $(1, -1, 2)$, $(2, 1, h)$, $(0, 3, 1)$ linearly dependent?
- Are $1 + x + x^2$, $1 + 2x + 4x^2$, $1 + 3x + 9x^2$ independent in $\mathbb{P}_2$? Relate your answer to polynomial interpolation at the nodes $1, 2, 3$.
- Interview: Your feature matrix has 2,000 columns,
matrix_rankreports full column rank, but the regression coefficients are enormous and change completely when you drop a single row of data. What is going on, and what would you measure to confirm it? Hint: the smallest singular value and the condition number (Section 11.3); exact rank is not the same as numerical robustness.
Dependence Relations
Why it matters. When vectors are dependent, the dependence relations say exactly which vectors are redundant and how to rebuild them from the others. They also have direct meaning in applications. The coefficients that balance a chemical equation (Section 3.5) are a dependence relation among the molecules' atom-count vectors. The loop currents of a circuit are dependence relations among its edges. On the theory side, one lemma about dependence relations is the key to proving that dimension is well defined (Section 6.4).
All relations form a subspace. The weight vectors $\mathbf{c} = (c_1, \dots, c_k)$ with $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$ are exactly the vectors of $\operatorname{Nul} A$, where $A = [,\mathbf{v}_1 \ \cdots \ \mathbf{v}_k,]$. Hence:
- the nonzero null vectors are the dependence relations;
- a basis of $\operatorname{Nul} A$ (one special solution per free variable) gives a complete set of independent relations;
- the number of independent relations is $k - \operatorname{rank} A$. It counts how many vectors are redundant.
Reading relations from the RREF. Row operations do not change the solutions of $A\mathbf{c} = \mathbf{0}$. Therefore the columns of $A$ satisfy exactly the same linear relations as the columns of its RREF $R$. In $R$, every non-pivot column is visibly a combination of the pivot columns, with its entries as the weights. The same combination holds for the original columns.
For the running example, column 3 of $R$ is $(-2, 1, 0, 0) = -2,(\text{col } 1) + 1,(\text{col } 2)$. So in $A$,
$$\mathbf{v}_3 = -2\mathbf{v}_1 + \mathbf{v}_2, \qquad\text{equivalently}\qquad 2\mathbf{v}_1 - \mathbf{v}_2 + \mathbf{v}_3 = \mathbf{0}.$$
Check: $2(1, 2, 0, 1) - (2, 4, 1, 3) + (0, 0, 1, 1) = (0, 0, 0, 0)$.
The linear dependence lemma. If $\mathbf{v}_1, \dots, \mathbf{v}_k$ are dependent and $\mathbf{v}_1 \ne \mathbf{0}$, then some $\mathbf{v}_j$ with $j \ge 2$ is a linear combination of the earlier vectors $\mathbf{v}1, \dots, \mathbf{v}{j-1}$. Removing that $\mathbf{v}_j$ does not change the span.
Proof. Take a dependence relation and let $j$ be the largest index with $c_j \ne 0$. Then $c_1\mathbf{v}_1 + \cdots + c_j\mathbf{v}_j = \mathbf{0}$, so $\mathbf{v}j = -\frac{1}{c_j}(c_1\mathbf{v}1 + \cdots + c{j-1}\mathbf{v}{j-1})$. Here $j \ge 2$, since $j = 1$ would give $c_1\mathbf{v}_1 = \mathbf{0}$ with $\mathbf{v}_1 \ne \mathbf{0}$. Any combination that uses $\mathbf{v}_j$ can be rewritten without it, so the span is unchanged. $\blacksquare$
The replacement theorem. If $V$ is spanned by $m$ vectors, then every linearly independent set in $V$ has at most $m$ vectors.
Proof (matrix version). Let $\mathbf{w}_1, \dots, \mathbf{w}_m$ span $V$, and let $\mathbf{u}_1, \dots, \mathbf{u}_k \in V$ with $k > m$. Each $\mathbf{u}_j$ is a combination $\mathbf{u}j = \sum_i c{ij}\mathbf{w}_i$, and these weights form an $m \times k$ matrix $C$. Since $k > m$, the homogeneous system $C\mathbf{x} = \mathbf{0}$ has more unknowns than equations, so it has a nontrivial solution $\mathbf{x}$ (Section 3.4). Then
$$\sum_j x_j\mathbf{u}j = \sum_j x_j \sum_i c{ij}\mathbf{w}i = \sum_i \Big(\sum_j c{ij}x_j\Big)\mathbf{w}_i = \sum_i (C\mathbf{x})_i,\mathbf{w}_i = \mathbf{0},$$
a nontrivial dependence relation among the $\mathbf{u}_j$. $\blacksquare$
The replacement theorem is the single most important fact in this subchapter. Section 6.4 uses it to show that all bases of a space have the same size.
import sympy as sp
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 0, 1],
[0, 1, 1, 1],
[1, 3, 1, 1]]) # columns v1, v2, v3, v4 (running example)
relations = A.nullspace() # a basis of all dependence relations
print(len(relations), relations[0].T) # 1 Matrix([[2, -1, 1, 0]]): 2 v1 - v2 + v3 = 0
print((A * relations[0]).T) # Matrix([[0, 0, 0, 0]])
R, pivots = A.rref()
print(R[:, 2].T) # Matrix([[-2, 1, 0, 0]]): v3 = -2 v1 + 1 v2
# Balancing H2 + O2 -> H2O is a dependence relation among atom-count vectors (H, O).
# Products enter with a minus sign: a*H2 + b*O2 - c*H2O = 0
M = sp.Matrix([[2, 0, -2], # hydrogen atoms in H2, O2, H2O
[0, 2, -1]]) # oxygen atoms
r = M.nullspace()[0]
r = r * sp.ilcm(*[term.q for term in r]) # clear denominators to get the smallest integers
print(r.T) # Matrix([[2, 1, 2]]): 2 H2 + O2 -> 2 H2O
Key takeaways
- Dependence relations among the columns of $A$ are exactly the nonzero vectors of $\operatorname{Nul} A$; there are $k - \operatorname{rank} A$ independent ones.
- Row operations preserve the relations among columns, so each non-pivot column of the RREF shows how the original column is built from the pivot columns.
- Linear dependence lemma: in a dependent list, some vector is a combination of the earlier ones and can be dropped without changing the span.
- Replacement theorem: an independent set is never larger than a spanning set.
🧪 Practice
- Find a basis for all dependence relations among $(1, 1, 0)$, $(0, 1, 1)$, $(1, 2, 1)$, $(2, 3, 1)$, and express each redundant vector in terms of the others.
- Write out the proof of the linear dependence lemma for the running example: which $j$ does the proof pick, and which earlier vectors does it use?
- Use the replacement theorem to show that any four polynomials in $\mathbb{P}_2$ are linearly dependent.
- Interview: A data matrix has 1,000,000 rows and 50 columns, and its rank is 47. How would you choose which 3 columns to drop so that the remaining 47 are independent and span the same column space? Is the choice unique? Hint: pivot columns of an RREF or of a column-pivoted QR; the answer depends on the column order.
Wronskian for Functions
Why it matters. Function spaces such as $C(\mathbb{R})$ are infinite-dimensional, so a function cannot be turned into one finite coordinate vector and row reduced. Yet independence of functions matters a great deal. The general solution of a second-order linear ODE is $c_1y_1 + c_2y_2$ only if $y_1$ and $y_2$ are independent. The Wronskian turns this into a determinant computation, and point evaluation offers a second, simpler test.
Independence of functions. Functions $f_1, \dots, f_n$ on an interval $I$ are linearly dependent if there are constants $c_1, \dots, c_n$, not all zero, with
$$c_1 f_1(x) + \cdots + c_n f_n(x) = 0 \quad\text{for every } x \in I.$$
The relation must hold identically, as an equation between functions, not just at a few points. For example, $\sin^2 x + \cos^2 x - 1 = 0$ for all $x$, so ${\sin^2, \cos^2, 1}$ is dependent.
Test 1: evaluate at points. If a relation holds for every $x$, it holds at any chosen points $x_1, \dots, x_n$, which gives the linear system
$$\begin{bmatrix} f_1(x_1) & \cdots & f_n(x_1) \ \vdots & & \vdots \ f_1(x_n) & \cdots & f_n(x_n) \end{bmatrix}\begin{bmatrix} c_1 \ \vdots \ c_n \end{bmatrix} = \mathbf{0}.$$
If this matrix is invertible for some choice of points, then $\mathbf{c} = \mathbf{0}$ and the functions are independent. A singular matrix proves nothing, since the points may just have been unlucky.
Test 2: the Wronskian. Differentiating the relation $n - 1$ times gives $n$ equations at each $x$. Their coefficient matrix has determinant
$$W(f_1, \dots, f_n)(x) = \det\begin{bmatrix} f_1(x) & f_2(x) & \cdots & f_n(x) \ f_1'(x) & f_2'(x) & \cdots & f_n'(x) \ \vdots & \vdots & & \vdots \ f_1^{(n-1)}(x) & f_2^{(n-1)}(x) & \cdots & f_n^{(n-1)}(x) \end{bmatrix}.$$
Theorem. If the $f_i$ are $(n-1)$ times differentiable on $I$ and $W(x_0) \ne 0$ for some $x_0 \in I$, then $f_1, \dots, f_n$ are linearly independent on $I$.
Proof. A dependence relation $\sum c_i f_i = 0$ on $I$ can be differentiated $k$ times to give $\sum c_i f_i^{(k)} = 0$ on $I$. At $x_0$, these $n$ equations say that the Wronskian matrix times $\mathbf{c}$ is $\mathbf{0}$. That matrix is invertible, so $\mathbf{c} = \mathbf{0}$. $\blacksquare$
| Functions | Wronskian | Conclusion |
|---|---|---|
| $1, x, x^2$ | $2$ | Independent |
| $e^x, e^{2x}$ | $e^{3x}$ | Independent |
| $\sin x, \cos x$ | $-1$ | Independent |
| $e^{ax}, e^{bx}$ with $a \ne b$ | $(b - a)e^{(a+b)x}$ | Independent |
| $\sin^2 x, \cos^2 x, 1$ | $0$ | Inconclusive by itself, but in fact dependent |
The converse is false in general. $W \equiv 0$ does not imply dependence. The functions $f(x) = x^2$ and $g(x) = x\lvert x\rvert$ are differentiable on $[-1, 1]$, with $W \equiv 0$. But they are independent: on $[0, 1]$ they agree, and on $[-1, 0]$ they are negatives of each other, so no single constant relation fits both halves. Test 1 confirms this with the points $\pm 1$.
The converse is true for ODE solutions. If $y_1, \dots, y_n$ solve one linear homogeneous ODE $y^{(n)} + p_{n-1}(x)y^{(n-1)} + \cdots + p_0(x)y = 0$ with continuous coefficients, then Abel's identity shows that $W$ is either never zero or identically zero on $I$. So, for solutions, one evaluation at one point settles independence.
import numpy as np
import sympy as sp
x = sp.symbols('x', real=True)
print(sp.wronskian([1, x, x**2], x)) # 2
print(sp.simplify(sp.wronskian([sp.exp(x), sp.exp(2*x)], x))) # exp(3*x)
print(sp.simplify(sp.wronskian([sp.sin(x), sp.cos(x)], x))) # -1
print(sp.simplify(sp.wronskian([sp.sin(x)**2, sp.cos(x)**2, 1], x))) # 0 (and they are dependent)
# W = 0 everywhere, yet independent: x^2 and x|x|
f = lambda t: t**2
g = lambda t: t * abs(t)
fp = lambda t: 2 * t # derivatives, valid on all of [-1, 1]
gp = lambda t: 2 * abs(t)
print([float(f(t) * gp(t) - g(t) * fp(t)) for t in np.linspace(-1, 1, 5)]) # [0.0, 0.0, 0.0, 0.0, 0.0]
# Test 1 (evaluation at points) settles it
E = np.array([[f(-1), g(-1)],
[f(1), g(1)]])
print(np.linalg.det(E)) # 2.0: nonzero, so x^2 and x|x| are independent
Key takeaways
- Functions are dependent only if a single nontrivial relation holds for every $x$ in the interval.
- If the evaluation matrix at some points is invertible, the functions are independent.
- If the Wronskian is nonzero at one point, the functions are independent.
- $W \equiv 0$ does not imply dependence in general (example: $x^2$ and $x\lvert x\rvert$), but it does for solutions of a single linear homogeneous ODE.
🧪 Practice
- Compute the Wronskian of $e^x$ and $xe^x$, and conclude whether they are independent.
- Show that $1$, $\cos 2x$, and $\sin^2 x$ are dependent by finding an explicit relation, and verify that their Wronskian is identically zero.
- Use evaluation at three points to prove that $x$, $x^2$, $x^3$ are independent on $\mathbb{R}$.
- Interview: A numerical ODE solver returns two solutions $y_1, y_2$ of $y'' + p(x)y' + q(x)y = 0$ on $[0, 10]$. How do you check that they form a fundamental set, so that every solution is $c_1y_1 + c_2y_2$? Why is checking one point enough here, when it is not enough for arbitrary functions? Hint: Abel's identity, $W(x) = W(x_0)\exp\left(-\int_{x_0}^x p(t),dt\right)$.
<a id="64-basis-and-dimension"></a>
6.4 Basis and Dimension
A basis is a spanning set with no redundancy: the smallest set of building blocks that generates the whole space. All bases of a space have the same number of vectors, and that number, the dimension, is the single most important invariant of a vector space. This subchapter defines bases, shows how to shrink a spanning set or enlarge an independent set to one, and proves the basic facts about dimension.
Definition of a Basis
Why it matters. A basis is a coordinate system. Spanning guarantees that every vector has an address in terms of the basis, and independence guarantees that the address is unique. With a basis chosen, abstract vectors become lists of numbers that can be stored and computed with (Section 6.5). Choosing a good basis is often the whole solution of a problem. Diagonalization (Chapter 8), Fourier analysis, JPEG compression, and principal component analysis are all choices of basis.
Definition. A set $\mathcal{B} = {\mathbf{b}_1, \dots, \mathbf{b}_n}$ in a vector space $V$ is a basis of $V$ if
- $\mathcal{B}$ is linearly independent, and
- $\mathcal{B}$ spans $V$.
By convention, the empty set is a basis of ${\mathbf{0}}$.
Theorem (unique representation). $\mathcal{B}$ is a basis of $V$ if and only if every $\mathbf{v} \in V$ can be written as
$$\mathbf{v} = c_1\mathbf{b}_1 + \cdots + c_n\mathbf{b}_n$$
in exactly one way. This follows directly from Section 6.3: spanning gives at least one way, and independence gives at most one.
| Spans $V$ | Does not span $V$ | |
|---|---|---|
| Independent | basis: every vector has exactly one address | some vectors have no address |
| Dependent | every vector has many addresses | both problems |
too few just right too many
independent, not spanning independent and spanning spanning, not independent
{(1,0)} {(1,0), (0,1)} {(1,0), (0,1), (1,1)}
(0,1) has no address (3,2) = 3(1,0) + 2(0,1), (1,1) = 1(1,1)
and in no other way = 1(1,0) + 1(0,1)
Two characterizations. For a finite set $\mathcal{B}$ in $V$, the following are equivalent:
- $\mathcal{B}$ is a basis.
- $\mathcal{B}$ is a minimal spanning set: it spans $V$, but no proper subset does.
- $\mathcal{B}$ is a maximal independent set: it is independent, but adding any vector of $V$ makes it dependent.
Proof sketch. A spanning set that is dependent has a redundant vector (Section 6.3), which can be removed without losing the span, so a minimal spanning set must be independent. An independent set that does not span misses some $\mathbf{v}$, and adding $\mathbf{v}$ keeps it independent, so a maximal independent set must span. $\blacksquare$
Bases are not unique. $\mathbb{R}^2$ has infinitely many bases: any two non-parallel vectors form one. For $n$ vectors in $\mathbb{R}^n$, the Invertible Matrix Theorem (Section 4.3) gives a one-step test:
$${\mathbf{b}_1, \dots, \mathbf{b}_n} \text{ is a basis of } \mathbb{R}^n \iff P = [,\mathbf{b}_1 \ \cdots \ \mathbf{b}_n,] \text{ is invertible} \iff \det P \ne 0.$$
Example. ${(1, 1), (1, -1)}$ is a basis of $\mathbb{R}^2$, because $\det\begin{bmatrix} 1 & 1 \ 1 & -1 \end{bmatrix} = -2 \ne 0$. The address of $(7, 4)$ is the unique solution of $c_1(1, 1) + c_2(1, -1) = (7, 4)$, which is $c_1 = \tfrac{11}{2}$, $c_2 = \tfrac32$. This is the computation from Section 2.2, now read as finding coordinates.
import numpy as np
def is_basis_of_Rn(*vectors):
P = np.column_stack(vectors)
n_rows, n_cols = P.shape
return n_rows == n_cols and np.linalg.matrix_rank(P) == n_cols # square and invertible
print(is_basis_of_Rn([1, 1], [1, -1])) # True
print(is_basis_of_Rn([1, 2], [2, 4])) # False: parallel
print(is_basis_of_Rn([1, 0, 0], [0, 1, 0])) # False: independent but does not span R^3
print(is_basis_of_Rn([1, 2, 1], [2, 1, 0], [1, -1, -1])) # False: the third is the second minus the first
# Unique address of (7, 4) in the basis {(1, 1), (1, -1)}
P = np.array([[1, 1], [1, -1]])
print(np.linalg.solve(P, [7, 4])) # [5.5 1.5]
Key takeaways
- A basis is an independent spanning set; equivalently, every vector has exactly one representation in it.
- A basis is both a minimal spanning set and a maximal independent set.
- Bases are not unique; choosing a convenient basis is a central technique.
- $n$ vectors form a basis of $\mathbb{R}^n$ exactly when the matrix with those columns is invertible.
🧪 Practice
- Is ${(1, 2, 1), (2, 1, 0), (1, -1, -1)}$ a basis of $\mathbb{R}^3$? If not, find a dependence relation and replace one vector to make it a basis.
- Show that ${1,\ 1 + x,\ 1 + x + x^2}$ is a basis of $\mathbb{P}_2$.
- Prove that a minimal spanning set is linearly independent.
- Interview: An image can be stored as pixel values or as JPEG coefficients. In linear algebra terms, what is the relationship between the two, and why does the second representation compress so much better? Hint: the same vector in two bases (pixel basis versus a cosine basis); most natural images have only a few large coefficients in the cosine basis.
Standard Bases
Why it matters. Most familiar spaces come with one especially simple basis, in which a vector's coordinates are just the numbers used to write it down: entries of a tuple, coefficients of a polynomial, entries of a matrix. These standard bases are the default coordinate systems that software uses. Knowing them, and knowing that they are a convention rather than a law, makes it easier to switch to better bases when a problem calls for it.
The standard bases.
| Space | Standard basis | Dimension | Coordinates of a vector |
|---|---|---|---|
| $\mathbb{R}^n$ | $\mathbf{e}_1, \dots, \mathbf{e}_n$, the columns of $I_n$ | $n$ | its entries |
| $\mathbb{P}_n$ | $1, x, x^2, \dots, x^n$ (the monomials) | $n + 1$ | its coefficients $a_0, \dots, a_n$ |
| $\mathbb{R}^{m \times n}$ | $E_{ij}$: 1 in position $(i, j)$, 0 elsewhere | $mn$ | its entries $a_{ij}$ |
| $\mathbb{C}^n$ over $\mathbb{C}$ | $\mathbf{e}_1, \dots, \mathbf{e}_n$ | $n$ | its complex entries |
| $\mathbb{C}^n$ over $\mathbb{R}$ | $\mathbf{e}_1, i\mathbf{e}_1, \dots, \mathbf{e}_n, i\mathbf{e}_n$ | $2n$ | real and imaginary parts |
| $\mathbb{F}_2^n$ | $\mathbf{e}_1, \dots, \mathbf{e}_n$ | $n$ | its bits |
| ${\mathbf{0}}$ | $\varnothing$ | $0$ | none |
Independence of the monomials: if $a_0 + a_1x + \cdots + a_nx^n$ is the zero function, then all $a_i = 0$, because a nonzero polynomial of degree at most $n$ has at most $n$ roots.
Ordering matters for matrices. To turn a matrix into a coordinate vector, the $E_{ij}$ must be listed in some order. Two conventions are common:
A = [ a b c ] row-major (C order, NumPy default): (a, b, c, d, e, f)
[ d e f ] column-major (Fortran order, LAPACK, (a, d, b, e, c, f)
MATLAB, and the vec operator):
Mixing the two conventions silently transposes data. Both are valid choices of an ordered basis.
Infinite-dimensional spaces. $\mathbb{P}$, the space of all polynomials, has the infinite basis ${1, x, x^2, \dots}$. Every polynomial is a finite combination of monomials. In the space of all real sequences $\mathbb{R}^\infty$, the vectors $\mathbf{e}_1 = (1, 0, 0, \dots)$, $\mathbf{e}_2 = (0, 1, 0, \dots)$, ... are independent but do not span. Finite combinations of them produce only sequences with finitely many nonzero terms, so $(1, 1, 1, \dots)$ is missing. Bases of such spaces exist (assuming the axiom of choice) but cannot be written down. Analysis therefore replaces finite combinations with convergent series (Section 13.4).
Other useful bases. "Standard" means convenient, not best. Each of the following is a basis of $\mathbb{P}_n$ or $\mathbb{R}^n$ that makes some task easy:
| Basis | Space | Makes easy |
|---|---|---|
| Lagrange polynomials $L_0, \dots, L_n$ at nodes $x_0, \dots, x_n$ | $\mathbb{P}_n$ | interpolation: the coordinates of $p$ are its values $p(x_j)$ |
| Taylor basis $1, (x - a), \dots, (x - a)^n$ | $\mathbb{P}_n$ | local approximation: the coordinates are $p^{(k)}(a)/k!$ |
| Bernstein polynomials | $\mathbb{P}_n$ | Bezier curves in graphics |
| Chebyshev polynomials | $\mathbb{P}_n$ | numerically stable approximation |
| Fourier (sines and cosines) | $\mathbb{R}^n$ | frequency analysis (Section 13.3) |
| Haar wavelets | $\mathbb{R}^{2^k}$ | multiresolution signal and image compression |
The Lagrange basis is defined by $L_j(x_i) = 1$ if $i = j$ and $0$ otherwise. Then any $p \in \mathbb{P}_n$ equals $\sum_j p(x_j)L_j$, because both sides have the same values at $n + 1$ points.
from functools import reduce
import numpy as np
from numpy.polynomial import Polynomial as P
# R^n: v is the combination of the standard basis vectors with its own entries as weights
v = np.array([4., -1., 2.])
E = np.eye(3)
print(sum(v[i] * E[:, i] for i in range(3))) # [ 4. -1. 2.]
# R^{2x3}: the E_ij in row-major order rebuild A from its entries
A = np.array([[1, 2, 3], [4, 5, 6]])
basis = [np.eye(1, 6, k).reshape(2, 3) for k in range(6)] # E_11, E_12, E_13, E_21, E_22, E_23
print(np.array_equal(sum(c * B for c, B in zip(A.flatten(), basis)), A)) # True
print(A.flatten(order='C'), A.flatten(order='F')) # [1 2 3 4 5 6] [1 4 2 5 3 6]
# Lagrange basis of P_2 at the nodes 0, 1, 2
nodes = [0, 1, 2]
def lagrange(j):
factors = [P([-xm, 1]) / (nodes[j] - xm) for m, xm in enumerate(nodes) if m != j]
return reduce(lambda p, q: p * q, factors) # product of (x - x_m) / (x_j - x_m)
L = [lagrange(j) for j in range(3)]
print(np.round([[Lj(xi) for xi in nodes] for Lj in L], 10)) # identity matrix: L_j(x_i) = 1 iff i == j
# The coordinates of p in the Lagrange basis are its values at the nodes
p = P([1, -2, 3]) # 1 - 2x + 3x^2
q = sum(p(xj) * Lj for xj, Lj in zip(nodes, L))
print(np.round(q.coef, 10)) # [ 1. -2. 3.]: the same polynomial
Key takeaways
- Standard bases: $\mathbf{e}_i$ for $\mathbb{R}^n$, monomials for $\mathbb{P}n$, $E{ij}$ for $\mathbb{R}^{m \times n}$; in them, coordinates are the usual entries or coefficients.
- An ordered basis needs an order; row-major and column-major flattening of matrices are two different orderings.
- ${1, x, x^2, \dots}$ is a basis of $\mathbb{P}$, but the $\mathbf{e}_i$ do not span the space of all sequences.
- Non-standard bases (Lagrange, Taylor, Fourier, wavelets) make specific tasks easy.
🧪 Practice
- Write the coordinates of $\begin{bmatrix} 2 & -1 \ 0 & 5 \end{bmatrix}$ in the standard basis of $\mathbb{R}^{2 \times 2}$, in row-major and in column-major order.
- Find the Lagrange basis of $\mathbb{P}_2$ for the nodes $-1, 0, 1$, and express $x^2$ in it.
- Explain why $\mathbf{e}_1, \mathbf{e}_2, \dots$ do not span the space of all real sequences, but do span the space of sequences with only finitely many nonzero terms.
- Interview: A pipeline reshapes a $1000 \times 3$ NumPy array (row-major) into a vector, hands it to a Fortran library (column-major), and reshapes the result back. The output looks scrambled. What happened, in terms of ordered bases, and how do you fix it? Hint: the same list of numbers is a coordinate vector relative to two different orderings of the $E_{ij}$.
Spanning Sets and Basis Extraction
Why it matters. Data rarely arrive as a basis. You get a list of generators, such as measurement vectors, features, or the columns of a matrix, and many of them are redundant. Extracting a basis removes the redundancy while keeping the span. The pivot-column method also explains which columns of a matrix to keep in feature selection, and it is the standard way to find a basis for a column space (Section 6.6).
Spanning set theorem. If a finite set $S$ spans a subspace $W \ne {\mathbf{0}}$, then some subset of $S$ is a basis of $W$.
Proof. If $S$ is independent, it is already a basis. Otherwise, by the linear dependence lemma (Section 6.3), some vector of $S$ is a combination of the others. Remove it; the span is unchanged. Repeat. The process stops, since $S$ is finite, and it stops at an independent set that still spans $W$. $\blacksquare$
Method 1: pivot columns (keeps original vectors).
- Put the vectors in the columns of $A$.
- Row reduce to find the pivot columns.
- The corresponding columns of the original $A$ form a basis of $\operatorname{Span}(S) = \operatorname{Col} A$.
This works because row operations preserve every linear relation among the columns (Section 6.3). The non-pivot columns are combinations of the pivot columns in $R$, hence also in $A$. The pivot columns are independent in $R$, hence also in $A$.
Pitfall. The pivot columns of $R$ itself are usually not in $\operatorname{Span}(S)$. Row operations change the column space; they only preserve the relations among columns.
Method 2: row reduction of rows (simpler vectors). Put the vectors in the rows of a matrix and row reduce. Row operations do not change the row space (Section 6.6), so the nonzero rows of the echelon form are a basis of the span. These basis vectors are usually not among the originals, but they are simpler, with many zeros.
| Method 1: vectors as columns | Method 2: vectors as rows | |
|---|---|---|
| Basis vectors | a subset of the original vectors | new vectors (rows of the echelon form) |
| Good for | interpretation, feature selection | simple descriptions, comparing spans |
| Also gives | the relations expressing the dropped vectors | nothing about the dropped vectors |
Example (running example). For $\mathbf{v}_1 = (1, 2, 0, 1)$, $\mathbf{v}_2 = (2, 4, 1, 3)$, $\mathbf{v}_3 = (0, 0, 1, 1)$, $\mathbf{v}_4 = (1, 1, 1, 1)$, the pivots of $A = [,\mathbf{v}_1\ \mathbf{v}_2\ \mathbf{v}_3\ \mathbf{v}_4,]$ are in columns 1, 2, 4. So ${\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_4}$ is a basis of their span, and $\mathbf{v}_3 = -2\mathbf{v}_1 + \mathbf{v}_2$ is redundant. The span is a 3-dimensional subspace of $\mathbb{R}^4$ given by one equation, $b_1 - b_2 - b_3 + b_4 = 0$. The first pivot column of $R$, $\mathbf{e}_1$, violates that equation, which illustrates the pitfall.
Greedy view. Method 1 is the same as scanning the list from left to right and keeping each vector that is not in the span of the vectors already kept. Since the result depends on the order of the list, a different order can give a different basis of the same subspace. In floating-point work, a column-pivoted QR factorization makes this choice robustly. It greedily picks the column that adds the most new length at each step.
import sympy as sp
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 0, 1],
[0, 1, 1, 1],
[1, 3, 1, 1]]) # columns v1, v2, v3, v4 (running example)
# Method 1: pivot columns of the ORIGINAL matrix
R, pivots = A.rref()
print(pivots) # (0, 1, 3): keep v1, v2, v4
# Pitfall: the pivot columns of R are generally not in Col A
in_col_A = lambda b: A.rank() == A.row_join(b).rank()
print(in_col_A(R[:, 0]), in_col_A(A[:, 0])) # False True
# Greedy left-to-right scan gives the same subset
def greedy_basis(vectors):
kept = []
for v in vectors:
if sp.Matrix.hstack(*kept, v).rank() > len(kept): # v adds a new direction
kept.append(v)
return kept
cols = [A[:, j] for j in range(A.cols)]
print([cols.index(v) for v in greedy_basis(cols)]) # [0, 1, 3]
print([cols.index(v) for v in greedy_basis(cols[::-1])]) # [3, 2, 1]: reversed order, a different basis
# Method 2: vectors as rows; the nonzero rows of the RREF are a (new, simpler) basis
Rrows = A.T.rref()[0]
print([list(Rrows.row(i)) for i in range(Rrows.rows) if any(Rrows.row(i))])
# [[1, 0, 0, -1], [0, 1, 0, 1], [0, 0, 1, 1]]
Key takeaways
- Every finite spanning set contains a basis; remove redundant vectors one at a time.
- Pivot columns of the original matrix form a basis of the column space; pivot columns of the RREF generally do not lie in it.
- Nonzero rows of an echelon form give a different, simpler basis of the span of the rows.
- The extracted basis depends on the order of the vectors; there is no single "correct" subset.
🧪 Practice
- Extract a basis from $(1, 0, 1)$, $(2, 0, 2)$, $(0, 1, 1)$, $(1, 1, 2)$, $(0, 0, 1)$, and express each discarded vector in terms of the basis.
- Find a basis of $\operatorname{Span}{1 + x,\ 2 + 2x,\ x^2,\ 1 + x + x^2}$ in $\mathbb{P}_2$, and state its dimension.
- Explain why row operations preserve linear relations among columns but can change the column space. Give a $2 \times 2$ example where the column space changes.
- Interview: For a model with 500 partly redundant features, would you rather present stakeholders with a basis made of original features (method 1) or with new combined features (method 2 or PCA)? What would you use numerically on noisy data? Hint: interpretability versus conditioning; column-pivoted QR selects original columns robustly.
Extending to a Basis
Why it matters. Many arguments start with a few vectors you already care about and need a full basis that contains them. Examples are an eigenvector you have found, a known solution, or a camera's viewing direction. Extension is the mirror image of extraction: extraction shrinks a spanning set down to a basis, and extension grows an independent set up to one. It is used in proofs throughout the course, including the dimension formula below, the Schur decomposition (Chapter 8), and Gram-Schmidt (Chapter 9).
Theorem. In a finite-dimensional space $V$, every linearly independent set can be extended to a basis of $V$.
Proof. Let $\mathbf{u}_1, \dots, \mathbf{u}_k$ be independent, and let $\mathbf{w}_1, \dots, \mathbf{w}_m$ be any spanning set of $V$. The combined list $\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_1, \dots, \mathbf{w}_m$ spans $V$. Extract a basis by the left-to-right greedy scan. No $\mathbf{u}_i$ is discarded, because the $\mathbf{u}$'s come first and are independent. $\blacksquare$
Algorithm (in $\mathbb{R}^n$). Form $[,\mathbf{u}_1 \ \cdots \ \mathbf{u}_k \mid \mathbf{e}_1 \ \cdots \ \mathbf{e}_n,]$, find its pivot columns, and keep the corresponding original columns. The first $k$ columns are all pivots, and the $\mathbf{e}_j$ that are kept complete the basis.
Example. Extend $\mathbf{u}_1 = (1, 1, 0, 0)$, $\mathbf{u}_2 = (0, 1, 1, 0)$ to a basis of $\mathbb{R}^4$.
- $\mathbf{e}_1$ is not in $\operatorname{Span}{\mathbf{u}_1, \mathbf{u}_2}$, since every vector there has the form $(a, a + b, b, 0)$. Keep it.
- $\mathbf{e}_2 = \mathbf{u}_1 - \mathbf{e}_1$. Discard it.
- $\mathbf{e}_3 = \mathbf{u}_2 - \mathbf{u}_1 + \mathbf{e}_1$. Discard it.
- $\mathbf{e}_4$ has a nonzero fourth entry, which none of the kept vectors has. Keep it.
Result: ${\mathbf{u}_1, \mathbf{u}_2, \mathbf{e}_1, \mathbf{e}_4}$.
Complements exist. The added vectors span a complement of $U = \operatorname{Span}{\mathbf{u}_1, \dots, \mathbf{u}_k}$ (Section 6.2). In the example, $\mathbb{R}^4 = U \oplus \operatorname{Span}{\mathbf{e}_1, \mathbf{e}_4}$. So every subspace of a finite-dimensional space has a complement, though not a unique one.
given (independent) candidates (spanning) result (basis)
u1, u2 + e1, e2, e3, e4 -> u1, u2, e1, e4
\_______________/ \___________________/ \____/ \____/
must all survive keep only those that U a complement of U
add a new direction
import sympy as sp
U = [sp.Matrix([1, 1, 0, 0]), sp.Matrix([0, 1, 1, 0])]
M = sp.Matrix.hstack(*U, sp.eye(4)) # [u1 u2 | e1 e2 e3 e4]
_, pivots = M.rref()
print(pivots) # (0, 1, 2, 5): u1, u2, e1, e4
basis = [M[:, j] for j in pivots]
print(sp.Matrix.hstack(*basis).det()) # 1: nonzero, so a basis of R^4
# Extending {1 + x^2} to a basis of P_2, working with coefficient vectors (1, x, x^2)
M2 = sp.Matrix.hstack(sp.Matrix([1, 0, 1]), sp.eye(3))
print(M2.rref()[1]) # (0, 1, 2): keep 1 + x^2, then 1 and x
Key takeaways
- Every independent set in a finite-dimensional space extends to a basis.
- Algorithm: append a spanning set (such as the standard basis) after the given vectors and keep the pivot columns.
- The added vectors span a complement, so every subspace has a complement.
- Extraction (shrink a spanning set) and extension (grow an independent set) both meet at a basis.
🧪 Practice
- Extend ${(1, 2, 3)}$ to a basis of $\mathbb{R}^3$, and give a second, different extension.
- Extend ${1 + x^2,\ x - x^2}$ to a basis of $\mathbb{P}_2$.
- Prove that if $U$ is a subspace of a finite-dimensional space $V$, then there is a subspace $W$ with $V = U \oplus W$.
- Interview: In 3D graphics you know a camera's viewing direction $\mathbf{d}$ and need two more vectors to complete a coordinate frame. How do you construct them robustly, without failing for particular directions? Hint: extend by the standard basis vector least aligned with $\mathbf{d}$ (smallest $\lvert d_i \rvert$), then use cross products (Section 2.4) to get perpendicular vectors.
Dimension of a Vector Space
Why it matters. "Plane" and "3D space" are informal ideas of dimension. The definition here makes them precise for any vector space: the number of independent directions, or equivalently the number of free parameters needed to specify a vector. Dimension predicts, before any computation, whether a set of vectors can be independent or can span. It also says that two spaces of the same dimension are structurally identical (Section 6.5).
Theorem (invariance of dimension). If $V$ has a basis with $n$ vectors, then every basis of $V$ has exactly $n$ vectors.
Proof. Let $\mathcal{B}$ and $\mathcal{C}$ be bases with $n$ and $m$ vectors. $\mathcal{B}$ spans and $\mathcal{C}$ is independent, so $m \le n$ by the replacement theorem (Section 6.3). Swapping roles, $n \le m$. $\blacksquare$
Definition. The dimension of $V$, written $\dim V$, is the number of vectors in any basis. $\dim{\mathbf{0}} = 0$. If $V$ has no finite spanning set, $V$ is infinite-dimensional.
| Space | Dimension | Reason (a basis, or a parameter count) |
|---|---|---|
| $\mathbb{R}^n$ | $n$ | $\mathbf{e}_1, \dots, \mathbf{e}_n$ |
| $\mathbb{P}_n$ | $n + 1$ | $1, x, \dots, x^n$; not $n$ |
| $\mathbb{R}^{m \times n}$ | $mn$ | the $E_{ij}$ |
| Symmetric $n \times n$ | $\frac{n(n+1)}{2}$ | free choice on and above the diagonal |
| Skew-symmetric $n \times n$ | $\frac{n(n-1)}{2}$ | diagonal forced to zero; free choice above it |
| Upper triangular $n \times n$ | $\frac{n(n+1)}{2}$ | entries on and above the diagonal |
| Trace-zero $n \times n$ | $n^2 - 1$ | one linear condition on $n^2$ entries |
| $\mathbb{C}^n$ over $\mathbb{R}$ | $2n$ | real and imaginary parts |
| $\mathbb{P}$, $C[a, b]$, $\mathbb{R}^\infty$ | $\infty$ | $1, x, x^2, \dots$ are independent for every length |
As a check, symmetric plus skew-symmetric gives $\frac{n(n+1)}{2} + \frac{n(n-1)}{2} = n^2$, consistent with $\mathbb{R}^{n \times n} = \text{Sym} \oplus \text{Skew}$ (Section 6.2).
Consequences in a space of dimension $n$.
| Statement | Reason |
|---|---|
| More than $n$ vectors are always dependent | Replacement theorem |
| Fewer than $n$ vectors never span | A spanning set contains a basis, which has $n$ vectors |
| $n$ independent vectors automatically span | Otherwise extend to a basis with more than $n$ vectors |
| $n$ spanning vectors are automatically independent | Otherwise extract a basis with fewer than $n$ vectors |
The last two rows form the basis theorem. With exactly $n$ vectors, checking either independence or spanning is enough. This halves the work and generalizes the "square matrix" part of the Invertible Matrix Theorem.
Counting dimensions with constraints. A subspace of an $N$-dimensional space defined by $k$ independent homogeneous linear conditions has dimension $N - k$. This is rank-nullity in disguise (Section 6.6). For example, symmetric $n \times n$ matrices satisfy the $\binom{n}{2}$ conditions $a_{ij} = a_{ji}$ for $i < j$, leaving $n^2 - \binom{n}{2} = \frac{n(n+1)}{2}$.
from itertools import combinations
import numpy as np
def dim_of_matrix_subspace(n, constraints):
"""dim {A in R^{n x n} : every constraint is 0} = n^2 - rank of the constraint system.
Each constraint is a linear function of A; applying it to each E_ij gives one row."""
E = [np.eye(1, n * n, k).reshape(n, n) for k in range(n * n)]
C = np.array([[con(Eij) for Eij in E] for con in constraints(n)])
return n * n - np.linalg.matrix_rank(C)
sym = lambda n: [lambda A, i=i, j=j: A[i, j] - A[j, i] for i, j in combinations(range(n), 2)]
skew = lambda n: [lambda A, i=i, j=j: A[i, j] + A[j, i] for i in range(n) for j in range(i, n)]
tr0 = lambda n: [lambda A: np.trace(A)]
for n in [2, 3, 4]:
print(n, dim_of_matrix_subspace(n, sym), dim_of_matrix_subspace(n, skew), dim_of_matrix_subspace(n, tr0))
# 2 3 1 3
# 3 6 3 8
# 4 10 6 15
# Basis theorem: 3 independent vectors in R^3 automatically span
B = np.array([[1, 1, 0], [0, 1, 1], [1, 0, 1]]).T
print(np.linalg.matrix_rank(B)) # 3: independent, hence a basis of R^3
Key takeaways
- All bases of a space have the same size; that number is the dimension.
- $\dim\mathbb{P}_n = n + 1$, $\dim\mathbb{R}^{m \times n} = mn$, and symmetric $n \times n$ matrices have dimension $n(n+1)/2$.
- In an $n$-dimensional space, more than $n$ vectors are dependent and fewer than $n$ cannot span.
- Basis theorem: $n$ vectors in an $n$-dimensional space form a basis if they are independent or if they span.
- $k$ independent homogeneous linear conditions cut the dimension down by $k$.
🧪 Practice
- Find the dimension of ${p \in \mathbb{P}_4 : p(1) = 0 \text{ and } p(-1) = 0}$ and give a basis.
- What is the dimension of the space of $3 \times 3$ upper triangular matrices with trace $0$? Of the $3 \times 3$ matrices whose rows all sum to zero?
- Use the basis theorem to show that ${1,\ x - 1,\ (x - 1)^2}$ is a basis of $\mathbb{P}_2$ by checking only independence.
- Interview: A colleague fits a linear model with 1,000 coefficients to 500 data points and says the model "uses all 1,000 dimensions" of the parameter space. What is wrong with this claim, and how large is the set of parameter vectors that fit the data equally well? Hint: the $500 \times 1000$ data matrix has rank at most 500, so its null space has dimension at least 500.
Dimension of Subspaces
Why it matters. Dimension behaves predictably under the subspace operations of Section 6.2. A subspace is never larger than the whole space, and the dimension of a sum is given by an inclusion-exclusion formula. These facts let you prove that subspaces must intersect, or must fill the space, by counting alone. An example is "two planes through the origin in $\mathbb{R}^3$ always share a line". They also complete the classification of subspaces of $\mathbb{R}^n$.
Theorem. If $W$ is a subspace of a finite-dimensional space $V$, then $W$ is finite-dimensional and $\dim W \le \dim V$. Moreover, $\dim W = \dim V$ if and only if $W = V$.
Proof. An independent set in $W$ is independent in $V$, so it has at most $\dim V$ vectors. A maximal independent set in $W$ is therefore finite, and it is a basis of $W$. If $\dim W = \dim V = n$, a basis of $W$ is $n$ independent vectors in $V$, which span $V$ by the basis theorem. $\blacksquare$
The equality case is a powerful tool. To prove two subspaces are equal, it suffices to show that one contains the other and that they have the same dimension.
Classification. The subspaces of $\mathbb{R}^n$ are sorted by dimension $0, 1, \dots, n$. In $\mathbb{R}^3$ these are ${\mathbf{0}}$, lines through $\mathbf{0}$, planes through $\mathbf{0}$, and $\mathbb{R}^3$, which completes the argument begun in Section 6.2.
Dimension of a sum (Grassmann's formula). For finite-dimensional subspaces $U$ and $W$,
$$\dim(U + W) = \dim U + \dim W - \dim(U \cap W).$$
Proof sketch. Take a basis $\mathbf{z}_1, \dots, \mathbf{z}_k$ of $U \cap W$. Extend it to a basis of $U$ by adding $\mathbf{u}_1, \dots, \mathbf{u}_p$, and to a basis of $W$ by adding $\mathbf{w}_1, \dots, \mathbf{w}_q$. The combined list $\mathbf{z}$'s, $\mathbf{u}$'s, $\mathbf{w}$'s spans $U + W$. One can check that it is independent. So $\dim(U + W) = k + p + q = (k + p) + (k + q) - k$. $\blacksquare$
It parallels counting elements of a union, $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert$. The overlap is counted twice and must be subtracted once.
U + W
+--------------------------------------------+
| U |
| +---------------------+ |
| | u_1 .. u_p +-----+--------------+ |
| | | z_1 .. z_k (U ∩ W)| |
| +---------------+-----+ | |
| | w_1 .. w_q W | |
| +--------------------+ |
+--------------------------------------------+
dim(U + W) = p + k + q = (p + k) + (k + q) - k
Consequences by counting.
- Two planes through $\mathbf{0}$ in $\mathbb{R}^3$: $\dim(U \cap W) = 2 + 2 - \dim(U + W) \ge 4 - 3 = 1$. They share at least a line.
- Two planes through $\mathbf{0}$ in $\mathbb{R}^4$ can meet only in ${\mathbf{0}}$, since $2 + 2 - 4 = 0$.
- In general, $\dim(U \cap W) \ge \dim U + \dim W - \dim V$.
- $U + W$ is a direct sum exactly when $\dim(U + W) = \dim U + \dim W$.
Codimension. The number $\dim V - \dim W$ is the codimension of $W$, the number of independent linear equations needed to cut out $W$. A hyperplane through $\mathbf{0}$ is a subspace of codimension 1, such as a plane in $\mathbb{R}^3$ or ${\mathbf{x} \in \mathbb{R}^n : \mathbf{a} \cdot \mathbf{x} = 0}$ with $\mathbf{a} \ne \mathbf{0}$.
import numpy as np
rng = np.random.default_rng(42)
rank = np.linalg.matrix_rank
C = rng.normal(size=(6, 2)) # a 2D subspace that U and W will share
A = np.hstack([C, rng.normal(size=(6, 1))]) # U = Col A, dim 3
B = np.hstack([C, rng.normal(size=(6, 2))]) # W = Col B, dim 4
dim_U, dim_W = rank(A), rank(B)
dim_sum = rank(np.hstack([A, B]))
# Because the columns of A and of B are independent, dim(U ∩ W) = nullity of [A | -B]
dim_cap = A.shape[1] + B.shape[1] - rank(np.hstack([A, -B]))
print(dim_U, dim_W, dim_sum, dim_cap) # 3 4 5 2
print(dim_sum == dim_U + dim_W - dim_cap) # True
# Two random planes in R^3 always share a line; in R^4 they generically share only 0
for n in [3, 4]:
P1, P2 = rng.normal(size=(n, 2)), rng.normal(size=(n, 2))
print(n, 4 - rank(np.hstack([P1, -P2]))) # 3 1, then 4 0
Key takeaways
- A subspace of $V$ has dimension at most $\dim V$, with equality only for $V$ itself.
- To prove $W = V$, show $W \subseteq V$ and $\dim W = \dim V$.
- Grassmann: $\dim(U + W) = \dim U + \dim W - \dim(U \cap W)$.
- Counting dimensions forces intersections: $\dim(U \cap W) \ge \dim U + \dim W - \dim V$.
- Codimension counts the independent equations needed to define a subspace.
🧪 Practice
- $U$ and $W$ are subspaces of $\mathbb{R}^5$ with $\dim U = 3$ and $\dim W = 4$. What are the smallest and largest possible values of $\dim(U \cap W)$? Give examples achieving both.
- Prove that two distinct planes through the origin in $\mathbb{R}^3$ intersect in exactly a line.
- Let $U = {\mathbf{x} \in \mathbb{R}^4 : x_1 + x_2 = 0}$ and $W = {\mathbf{x} \in \mathbb{R}^4 : x_3 = x_4 = 0}$. Find $\dim U$, $\dim W$, $\dim(U \cap W)$, and $\dim(U + W)$, and check Grassmann's formula.
- Interview: Two recommendation models each represent users with a 40-dimensional subspace of the same 64-dimensional embedding space. What is the minimum possible dimension of the directions both models capture, and what does this imply for comparing the models? Hint: $40 + 40 - 64$.
<a id="65-coordinates-and-change-of-basis"></a>
6.5 Coordinates and Change of Basis
Choosing a basis turns abstract vectors into lists of numbers that a computer can store. Choosing a different basis changes the list but not the vector. This subchapter makes the translation precise, shows that it turns every $n$-dimensional space into a copy of $\mathbb{R}^n$, and computes how coordinates change when the basis changes.
Coordinate Vectors Relative to a Basis
Why it matters. Computers cannot store "the polynomial $p$" or "the function $f$". They store arrays of numbers. A basis provides the dictionary: each vector corresponds to the unique list of weights that rebuild it from the basis. Every numerical computation on abstract vectors, such as storing a polynomial as coefficients, an image as pixels, or a sound as samples, is a computation on coordinate vectors relative to some basis.
Definition. Let $\mathcal{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ be an ordered basis of $V$. For $\mathbf{v} \in V$, the unique scalars with $\mathbf{v} = c_1\mathbf{b}_1 + \cdots + c_n\mathbf{b}_n$ form the coordinate vector of $\mathbf{v}$ relative to $\mathcal{B}$:
$$[\mathbf{v}]_{\mathcal{B}} = \begin{bmatrix} c_1 \ \vdots \ c_n \end{bmatrix} \in F^n.$$
The order of the basis vectors matters: swapping $\mathbf{b}_1$ and $\mathbf{b}2$ swaps $c_1$ and $c_2$. Relative to the standard basis $\mathcal{E}$ of $\mathbb{R}^n$, $[\mathbf{v}]{\mathcal{E}} = \mathbf{v}$.
Computing coordinates in $\mathbb{R}^n$. Let $P_{\mathcal{B}} = [,\mathbf{b}_1 \ \cdots \ \mathbf{b}_n,]$. The definition says
$$\mathbf{v} = P_{\mathcal{B}},[\mathbf{v}]{\mathcal{B}}, \qquad\text{so}\qquad [\mathbf{v}]{\mathcal{B}} = P_{\mathcal{B}}^{-1}\mathbf{v}.$$
In practice, solve $P_{\mathcal{B}}\mathbf{c} = \mathbf{v}$ rather than forming the inverse (Section 4.3).
Example. Let $\mathcal{B} = \big((2, 1), (-1, 1)\big)$ and $\mathbf{v} = (3, 3)$. Solving $2c_1 - c_2 = 3$, $c_1 + c_2 = 3$ gives $c_1 = 2$, $c_2 = 1$, so $[\mathbf{v}]_{\mathcal{B}} = (2, 1)$. The same arrow has address $(3, 3)$ on the standard grid and $(2, 1)$ on the skewed grid of $\mathcal{B}$:
standard grid: v = 3 e1 + 3 e2 skewed grid of B: v = 2 b1 + 1 b2
y b1 = (2, 1), b2 = (-1, 1)
3 + . . * v
| 0 --b1--> (2, 1) --b1--> (4, 2) --b2--> (3, 3) = v
2 + . . .
| walk 2 steps along b1, then 1 step along b2
1 + . . .
| [v]_E = (3, 3) [v]_B = (2, 1)
0 +---+---+---+--> x one vector, two addresses
0 1 2 3
Example in $\mathbb{P}_2$. Let $\mathcal{B} = (1,\ 1 + x,\ 1 + x + x^2)$ and $p = 5 - x + 2x^2$. Matching coefficients in $c_1 \cdot 1 + c_2(1 + x) + c_3(1 + x + x^2) = 5 - x + 2x^2$:
$$x^2:\ c_3 = 2, \qquad x:\ c_2 + c_3 = -1, \qquad 1:\ c_1 + c_2 + c_3 = 5,$$
so $c_3 = 2$, $c_2 = -3$, $c_1 = 6$, and $[p]_{\mathcal{B}} = (6, -3, 2)$.
Analogy. A vector is a place; coordinates are its address in a particular addressing system. The same building has a street address, GPS coordinates, and a grid reference on a city map. Converting between them does not move the building. In the same way, changing basis changes the numbers, not the vector.
import numpy as np
import sympy as sp
# Coordinates in R^2: solve P_B c = v
PB = np.array([[2., -1.],
[1., 1.]]) # columns b1 = (2, 1), b2 = (-1, 1)
v = np.array([3., 3.])
c = np.linalg.solve(PB, v)
print(c) # [2. 1.]
print(PB @ c) # [3. 3.]: rebuilding v from its coordinates
# Order matters: swapping the basis vectors swaps the coordinates
print(np.linalg.solve(PB[:, ::-1], v)) # [1. 2.]
# Coordinates in P_2 relative to B = (1, 1 + x, 1 + x + x^2)
x = sp.symbols('x')
B = [sp.Integer(1), 1 + x, 1 + x + x**2]
c1, c2, c3 = sp.symbols('c1:4')
p = 5 - x + 2*x**2
eqs = sp.Poly(c1*B[0] + c2*B[1] + c3*B[2] - p, x).all_coeffs()
print(sp.solve(eqs, [c1, c2, c3])) # {c1: 6, c2: -3, c3: 2}
Key takeaways
- $[\mathbf{v}]_{\mathcal{B}}$ lists the unique weights that rebuild $\mathbf{v}$ from the ordered basis $\mathcal{B}$.
- In $\mathbb{R}^n$: $\mathbf{v} = P_{\mathcal{B}}[\mathbf{v}]{\mathcal{B}}$, so coordinates come from solving $P{\mathcal{B}}\mathbf{c} = \mathbf{v}$.
- In other spaces, coordinates come from matching coefficients, which is again a linear system.
- Coordinates depend on the basis and its order; the vector itself does not.
🧪 Practice
- Find $[\mathbf{v}]_{\mathcal{B}}$ for $\mathbf{v} = (1, 2, 3)$ and $\mathcal{B} = \big((1, 0, 0), (1, 1, 0), (1, 1, 1)\big)$.
- If $[\mathbf{v}]_{\mathcal{B}} = (2, -1)$ for $\mathcal{B} = \big((1, 2), (3, 4)\big)$, what is $\mathbf{v}$?
- Find the coordinates of $\begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}$ relative to the basis $\left(\begin{bmatrix} 1 & 0 \ 0 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 1 \ 0 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 1 \ 1 & 1 \end{bmatrix}\right)$ of $\mathbb{R}^{2 \times 2}$.
- Interview: Why should coordinates be computed with
np.linalg.solve(P, v)rather thannp.linalg.inv(P) @ v? When might forming the inverse still be reasonable? Hint: operation counts and rounding error (Section 4.3); many right-hand sides can reuse one LU factorization (Section 4.4).
Coordinate Mapping and Isomorphism to R^n
Why it matters. This topic explains why the methods of Sections 6.3 and 6.4 worked on polynomials and matrices. The coordinate map turns any $n$-dimensional space into $F^n$ while preserving addition and scaling, so every question about span, independence, or dimension can be answered in $F^n$ with row reduction. It also gives the deepest fact about finite-dimensional vector spaces: up to relabeling, there is only one of each dimension.
The coordinate map. For an ordered basis $\mathcal{B}$ of $V$ with $n$ vectors, define
$$T_{\mathcal{B}} : V \to F^n, \qquad T_{\mathcal{B}}(\mathbf{v}) = [\mathbf{v}]_{\mathcal{B}}.$$
Theorem. $T_{\mathcal{B}}$ is linear, one-to-one, and onto:
- $[\mathbf{u} + \mathbf{w}]{\mathcal{B}} = [\mathbf{u}]{\mathcal{B}} + [\mathbf{w}]{\mathcal{B}}$ and $[c\mathbf{u}]{\mathcal{B}} = c,[\mathbf{u}]_{\mathcal{B}}$;
- $[\mathbf{u}]{\mathcal{B}} = [\mathbf{w}]{\mathcal{B}}$ implies $\mathbf{u} = \mathbf{w}$;
- every $\mathbf{c} \in F^n$ is $[\mathbf{v}]_{\mathcal{B}}$ for $\mathbf{v} = c_1\mathbf{b}_1 + \cdots + c_n\mathbf{b}_n$.
Proof of 1. If $\mathbf{u} = \sum c_i\mathbf{b}_i$ and $\mathbf{w} = \sum d_i\mathbf{b}_i$, then $\mathbf{u} + \mathbf{w} = \sum (c_i + d_i)\mathbf{b}_i$. By uniqueness of coordinates, these are the coordinates of $\mathbf{u} + \mathbf{w}$. Scaling is similar. Parts 2 and 3 follow from uniqueness and spanning. $\blacksquare$
A linear bijection between vector spaces is called an isomorphism (Chapter 7). So every $n$-dimensional space over $F$ is isomorphic to $F^n$.
Consequence: compute in $F^n$. Because $T_{\mathcal{B}}$ preserves linear combinations and is one-to-one,
$$c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0} \iff c_1[\mathbf{v}1]{\mathcal{B}} + \cdots + c_k[\mathbf{v}k]{\mathcal{B}} = \mathbf{0}.$$
Hence:
- $\mathbf{v}_1, \dots, \mathbf{v}_k$ are independent in $V$ $\iff$ their coordinate vectors are independent in $F^n$;
- $\mathbf{v} \in \operatorname{Span}{\mathbf{v}i}$ $\iff$ $[\mathbf{v}]{\mathcal{B}} \in \operatorname{Span}{[\mathbf{v}i]{\mathcal{B}}}$;
- the dimension of a subspace of $V$ equals the dimension of its image in $F^n$.
V (abstract: polynomials, matrices, ...) F^n (arrays a computer can handle)
v1, ..., vk ---------------- [ . ]_B ----------------> [v1]_B, ..., [vk]_B
| |
independent? in the span? row reduce, rank, solve
dimension of the span? |
| |
answer <------------ same answer (T_B is linear and one-to-one) ------ answer
Same dimension, same space. Composing coordinate maps shows that any two $n$-dimensional spaces over $F$ are isomorphic. For example, $\mathbb{P}_3 \cong \mathbb{R}^4 \cong \mathbb{R}^{2 \times 2}$, via
$$a_0 + a_1x + a_2x^2 + a_3x^3 ;\longleftrightarrow; (a_0, a_1, a_2, a_3) ;\longleftrightarrow; \begin{bmatrix} a_0 & a_1 \ a_2 & a_3 \end{bmatrix}.$$
As vector spaces, these are the same; dimension is the only invariant.
Caveat: only linear structure is preserved. An isomorphism respects addition and scalar multiplication, nothing more. Other structure does not transfer through coordinates:
| Structure in $V$ | Preserved by $T_{\mathcal{B}}$? |
|---|---|
| Sums, scalar multiples, spans, independence, dimension | Yes |
| Products of polynomials, matrix multiplication | No: $[pq]{\mathcal{B}}$ is not the entrywise product of $[p]{\mathcal{B}}$ and $[q]_{\mathcal{B}}$ |
| Lengths and angles | Only for orthonormal bases (Chapter 9) |
| Degree of a polynomial, rank of a matrix | Not visible as a simple feature of the coordinate vector in general |
import numpy as np
from numpy.polynomial import Polynomial as P
# Coordinate map for P_2 relative to B = (1, 1 + x, 1 + x + x^2):
# the columns of PB are the standard (monomial) coefficients of the basis polynomials
PB = np.array([[1., 1., 1.],
[0., 1., 1.],
[0., 0., 1.]])
coords = lambda p: np.linalg.solve(PB, np.pad(p.coef, (0, 3 - len(p.coef))))
p, q = P([5, -1, 2]), P([0, 3, 1])
print(np.allclose(coords(p + q), coords(p) + coords(q))) # True: T_B preserves sums
print(np.allclose(coords(4 * p), 4 * coords(p))) # True: and scalar multiples
# Independence in P_2 is decided in R^3: 1 + 2x, 3 - x + x^2, 5 + 3x + x^2
polys = [P([1, 2]), P([3, -1, 1]), P([5, 3, 1])]
C = np.column_stack([coords(r) for r in polys])
print(np.linalg.matrix_rank(C)) # 2: dependent in P_2 as well
# Products are not preserved: the coordinates of p*q are not coords(p) * coords(q)
print(coords(p) * coords(q)) # [-18. -6. 2.]: entrywise product of (6, -3, 2) and (-3, 2, 1)
print((p * q).coef) # [ 0. 15. 2. 5. 2.]: p*q has degree 4, not even in P_2
Key takeaways
- The coordinate map $\mathbf{v} \mapsto [\mathbf{v}]_{\mathcal{B}}$ is a linear bijection $V \to F^n$, an isomorphism.
- Independence, span, and dimension questions in $V$ can be answered by row reducing coordinate vectors in $F^n$.
- All $n$-dimensional spaces over the same field are isomorphic; dimension is the only invariant.
- Isomorphisms preserve linear structure only, not products, lengths, or angles (unless the basis is orthonormal).
🧪 Practice
- Use coordinate vectors to decide whether $1 + 2x$, $3 - x + x^2$, and $5 + 3x + x^2$ are independent in $\mathbb{P}_2$. If they are dependent, find the relation.
- Prove that $[c\mathbf{u}]{\mathcal{B}} = c,[\mathbf{u}]{\mathcal{B}}$, and that the coordinate map is one-to-one.
- Write down an explicit isomorphism between $\mathbb{P}_5$ and $\mathbb{R}^{2 \times 3}$. Is there an isomorphism between $\mathbb{P}_5$ and $\mathbb{R}^{2 \times 2}$?
- Interview: If every $n$-dimensional real vector space is "just $\mathbb{R}^n$", why do mathematicians and engineers bother with abstract vector spaces at all? Hint: the isomorphism depends on a choice of basis; good basis choices are the whole point of many algorithms, and infinite-dimensional spaces have no such isomorphism.
Change of Basis Matrix
Why it matters. The same vector has different coordinates in different bases, and many problems are only easy in a particular basis. Examples are an eigenbasis that makes a matrix diagonal (Chapter 8), an orthonormal basis that makes projections trivial (Chapter 9), and a frequency basis that separates signal from noise. Moving between bases requires a matrix that converts coordinates in one basis to coordinates in another. Getting its direction right is a famous source of bugs.
Definition. Let $\mathcal{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ and $\mathcal{C}$ be ordered bases of $V$. The change-of-coordinates matrix from $\mathcal{B}$ to $\mathcal{C}$ is the $n \times n$ matrix whose columns are the $\mathcal{C}$-coordinates of the $\mathcal{B}$-vectors:
$$P_{\mathcal{C} \leftarrow \mathcal{B}} = \big[,[\mathbf{b}1]{\mathcal{C}} \ \ [\mathbf{b}2]{\mathcal{C}} \ \cdots \ [\mathbf{b}n]{\mathcal{C}},\big].$$
Theorem. For every $\mathbf{v} \in V$,
$$[\mathbf{v}]{\mathcal{C}} = P{\mathcal{C} \leftarrow \mathcal{B}},[\mathbf{v}]_{\mathcal{B}}.$$
Proof. If $[\mathbf{v}]_{\mathcal{B}} = (c_1, \dots, c_n)$, then $\mathbf{v} = \sum c_i\mathbf{b}i$. The coordinate map is linear, so $[\mathbf{v}]{\mathcal{C}} = \sum c_i[\mathbf{b}i]{\mathcal{C}}$, which is the matrix-vector product above (column view, Section 3.2). $\blacksquare$
Properties.
| Property | Formula | Reason |
|---|---|---|
| Invertible | $P_{\mathcal{B} \leftarrow \mathcal{C}} = (P_{\mathcal{C} \leftarrow \mathcal{B}})^{-1}$ | Converting there and back is the identity |
| Composition | $P_{\mathcal{D} \leftarrow \mathcal{B}} = P_{\mathcal{D} \leftarrow \mathcal{C}},P_{\mathcal{C} \leftarrow \mathcal{B}}$ | Convert $\mathcal{B} \to \mathcal{C} \to \mathcal{D}$ |
| From $\mathcal{B}$ to standard ($\mathbb{R}^n$) | $P_{\mathcal{E} \leftarrow \mathcal{B}} = P_{\mathcal{B}} = [,\mathbf{b}_1 \ \cdots \ \mathbf{b}_n,]$ | $[\mathbf{b}i]{\mathcal{E}} = \mathbf{b}_i$ |
| From standard to $\mathcal{B}$ ($\mathbb{R}^n$) | $P_{\mathcal{B} \leftarrow \mathcal{E}} = P_{\mathcal{B}}^{-1}$ | Inverse of the previous row |
| Same basis | $P_{\mathcal{B} \leftarrow \mathcal{B}} = I$ |
Mnemonic. Read the subscripts right to left, like the matrix product. In $P_{\mathcal{D} \leftarrow \mathcal{C}},P_{\mathcal{C} \leftarrow \mathcal{B}}$, the inner labels $\mathcal{C}$ meet and cancel. The input basis is on the right, and the output basis is on the left.
The direction pitfall. The matrix whose columns are the new basis vectors, written in old coordinates, converts new coordinates to old, not the other way around. If the new basis $\mathcal{B}$ is a rotation of the standard axes by $+30^\circ$, then $P_{\mathcal{B}}$ is the rotation matrix $R_{30^\circ}$. However, the new coordinates of a fixed vector are $R_{30^\circ}^{-1}\mathbf{v} = R_{-30^\circ}\mathbf{v}$: rotating the axes one way makes the coordinates turn the other way. Physicists call this contravariance: basis vectors transform with $P$, coordinates with $P^{-1}$.
P_B = [ b1 b2 ] (new basis vectors written in old coordinates)
new coordinates [v]_B ---- multiply by P_B ------> [v]_E old coordinates
new coordinates [v]_B <--- multiply by P_B^{-1} --- [v]_E old coordinates
Example. $\mathcal{B} = \big((2, 1), (-1, 1)\big)$ in $\mathbb{R}^2$:
$$P_{\mathcal{E} \leftarrow \mathcal{B}} = \begin{bmatrix} 2 & -1 \ 1 & 1 \end{bmatrix}, \qquad P_{\mathcal{B} \leftarrow \mathcal{E}} = \frac{1}{3}\begin{bmatrix} 1 & 1 \ -1 & 2 \end{bmatrix}.$$
Then $P_{\mathcal{E} \leftarrow \mathcal{B}}(2, 1) = (3, 3)$ and $P_{\mathcal{B} \leftarrow \mathcal{E}}(3, 3) = (2, 1)$, which matches the earlier example.
import numpy as np
PB = np.array([[2., -1.],
[1., 1.]]) # P_{E<-B}: columns are b1, b2
P_B_from_E = np.linalg.inv(PB) # P_{B<-E}
print(np.round(3 * P_B_from_E, 10).tolist()) # [[1.0, 1.0], [-1.0, 2.0]]: P_{B<-E} is 1/3 of this
c = np.array([2., 1.]) # [v]_B
v = PB @ c # new -> old
print(v, P_B_from_E @ v) # [3. 3.] [2. 1.]
# Rotating the axes by +30 degrees turns the coordinates by -30 degrees
t = np.radians(30)
R = np.array([[np.cos(t), -np.sin(t)],
[np.sin(t), np.cos(t)]]) # columns: the rotated axes, i.e. P_{E<-B}
e1 = np.array([1., 0.])
coords_new = np.linalg.solve(R, e1) # [e1]_B
print(np.round(coords_new, 4)) # [ 0.866 -0.5 ]: e1 sits at -30 degrees in the new frame
print(np.allclose(coords_new, R.T @ e1)) # True: for rotations, P^{-1} = P^T (Chapter 9)
Key takeaways
- $P_{\mathcal{C} \leftarrow \mathcal{B}}$ has columns $[\mathbf{b}i]{\mathcal{C}}$ and satisfies $[\mathbf{v}]{\mathcal{C}} = P{\mathcal{C} \leftarrow \mathcal{B}}[\mathbf{v}]_{\mathcal{B}}$.
- It is invertible, $P_{\mathcal{B} \leftarrow \mathcal{C}} = P_{\mathcal{C} \leftarrow \mathcal{B}}^{-1}$, and the matrices compose like $P_{\mathcal{D} \leftarrow \mathcal{C}}P_{\mathcal{C} \leftarrow \mathcal{B}} = P_{\mathcal{D} \leftarrow \mathcal{B}}$.
- In $\mathbb{R}^n$, $P_{\mathcal{B}} = [,\mathbf{b}_1 \cdots \mathbf{b}n,]$ converts $\mathcal{B}$-coordinates to standard coordinates, and $P{\mathcal{B}}^{-1}$ converts back.
- Basis vectors and coordinates transform in opposite directions.
🧪 Practice
- For $\mathcal{B} = \big((1, 2), (3, 5)\big)$, compute $P_{\mathcal{E} \leftarrow \mathcal{B}}$, $P_{\mathcal{B} \leftarrow \mathcal{E}}$, and $[(1, 1)]_{\mathcal{B}}$.
- In $\mathbb{P}2$, find the change-of-coordinates matrix from $\mathcal{B} = (1,\ 1 + x,\ 1 + x + x^2)$ to the monomial basis, and use its inverse to recompute $[5 - x + 2x^2]{\mathcal{B}}$.
- Prove that $P_{\mathcal{D} \leftarrow \mathcal{B}} = P_{\mathcal{D} \leftarrow \mathcal{C}},P_{\mathcal{C} \leftarrow \mathcal{B}}$.
- Interview: A robot reports a point in its gripper frame. You know the gripper's three axis vectors expressed in world coordinates. Which matrix converts gripper coordinates to world coordinates? What changes if you are instead given the world axes in gripper coordinates? Hint: the columns are the basis vectors written in the target coordinates; for orthonormal frames, the inverse is the transpose.
Transition Between Bases
Why it matters. Often neither basis is the standard one. For example, you may need to convert from an eigenbasis to an orthonormal basis, or from the Lagrange basis to the Chebyshev basis. The change-of-coordinates matrix can still be computed with one row reduction, by going through the standard coordinates. This topic also previews how matrices of linear maps change with the basis, which is the idea of similarity in Chapters 7 and 8.
Through the standard basis. In $\mathbb{R}^n$, compose $\mathcal{B} \to \mathcal{E} \to \mathcal{C}$:
$$P_{\mathcal{C} \leftarrow \mathcal{B}} = P_{\mathcal{C} \leftarrow \mathcal{E}},P_{\mathcal{E} \leftarrow \mathcal{B}} = P_{\mathcal{C}}^{-1}P_{\mathcal{B}}.$$
P_{C<-B} = P_C^{-1} P_B
[v]_B --------------------------------------------> [v]_C
\ ^
\ P_B P_C^{-1} /
\ /
'------------> v = [v]_E -----------------'
standard coordinates
Algorithm (one row reduction). Since $P_{\mathcal{C}}^{-1}P_{\mathcal{B}}$ solves $P_{\mathcal{C}}X = P_{\mathcal{B}}$, row reduce the augmented matrix
$$[,P_{\mathcal{C}} \mid P_{\mathcal{B}},] ;\longrightarrow; [,I \mid P_{\mathcal{C} \leftarrow \mathcal{B}},].$$
This is the same method as computing an inverse by row reduction (Section 4.3), with $P_{\mathcal{B}}$ in place of $I$.
Example. $\mathcal{B} = \big((-9, 1), (-5, -1)\big)$ and $\mathcal{C} = \big((1, -4), (3, -5)\big)$:
$$\left[\begin{array}{cc|cc} 1 & 3 & -9 & -5 \ -4 & -5 & 1 & -1 \end{array}\right] ;\longrightarrow; \left[\begin{array}{cc|cc} 1 & 0 & 6 & 4 \ 0 & 1 & -5 & -3 \end{array}\right], \qquad P_{\mathcal{C} \leftarrow \mathcal{B}} = \begin{bmatrix} 6 & 4 \ -5 & -3 \end{bmatrix}.$$
Check the first column: $6(1, -4) - 5(3, -5) = (-9, 1) = \mathbf{b}_1$.
Polynomial bases: interpolation is a change of basis. In $\mathbb{P}_n$, let $\mathcal{M}$ be the monomial basis and $\mathcal{L}$ the Lagrange basis at nodes $x_0, \dots, x_n$ (Section 6.4). The $\mathcal{L}$-coordinates of $p$ are its values at the nodes, so
$$[p]{\mathcal{L}} = \begin{bmatrix} p(x_0) \ \vdots \ p(x_n) \end{bmatrix} = V,[p]{\mathcal{M}}, \qquad V = \begin{bmatrix} 1 & x_0 & \cdots & x_0^n \ \vdots & & & \vdots \ 1 & x_n & \cdots & x_n^n \end{bmatrix}.$$
So $P_{\mathcal{L} \leftarrow \mathcal{M}}$ is the Vandermonde matrix. Evaluation converts monomial coefficients to Lagrange coordinates. Interpolation, which solves $V\mathbf{a} = \mathbf{y}$ (Section 3.5), is the inverse change of basis. The ill-conditioning of $V$ for many equally spaced nodes is a property of this particular pair of bases.
Preview: matrices of maps change by similarity. If a linear map has matrix $A$ in standard coordinates, then in $\mathcal{B}$-coordinates it has matrix $P_{\mathcal{B}}^{-1}AP_{\mathcal{B}}$: convert to standard coordinates, apply $A$, convert back. Matrices related this way are similar (Section 7.2). Choosing $\mathcal{B}$ to make $P_{\mathcal{B}}^{-1}AP_{\mathcal{B}}$ diagonal is the goal of Chapter 8.
import numpy as np
import sympy as sp
PB = sp.Matrix([[-9, -5], [1, -1]]) # columns b1, b2
PC = sp.Matrix([[1, 3], [-4, -5]]) # columns c1, c2
# Row reduce [P_C | P_B] -> [I | P_{C<-B}]
R = PC.row_join(PB).rref()[0]
P_CB = R[:, 2:]
print(P_CB) # Matrix([[6, 4], [-5, -3]])
print(P_CB == PC.inv() * PB) # True: the same as P_C^{-1} P_B
# Check: [v]_C = P_{C<-B} [v]_B for v = 2 b1 - b2
vB = sp.Matrix([2, -1])
v = PB * vB
print(PC.solve(v).T, (P_CB * vB).T) # Matrix([[8, -7]]) Matrix([[8, -7]])
# Monomial -> Lagrange coordinates is the Vandermonde matrix
nodes = np.array([0., 1., 2.])
V = np.vander(nodes, 3, increasing=True) # rows (1, x_i, x_i^2)
a = np.array([1., -2., 3.]) # p = 1 - 2x + 3x^2 in the monomial basis
y = V @ a # change of basis = evaluation at the nodes
print(y) # [1. 2. 9.]
print(np.linalg.solve(V, y)) # [ 1. -2. 3.]: interpolation is the inverse change
# Equally spaced nodes make this change of basis badly conditioned as the degree grows
for n in [5, 10, 20]:
print(n, f"{np.linalg.cond(np.vander(np.linspace(0, 1, n + 1), increasing=True)):.1e}")
# 5 4.9e+03
# 10 1.2e+08
# 20 9.1e+16: about as bad as double precision can represent
Key takeaways
- $P_{\mathcal{C} \leftarrow \mathcal{B}} = P_{\mathcal{C}}^{-1}P_{\mathcal{B}}$: go from $\mathcal{B}$ to standard coordinates, then from standard to $\mathcal{C}$.
- Compute it with one row reduction: $[,P_{\mathcal{C}} \mid P_{\mathcal{B}},] \to [,I \mid P_{\mathcal{C} \leftarrow \mathcal{B}},]$.
- Evaluating a polynomial at nodes is a change from monomial to Lagrange coordinates; interpolation is the inverse change.
- The matrix of a linear map changes by similarity, $P^{-1}AP$, when the basis changes.
🧪 Practice
- Compute $P_{\mathcal{C} \leftarrow \mathcal{B}}$ and $P_{\mathcal{B} \leftarrow \mathcal{C}}$ for $\mathcal{B} = \big((1, 1), (1, 2)\big)$ and $\mathcal{C} = \big((2, 1), (1, 1)\big)$, and verify that their product is $I$.
- In $\mathbb{P}_2$, find the change-of-coordinates matrix from the monomial basis $(1, x, x^2)$ to the Taylor basis $\big(1, (x - 1), (x - 1)^2\big)$. Use it to expand $3 + 2x + x^2$ in powers of $(x - 1)$, and compare with Taylor's formula.
- For $A = \begin{bmatrix} 3 & 1 \ 0 & 2 \end{bmatrix}$ and $\mathcal{B} = \big((1, 0), (1, -1)\big)$, compute $P_{\mathcal{B}}^{-1}AP_{\mathcal{B}}$. What is special about the result, and about the vectors in $\mathcal{B}$?
- Interview: Interpolating data with a degree-20 polynomial through equally spaced points gives wildly wrong coefficients in double precision. In change-of-basis terms, what is going wrong, and what would you change? Hint: the condition number of the monomial-to-Lagrange matrix; use a better-conditioned basis (Chebyshev) or better nodes.
<a id="66-fundamental-subspaces-of-a-matrix"></a>
6.6 Fundamental Subspaces of a Matrix
Every $m \times n$ matrix $A$ carries four subspaces: two in $\mathbb{R}^n$ (the row space and the null space) and two in $\mathbb{R}^m$ (the column space and the left null space). Their dimensions are fixed by a single number, the rank, and they meet at right angles. Together they describe completely what $A\mathbf{x} = \mathbf{b}$ can and cannot do.
Throughout this subchapter, the running example is
$$A = \begin{bmatrix} 1 & 2 & 0 & 1 \ 2 & 4 & 1 & 4 \ 3 & 6 & 1 & 5 \end{bmatrix} ;\longrightarrow; R = \begin{bmatrix} 1 & 2 & 0 & 1 \ 0 & 0 & 1 & 2 \ 0 & 0 & 0 & 0 \end{bmatrix} \quad (\text{RREF}),$$
a $3 \times 4$ matrix ($m = 3$, $n = 4$) with pivots in columns 1 and 3, so $\operatorname{rank} A = 2$. Note that row 3 of $A$ is the sum of rows 1 and 2.
Column Space
Why it matters. The column space answers the existence question: for which right-hand sides $\mathbf{b}$ does $A\mathbf{x} = \mathbf{b}$ have a solution? It is also the set of all possible outputs of the map $\mathbf{x} \mapsto A\mathbf{x}$. In data fitting, the predictions $X\boldsymbol{\beta}$ of a linear model can only lie in $\operatorname{Col} X$, and when the observed data do not, the result is least squares (Section 9.5).
Definition. The column space of an $m \times n$ matrix $A = [,\mathbf{a}_1 \ \cdots \ \mathbf{a}_n,]$ is
$$\operatorname{Col} A = \operatorname{Span}{\mathbf{a}_1, \dots, \mathbf{a}_n} = {A\mathbf{x} : \mathbf{x} \in \mathbb{R}^n} \subseteq \mathbb{R}^m.$$
The two descriptions agree because $A\mathbf{x} = x_1\mathbf{a}_1 + \cdots + x_n\mathbf{a}_n$ (Section 3.2). Therefore
$$A\mathbf{x} = \mathbf{b} \text{ is consistent} \iff \mathbf{b} \in \operatorname{Col} A.$$
$\operatorname{Col} A$ is a subspace, since it is a span. It is also called the range or image of $A$.
Basis and dimension. The pivot columns of $A$ form a basis of $\operatorname{Col} A$ (Section 6.4, method 1). Hence
$$\dim\operatorname{Col} A = \text{number of pivots} = \operatorname{rank} A.$$
Remember to take the columns from $A$, not from $R$.
For the running example, the pivot columns are 1 and 3, so
$$\operatorname{Col} A = \operatorname{Span}\left{\begin{bmatrix} 1 \ 2 \ 3 \end{bmatrix}, \begin{bmatrix} 0 \ 1 \ 1 \end{bmatrix}\right},$$
a plane through the origin in $\mathbb{R}^3$. Column 2 is twice column 1, and column 4 is column 1 plus twice column 3, as column 4 of $R$ shows.
An equation for $\operatorname{Col} A$. Since $\operatorname{Col} A$ is a plane in $\mathbb{R}^3$, it is described by one equation. Row 3 of $A$ equals row 1 plus row 2, so every output $\mathbf{b} = A\mathbf{x}$ satisfies $b_3 = b_1 + b_2$:
$$\operatorname{Col} A = {\mathbf{b} \in \mathbb{R}^3 : b_1 + b_2 - b_3 = 0}.$$
The left null space topic below explains where this equation comes from in general.
When is $\operatorname{Col} A$ everything? $\operatorname{Col} A = \mathbb{R}^m$ exactly when $\operatorname{rank} A = m$, a pivot in every row. Then $A\mathbf{x} = \mathbf{b}$ is solvable for every $\mathbf{b}$.
R^4 (inputs x) R^3 (outputs Ax)
b3
| Col A: the plane b1 + b2 - b3 = 0
any x -------------- A --------------> | /--------------/
| / * Ax /
| / /
|/--------------/----- b2
/
b1
every output lands in the plane; b = (1, 1, 1) is off the plane, so Ax = (1, 1, 1) has no solution
import sympy as sp
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 1, 4],
[3, 6, 1, 5]])
R, pivots = A.rref()
print(pivots) # (0, 2): columns 1 and 3 are the pivot columns
basis = [A[:, j] for j in pivots] # take them from A, not from R
print([list(b) for b in basis]) # [[1, 2, 3], [0, 1, 1]]
print(A.columnspace() == basis) # True: sympy's columnspace() uses the same rule
# Membership: b is in Col A iff appending it does not raise the rank
for b in [(1, 0, 1), (1, 1, 1)]:
print(b, A.rank() == A.row_join(sp.Matrix(b)).rank())
# (1, 0, 1) True
# (1, 1, 1) False
Key takeaways
- $\operatorname{Col} A$ is the span of the columns, equivalently the set of all outputs $A\mathbf{x}$; it lives in $\mathbb{R}^m$.
- $A\mathbf{x} = \mathbf{b}$ is solvable exactly when $\mathbf{b} \in \operatorname{Col} A$.
- The pivot columns of the original $A$ are a basis; $\dim\operatorname{Col} A = \operatorname{rank} A$.
- $\operatorname{Col} A = \mathbb{R}^m$ exactly when $\operatorname{rank} A = m$.
🧪 Practice
- Find a basis of $\operatorname{Col} B$ for $B = \begin{bmatrix} 1 & -1 & 2 & 0 \ 2 & -2 & 5 & 1 \ -1 & 1 & -1 & 1 \end{bmatrix}$, and determine whether $\operatorname{Col} B = \mathbb{R}^3$.
- For the running example, is $\mathbf{b} = (2, -1, 1)$ in $\operatorname{Col} A$? If so, find one solution of $A\mathbf{x} = \mathbf{b}$.
- Prove that $\operatorname{Col}(AB) \subseteq \operatorname{Col} A$ whenever $AB$ is defined. Give an example where the inclusion is strict.
- Interview: In linear regression $\mathbf{y} \approx X\boldsymbol{\beta}$, why is the fitted vector $\hat{\mathbf{y}} = X\hat{\boldsymbol{\beta}}$ always in $\operatorname{Col} X$? What does it mean, geometrically and practically, when $\mathbf{y}$ itself is not in $\operatorname{Col} X$? Hint: the residual $\mathbf{y} - \hat{\mathbf{y}}$ and the closest point of a subspace (Section 9.5).
Row Space
Why it matters. Each row of $A$ is one equation of the system $A\mathbf{x} = \mathbf{b}$, and its row space contains every equation that can be derived from them by combination. Redundant equations, such as row 3 of the running example, add nothing to the row space. The row space also identifies which part of an input $\mathbf{x}$ the matrix actually "sees" (last topic of this subchapter). Its dimension equals that of the column space, a surprising fact with many uses.
Definition. The row space of $A$ is the span of its rows, regarded as vectors in $\mathbb{R}^n$:
$$\operatorname{Row} A = \operatorname{Span}{\text{rows of } A} = \operatorname{Col} A^T \subseteq \mathbb{R}^n.$$
Row operations preserve the row space. Each elementary row operation replaces the rows by combinations of the old rows, so the new row space is contained in the old one. Each operation is reversible, so the old row space is contained in the new one. Hence row-equivalent matrices have the same row space. This is the opposite of the situation for columns.
| Row space | Column space | |
|---|---|---|
| Lives in | $\mathbb{R}^n$ | $\mathbb{R}^m$ |
| Changed by row operations? | No | Yes (but relations among columns are kept) |
| Basis | nonzero rows of any echelon form | pivot columns of the original $A$ |
| Dimension | $\operatorname{rank} A$ | $\operatorname{rank} A$ |
Basis and dimension. The nonzero rows of an echelon form are independent: each has a leading entry in a column where all rows below it have zeros. They span $\operatorname{Row} A$ by the previous paragraph. For the running example,
$$\operatorname{Row} A = \operatorname{Span}{(1, 2, 0, 1),\ (0, 0, 1, 2)} \subseteq \mathbb{R}^4,$$
and $\dim\operatorname{Row} A = 2$.
Row rank equals column rank. Both dimensions equal the number of pivots, so
$$\dim\operatorname{Row} A = \dim\operatorname{Col} A = \operatorname{rank} A, \qquad\text{equivalently}\qquad \operatorname{rank} A^T = \operatorname{rank} A.$$
This is not obvious. The rows are $m$ vectors in $\mathbb{R}^n$ and the columns are $n$ vectors in $\mathbb{R}^m$, and they generally span subspaces of different spaces. Yet "the number of independent equations" always equals "the number of independent columns". For example, a $3 \times 100$ matrix has at most 3 independent columns, because it has only 3 rows.
Caution. The row space basis should come from the echelon form, not from "the rows of $A$ in pivot positions". Row exchanges during elimination can move rows. If you need a basis made of original rows, apply the pivot-column method to $A^T$.
import numpy as np
import sympy as sp
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 1, 4],
[3, 6, 1, 5]])
R = A.rref()[0]
basis = [list(R.row(i)) for i in range(R.rows) if any(R.row(i))]
print(basis) # [[1, 2, 0, 1], [0, 0, 1, 2]]
# Is (1, 2, 1, 3) in Row A? Compare ranks after appending it as a new row
w = sp.Matrix([[1, 2, 1, 3]])
print(A.rank() == A.col_join(w).rank()) # True: it is row 1 + row 2 of R
# Row rank = column rank, even for very non-square matrices
rng = np.random.default_rng(0)
for m, n, r in [(3, 100, 3), (50, 8, 5), (20, 20, 7)]:
M = rng.normal(size=(m, r)) @ rng.normal(size=(r, n)) # an m x n matrix of rank r
print((m, n), np.linalg.matrix_rank(M), np.linalg.matrix_rank(M.T))
# (3, 100) 3 3
# (50, 8) 5 5
# (20, 20) 7 7
Key takeaways
- $\operatorname{Row} A = \operatorname{Col} A^T$ is the span of the rows; it lives in $\mathbb{R}^n$.
- Row operations do not change the row space, so the nonzero rows of any echelon form are a basis.
- $\dim\operatorname{Row} A = \dim\operatorname{Col} A = \operatorname{rank} A$: row rank equals column rank.
- A redundant equation is a row that lies in the span of the other rows.
🧪 Practice
- Find a basis of $\operatorname{Row} B$ for the matrix $B$ of the previous topic's first exercise, and check that its dimension matches $\dim\operatorname{Col} B$.
- Is $(1, 2, 1, 2)$ in $\operatorname{Row} A$ for the running example? Is $(2, 4, 1, 4)$?
- Prove that if $E$ is invertible, then $\operatorname{Row}(EA) = \operatorname{Row} A$. Why does this not imply $\operatorname{Col}(EA) = \operatorname{Col} A$?
- Interview: Without computing anything, explain why a $5 \times 3$ matrix cannot have 4 linearly independent rows, and why a $3 \times 5$ matrix always has a nontrivial null space. Hint: row rank equals column rank, and the rank is at most $\min(m, n)$.
Null Space
Why it matters. The null space answers the uniqueness question. It consists of the inputs that $A$ sends to zero, and every solution of $A\mathbf{x} = \mathbf{b}$ can be shifted by any null space vector without changing $A\mathbf{x}$. If the null space is ${\mathbf{0}}$, solutions are unique. Otherwise its dimension counts the free parameters in every solution set. Null spaces also hold eigenvectors (Chapter 8), dependence relations among columns (Section 6.3), and the rigid-body motions of a mechanical structure.
Definition. The null space of an $m \times n$ matrix $A$ is
$$\operatorname{Nul} A = {\mathbf{x} \in \mathbb{R}^n : A\mathbf{x} = \mathbf{0}}.$$
Section 3.4 showed that it is a subspace of $\mathbb{R}^n$, and that the full solution set of a consistent system is $\mathbf{p} + \operatorname{Nul} A$ for any particular solution $\mathbf{p}$. It is also called the kernel of $A$.
Basis: the special solutions. Solve $A\mathbf{x} = \mathbf{0}$ from the RREF and write the solution in parametric vector form. Each free variable gives one vector, called a special solution: set that free variable to 1, the other free variables to 0, and solve for the basic variables. For the running example, the free variables are $x_2$ and $x_4$:
$$x_1 = -2x_2 - x_4, \quad x_3 = -2x_4 ;\implies; \mathbf{x} = x_2\begin{bmatrix} -2 \ 1 \ 0 \ 0 \end{bmatrix} + x_4\begin{bmatrix} -1 \ 0 \ -2 \ 1 \end{bmatrix}.$$
The special solutions are automatically independent. Each one has a 1 in its own free-variable position, where all the others have 0. Hence
$$\dim\operatorname{Nul} A = \text{number of free variables} = n - \operatorname{rank} A.$$
This number is the nullity of $A$. Here it is $4 - 2 = 2$, so $\operatorname{Nul} A$ is a plane in $\mathbb{R}^4$.
Implicit versus explicit. $\operatorname{Nul} A$ and $\operatorname{Col} A$ are described in opposite ways, so different tasks are easy for each:
| $\operatorname{Nul} A$ | $\operatorname{Col} A$ | |
|---|---|---|
| Lives in | $\mathbb{R}^n$ | $\mathbb{R}^m$ |
| Given by | equations: $A\mathbf{x} = \mathbf{0}$ (implicit) | generators: the columns (explicit) |
| Is $\mathbf{v}$ in it? | Easy: compute $A\mathbf{v}$ | Requires row reducing $[,A \mid \mathbf{v},]$ |
| List some elements | Requires solving $A\mathbf{x} = \mathbf{0}$ | Easy: any $A\mathbf{x}$ |
| Basis | special solutions from the RREF | pivot columns of $A$ |
| Dimension | $n - r$ | $r$ |
| Trivial when | $r = n$ (unique solutions) | never; it is all of $\mathbb{R}^m$ when $r = m$ |
Numerical null spaces. With floating-point data, $A\mathbf{x} = \mathbf{0}$ rarely holds exactly. Libraries compute an orthonormal basis of the numerical null space from the SVD (Chapter 11). These are the right singular vectors whose singular values fall below a tolerance. Such a basis differs from the special solutions but spans the same subspace.
import numpy as np
import sympy as sp
from scipy.linalg import null_space
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 1, 4],
[3, 6, 1, 5]])
special = A.nullspace() # special solutions, one per free variable
print([list(v) for v in special]) # [[-2, 1, 0, 0], [-1, 0, -2, 1]]
print(all(A * v == sp.zeros(3, 1) for v in special)) # True
# Membership is easy: just multiply
print(list(A * sp.Matrix([3, -1, 2, -1]))) # [0, 0, 0]: in Nul A
# Numerical, orthonormal basis of the same subspace (via the SVD)
N = null_space(np.array(A, dtype=float))
print(N.shape) # (4, 2): nullity 2
S = np.array([[-2, 1, 0, 0], [-1, 0, -2, 1]], dtype=float).T
print(np.linalg.matrix_rank(np.hstack([N, S]))) # 2: same span as the special solutions
Key takeaways
- $\operatorname{Nul} A$ is the set of solutions of $A\mathbf{x} = \mathbf{0}$, a subspace of $\mathbb{R}^n$.
- The special solutions (one per free variable) form a basis; nullity $= n - \operatorname{rank} A$.
- $\operatorname{Nul} A = {\mathbf{0}}$ exactly when solutions of $A\mathbf{x} = \mathbf{b}$ are unique (when they exist).
- Null space membership is easy to test, but finding elements requires solving; the column space is the reverse.
🧪 Practice
- Find a basis of $\operatorname{Nul}\begin{bmatrix} 1 & -1 & 2 \ 2 & -2 & 4 \end{bmatrix}$ and describe it geometrically.
- Explain why the special solutions are always linearly independent, using the positions of the free variables.
- Find a $2 \times 3$ matrix whose null space is $\operatorname{Span}{(1, 1, 1)}$. Then find a $1 \times 3$ matrix whose null space contains $(1, 1, 1)$. What is the null space of your $1 \times 3$ matrix?
- Interview: In a finite element simulation, the stiffness matrix $K$ of a structure floating freely in space has a nontrivial null space. What do the null space vectors represent physically, and why does a direct solver fail on $K\mathbf{u} = \mathbf{f}$? How is this usually fixed? Hint: rigid-body translations and rotations produce no deformation; boundary conditions remove them.
Left Null Space
Why it matters. The left null space records the dependencies among the rows, that is, the combinations of equations that cancel to $0 = 0$. Applied to the right-hand side, the same combination must give $0$ as well, otherwise the system is inconsistent. So the left null space supplies exactly the compatibility conditions on $\mathbf{b}$, the equations of $\operatorname{Col} A$. The same idea appears as parity checks in error-correcting codes and as loop laws in electrical networks.
Definition. The left null space of an $m \times n$ matrix $A$ is
$$\operatorname{Nul} A^T = {\mathbf{y} \in \mathbb{R}^m : A^T\mathbf{y} = \mathbf{0}} = {\mathbf{y} \in \mathbb{R}^m : \mathbf{y}^TA = \mathbf{0}^T}.$$
It is called "left" because $\mathbf{y}^T$ multiplies $A$ from the left. The condition $\mathbf{y}^TA = \mathbf{0}^T$ says $y_1(\text{row } 1) + \cdots + y_m(\text{row } m) = \mathbf{0}$, a dependence relation among the rows. Applying the null space results to the $n \times m$ matrix $A^T$, which also has rank $r$:
$$\dim\operatorname{Nul} A^T = m - \operatorname{rank} A.$$
For the running example, row 1 + row 2 - row 3 $= \mathbf{0}$, so $\operatorname{Nul} A^T = \operatorname{Span}{(1, 1, -1)}$, with dimension $3 - 2 = 1$.
Compatibility conditions. If $A\mathbf{x} = \mathbf{b}$ and $\mathbf{y} \in \operatorname{Nul} A^T$, then
$$\mathbf{y}^T\mathbf{b} = \mathbf{y}^TA\mathbf{x} = \mathbf{0}^T\mathbf{x} = 0.$$
So every $\mathbf{y}$ in the left null space gives a necessary condition $\mathbf{y} \cdot \mathbf{b} = 0$ for solvability. The last topic of this subchapter shows these conditions are also sufficient:
$$A\mathbf{x} = \mathbf{b} \text{ is consistent} \iff \mathbf{y} \cdot \mathbf{b} = 0 \text{ for every } \mathbf{y} \in \operatorname{Nul} A^T.$$
For the running example this is the equation $b_1 + b_2 - b_3 = 0$ found in the column space topic.
Computing it from elimination. Row reduce $[,A \mid I_m,]$ to $[,R \mid E,]$. The matrix $E$ records the row operations, so $EA = R$ (Section 4.4). The rows of $E$ that sit next to the zero rows of $R$ satisfy $\mathbf{y}^TA = \mathbf{0}^T$, and they form a basis of $\operatorname{Nul} A^T$. Elimination therefore finds the left null space as a by-product.
$$[,A \mid I,] = \left[\begin{array}{cccc|ccc} 1 & 2 & 0 & 1 & 1 & 0 & 0 \ 2 & 4 & 1 & 4 & 0 & 1 & 0 \ 3 & 6 & 1 & 5 & 0 & 0 & 1 \end{array}\right] ;\longrightarrow; \left[\begin{array}{cccc|ccc} 1 & 2 & 0 & 1 & 0 & -1 & 1 \ 0 & 0 & 1 & 2 & 0 & 3 & -2 \ 0 & 0 & 0 & 0 & 1 & 1 & -1 \end{array}\right].$$
The zero row of $R$ is next to $(1, 1, -1)$.
Application: loops in a network. The incidence matrix $A$ of a directed graph has one row per edge and one column per node, with $-1$ at the edge's start and $+1$ at its end. A vector $\mathbf{y}$ assigns a current to each edge. The condition $A^T\mathbf{y} = \mathbf{0}$ says that the net current into every node is zero, which is Kirchhoff's current law. So the left null space consists of the current patterns that flow around loops. For a connected graph with $n$ nodes and $m$ edges, $\operatorname{rank} A = n - 1$, so the number of independent loops is $m - n + 1$.
nodes 1..4, edges e1..e5 independent loops: m - n + 1 = 5 - 4 + 1 = 2
e1 loop 1: e1, e3, then e2 backwards
1 ------> 2 y = ( 1, -1, 1, 0, 0)
| / |
e2 | e3 / | e4 loop 2: e3, e5, then e4 backwards
v v v y = ( 0, 0, 1, -1, 1)
3 ------> 4
e5 A^T y = 0: current in = current out at every node
import sympy as sp
A = sp.Matrix([[1, 2, 0, 1],
[2, 4, 1, 4],
[3, 6, 1, 5]])
print([list(y) for y in A.T.nullspace()]) # [[-1, -1, 1]]: spans the same line as (1, 1, -1)
# From elimination: [A | I] -> [R | E]; rows of E beside zero rows of R span Nul A^T
RE = A.row_join(sp.eye(3)).rref()[0]
R, E = RE[:, :4], RE[:, 4:]
print([list(E.row(i)) for i in range(3) if not any(R.row(i))]) # [[1, 1, -1]]
print(list(E.row(2) * A)) # [0, 0, 0, 0]
# Compatibility condition: y . b = 0
y = sp.Matrix([1, 1, -1])
for b in [(1, 0, 1), (1, 1, 1)]:
print(b, (y.T * sp.Matrix(b))[0])
# (1, 0, 1) 0: solvable
# (1, 1, 1) 1: not solvable
# Graph incidence matrix: rows = edges, columns = nodes
edges = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
G = sp.zeros(len(edges), 4)
for k, (i, j) in enumerate(edges):
G[k, i - 1], G[k, j - 1] = -1, 1
print(G.rank(), len(G.T.nullspace())) # 3 2: rank n - 1, and m - n + 1 = 2 loops
Key takeaways
- $\operatorname{Nul} A^T = {\mathbf{y} : \mathbf{y}^TA = \mathbf{0}^T}$ consists of the dependence relations among the rows; it lives in $\mathbb{R}^m$ and has dimension $m - r$.
- Each $\mathbf{y} \in \operatorname{Nul} A^T$ gives a solvability condition $\mathbf{y} \cdot \mathbf{b} = 0$, and these conditions are exactly the equations of $\operatorname{Col} A$.
- Row reducing $[,A \mid I,]$ to $[,R \mid E,]$ gives a basis: the rows of $E$ next to the zero rows of $R$.
- For a graph's incidence matrix, the left null space is the space of loop currents (Kirchhoff's current law).
🧪 Practice
- Find a basis of the left null space of $\begin{bmatrix} 1 & 2 \ 2 & 4 \ 3 & 6 \end{bmatrix}$, and use it to write the conditions on $\mathbf{b}$ for $A\mathbf{x} = \mathbf{b}$ to be solvable.
- Row reduce $[,A \mid I,]$ for $A = \begin{bmatrix} 1 & 1 \ 1 & 2 \ 2 & 3 \end{bmatrix}$, and read off $\operatorname{Nul} A^T$ from $E$.
- For the graph in the diagram, add an edge from node 4 to node 1. How many independent loops are there now? Give a basis of loop vectors.
- Interview: You have 1,000 redundant sensor equations $A\mathbf{x} = \mathbf{b}$ for 50 unknowns, and you suspect that one sensor is faulty. How can vectors in $\operatorname{Nul} A^T$ detect, and possibly locate, the fault without solving for $\mathbf{x}$? Hint: for correct data, $\mathbf{y}^T\mathbf{b} = 0$ for every left null vector; the pattern of which checks fail points to the faulty sensor, as with the syndrome of an error-correcting code.
Rank and Nullity
Why it matters. The four subspaces have four dimensions, but they are all determined by the shape $m \times n$ and one number, the rank $r$. The rank is the most informative single number attached to a matrix. It tells you whether solutions exist and are unique, how much a matrix compresses its input, and how many numbers are needed to store it. Low-rank structure underlies data compression, recommender systems, and parameter-efficient fine-tuning of neural networks.
Definitions. The rank of $A$ is $\operatorname{rank} A = \dim\operatorname{Col} A = \dim\operatorname{Row} A$. The nullity of $A$ is $\dim\operatorname{Nul} A$. Section 3.4 defined the rank as the number of pivots; Section 6.6 has shown that these agree.
| Subspace | Lives in | Dimension | Basis from elimination |
|---|---|---|---|
| $\operatorname{Col} A$ | $\mathbb{R}^m$ | $r$ | pivot columns of $A$ |
| $\operatorname{Row} A$ | $\mathbb{R}^n$ | $r$ | nonzero rows of $R$ |
| $\operatorname{Nul} A$ | $\mathbb{R}^n$ | $n - r$ | special solutions |
| $\operatorname{Nul} A^T$ | $\mathbb{R}^m$ | $m - r$ | rows of $E$ beside zero rows of $R$ |
For the running example ($m = 3$, $n = 4$, $r = 2$): $2, 2, 2, 1$.
The four cases. Since $r \le \min(m, n)$, every matrix falls into one of four cases:
| Case | Shape | $\operatorname{Nul} A$ | $\operatorname{Col} A$ | Solutions of $A\mathbf{x} = \mathbf{b}$ |
|---|---|---|---|---|
| $r = m = n$ | square, invertible | ${\mathbf{0}}$ | $\mathbb{R}^m$ | exactly one for every $\mathbf{b}$ |
| $r = n < m$ | tall, full column rank | ${\mathbf{0}}$ | proper subspace | 0 or 1 |
| $r = m < n$ | wide, full row rank | nontrivial | $\mathbb{R}^m$ | infinitely many for every $\mathbf{b}$ |
| $r < m$, $r < n$ | rank-deficient | nontrivial | proper subspace | 0 or infinitely many |
Full column rank makes $A^TA$ invertible, which is the key to least squares (Section 9.5). Full row rank makes $AA^T$ invertible.
Rank inequalities and identities.
| Fact | Reason |
|---|---|
| $\operatorname{rank} A \le \min(m, n)$ | at most one pivot per row and per column |
| $\operatorname{rank} A^T = \operatorname{rank} A$ | row rank = column rank |
| $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$ | $\operatorname{Col}(AB) \subseteq \operatorname{Col} A$ and $\operatorname{Row}(AB) \subseteq \operatorname{Row} B$ |
| $\operatorname{rank}(EA) = \operatorname{rank}(AF) = \operatorname{rank} A$ for invertible $E, F$ | multiply by the inverse to recover $A$, then apply the previous row |
| $\operatorname{rank}(A + B) \le \operatorname{rank} A + \operatorname{rank} B$ | $\operatorname{Col}(A + B) \subseteq \operatorname{Col} A + \operatorname{Col} B$ |
| $\operatorname{rank}(A^TA) = \operatorname{rank} A$ (real $A$) | $A^TA\mathbf{x} = \mathbf{0} \implies \lVert A\mathbf{x}\rVert^2 = \mathbf{x}^TA^TA\mathbf{x} = 0$, so $\operatorname{Nul}(A^TA) = \operatorname{Nul} A$ |
Rank-one matrices. A matrix has rank 1 exactly when it is an outer product $\mathbf{u}\mathbf{v}^T$ with $\mathbf{u}, \mathbf{v} \ne \mathbf{0}$: every column is a multiple of $\mathbf{u}$. A rank-$r$ matrix is a sum of $r$ rank-one matrices, and it factors as $A = CR$ with $C$ ($m \times r$) and $R$ ($r \times n$). Storing it this way needs $r(m + n)$ numbers instead of $mn$. The SVD (Chapter 11) finds the best such factorization.
import numpy as np
rng = np.random.default_rng(7)
rank = np.linalg.matrix_rank
A = rng.normal(size=(6, 2)) @ rng.normal(size=(2, 5)) # 6 x 5, rank 2: it passes through a 2D bottleneck
B = rng.normal(size=(5, 3)) @ rng.normal(size=(3, 4)) # 5 x 4, rank 3
print(rank(A), rank(A.T), rank(A.T @ A)) # 2 2 2
print(rank(A @ B), min(rank(A), rank(B))) # 2 2
E = rng.normal(size=(6, 6)) # invertible (with probability 1)
print(rank(E @ A)) # 2: invertible factors preserve rank
u, v = rng.normal(size=4), rng.normal(size=3)
print(rank(np.outer(u, v))) # 1: an outer product has rank one
# Storage of a low-rank matrix: m*n numbers versus r*(m + n)
m, n, r = 4096, 4096, 8
print(m * n, r * (m + n)) # 16777216 65536
Key takeaways
- Rank $r$ = dimension of the column space = dimension of the row space; nullity = $n - r$; the left null space has dimension $m - r$.
- Full column rank ($r = n$) means unique solutions; full row rank ($r = m$) means solutions always exist.
- $\operatorname{rank}(AB) \le \min(\operatorname{rank} A, \operatorname{rank} B)$, and invertible factors do not change rank.
- Rank-one matrices are outer products $\mathbf{u}\mathbf{v}^T$; a rank-$r$ matrix needs only $r(m + n)$ numbers.
🧪 Practice
- A $7 \times 5$ matrix has rank 3. Give the dimensions of all four fundamental subspaces, and say which spaces they live in.
- Prove that $\operatorname{rank}(AB) \le \operatorname{rank} A$ using column spaces, and $\operatorname{rank}(AB) \le \operatorname{rank} B$ using row spaces.
- Can a $4 \times 6$ matrix have nullity 1? Can a $6 \times 4$ matrix have nullity 0? Can a $6 \times 4$ matrix have a left null space of dimension 1?
- Interview: LoRA fine-tunes a $4096 \times 4096$ weight matrix $W$ by learning an update $\Delta W = BA$, with $B$ of size $4096 \times 8$ and $A$ of size $8 \times 4096$. What is the maximum rank of the update, how many trainable parameters does it use compared with a full update, and what is the trade-off? Hint: $\operatorname{rank}(BA) \le 8$; compare $2 \cdot 4096 \cdot 8$ with $4096^2$.
Rank-Nullity Theorem
Why it matters. Rank-nullity is the bookkeeping law of linear algebra: dimensions are conserved. Each of the $n$ input dimensions either survives into the output or is killed. This one identity turns many questions about existence and uniqueness into arithmetic. It shows, for example, that a wide matrix must have a nontrivial null space, that for a square matrix injective and surjective are equivalent, and how many parameters describe a solution set.
Theorem (rank-nullity). For any $m \times n$ matrix $A$,
$$\operatorname{rank} A + \dim\operatorname{Nul} A = n.$$
Proof. Each of the $n$ columns of $A$ is either a pivot column or not. The pivot columns number $\operatorname{rank} A$. The non-pivot columns correspond to free variables, which number $\dim\operatorname{Nul} A$, since each contributes one special solution and these form a basis. $\blacksquare$
Section 7.3 states the theorem for any linear map $T : V \to W$ between finite-dimensional spaces: $\dim(\operatorname{image} T) + \dim(\ker T) = \dim V$.
Interpretation: conservation of dimension.
input space R^n output space R^m
+-----------------------+
| n - r dimensions | ---- sent to 0 ----> 0
| (Nul A) |
| - - - - - - - - - - | +----------------------+
| r dimensions | ---- survive -----> | Col A (r dims) |
| | +----------------------+
+-----------------------+
n = (n - r) + r "what is lost" + "what survives" = "what came in"
Consequences.
| Situation | Conclusion from $r + \text{nullity} = n$ |
|---|---|
| $n > m$ (wide matrix) | $r \le m < n$, so nullity $\ge n - m > 0$: nontrivial solutions of $A\mathbf{x} = \mathbf{0}$ exist (Section 3.4) |
| $m = n$ (square) | nullity $= 0 \iff r = n$: one-to-one $\iff$ onto (Invertible Matrix Theorem) |
| $A\mathbf{x} = \mathbf{b}$ consistent | the solution set $\mathbf{p} + \operatorname{Nul} A$ has $n - r$ free parameters |
| $k$ independent homogeneous equations in $n$ unknowns | the solution space has dimension $n - k$ |
| Subspace defined by linear conditions | its dimension is (ambient dimension) $-$ (rank of the conditions) |
Example. ${p \in \mathbb{P}_4 : p(1) = p(2) = 0}$. In monomial coordinates, the two conditions form a $2 \times 5$ matrix of rank 2, with rows $(1, 1, 1, 1, 1)$ and $(1, 2, 4, 8, 16)$. The subspace therefore has dimension $5 - 2 = 3$. It is $(x - 1)(x - 2),\mathbb{P}_2$, whose basis is $(x - 1)(x - 2)$ times $1, x, x^2$.
Example. The trace-zero $n \times n$ matrices are the null space of the $1 \times n^2$ "trace" matrix, which has rank 1. Their dimension is $n^2 - 1$, which matches Section 6.4.
import numpy as np
import sympy as sp
from scipy.linalg import null_space
rng = np.random.default_rng(3)
for m, n, r in [(3, 5, 2), (6, 4, 4), (5, 5, 3), (2, 7, 2)]:
A = rng.normal(size=(m, r)) @ rng.normal(size=(r, n)) # an m x n matrix of rank r
rank = np.linalg.matrix_rank(A)
nullity = null_space(A).shape[1]
print((m, n), rank, nullity, rank + nullity == n)
# (3, 5) 2 3 True
# (6, 4) 4 0 True
# (5, 5) 3 2 True
# (2, 7) 2 5 True
# Dimension of {p in P_4 : p(1) = p(2) = 0} via rank-nullity on the condition matrix
C = sp.Matrix([[1, 1, 1, 1, 1], # p(1) in terms of the coefficients a0..a4
[1, 2, 4, 8, 16]]) # p(2)
print(5 - C.rank(), len(C.nullspace())) # 3 3
Key takeaways
- $\operatorname{rank} A + \dim\operatorname{Nul} A = n$, the number of columns.
- Dimension is conserved: every input direction is either killed (null space) or survives into the column space.
- A wide matrix ($n > m$) always has a nontrivial null space; for square matrices, one-to-one and onto are equivalent.
- The dimension of a subspace cut out by linear conditions is the ambient dimension minus the rank of the conditions.
🧪 Practice
- A $5 \times 8$ matrix $A$ has rank 5. Is $A\mathbf{x} = \mathbf{b}$ solvable for every $\mathbf{b}$? How many free parameters does its solution set have?
- Use rank-nullity to find the dimension of ${A \in \mathbb{R}^{3 \times 3} : \operatorname{tr} A = 0 \text{ and } a_{12} = a_{21}}$.
- Prove that if $A$ is $6 \times 9$, then $\operatorname{Nul} A \ne {\mathbf{0}}$, and find the smallest possible nullity.
- Interview: A $1000 \times 1000$ projection matrix applied to embeddings has a 50-dimensional null space. How many dimensions of information survive the projection, and can the original embeddings be recovered from the projected ones? What extra information would make recovery possible? Hint: rank $= 950$; the map is not one-to-one, so recovery needs the lost components along $\operatorname{Nul} A$ or a prior that pins them down.
Orthogonality Relations Among the Four Subspaces
Why it matters. The four subspaces are not just a list of four dimensions. They fit together geometrically: the row space and null space are perpendicular and together fill $\mathbb{R}^n$, and the column space and left null space are perpendicular and together fill $\mathbb{R}^m$. This picture, sometimes called the fundamental theorem of linear algebra, explains exactly when $A\mathbf{x} = \mathbf{b}$ is solvable. It shows that $A$ is an invertible map from its row space to its column space, and it leads directly to least squares, the pseudoinverse, and the SVD (Chapters 9 and 11).
Orthogonality. Two subspaces are orthogonal if every vector of one is perpendicular to every vector of the other.
Theorem. For any real $m \times n$ matrix $A$:
- $\operatorname{Row} A \perp \operatorname{Nul} A$ in $\mathbb{R}^n$;
- $\operatorname{Col} A \perp \operatorname{Nul} A^T$ in $\mathbb{R}^m$.
Proof. $A\mathbf{x} = \mathbf{0}$ says that $\mathbf{r}_i \cdot \mathbf{x} = 0$ for each row $\mathbf{r}_i$ of $A$. So $\mathbf{x} \in \operatorname{Nul} A$ is perpendicular to every row, and hence to every combination of rows, which is all of $\operatorname{Row} A$. Applying this to $A^T$ gives part 2, since the rows of $A^T$ are the columns of $A$. $\blacksquare$
Complements, not just perpendicular. The dimensions add up: $r + (n - r) = n$ and $r + (m - r) = m$. Orthogonal subspaces meet only in $\mathbf{0}$, because a vector perpendicular to itself is zero. By Grassmann's formula (Section 6.4), each pair therefore fills its whole space:
$$\mathbb{R}^n = \operatorname{Row} A \oplus \operatorname{Nul} A, \qquad \mathbb{R}^m = \operatorname{Col} A \oplus \operatorname{Nul} A^T.$$
In fact, each subspace is exactly the set of all vectors perpendicular to the other, its orthogonal complement (Section 9.2): $\operatorname{Nul} A = (\operatorname{Row} A)^\perp$ and $\operatorname{Nul} A^T = (\operatorname{Col} A)^\perp$.
R^n R^m
+----------------------------------+ +----------------------------------+
| Row A dim r | | Col A dim r |
| | A x_r = b | |
| x_r ----------------------------------------------------> b |
| | | |
| ------------ 90 degrees ------- | | ------------ 90 degrees ------- |
| | | |
| Nul A dim n - r | A x_n = 0 | Nul A^T dim m - r |
| x_n ----------------------------------------------------> 0 |
+----------------------------------+ +----------------------------------+
any x = x_r + x_n, so A x = A x_r: only the row-space part of x matters
Consequences.
- $A$ only sees the row-space part. Write $\mathbf{x} = \mathbf{x}_r + \mathbf{x}_n$ with $\mathbf{x}_r \in \operatorname{Row} A$ and $\mathbf{x}_n \in \operatorname{Nul} A$. Then $A\mathbf{x} = A\mathbf{x}_r$.
- $A$ is invertible from $\operatorname{Row} A$ to $\operatorname{Col} A$. If $A\mathbf{x}_r = A\mathbf{x}_r'$ with both in $\operatorname{Row} A$, then $\mathbf{x}_r - \mathbf{x}_r'$ lies in $\operatorname{Row} A \cap \operatorname{Nul} A = {\mathbf{0}}$. So $A$ maps the $r$-dimensional row space one-to-one onto the $r$-dimensional column space. Every matrix, however singular or rectangular, hides an invertible $r \times r$ map inside it.
- Solvability (Fredholm alternative). $A\mathbf{x} = \mathbf{b}$ is solvable $\iff$ $\mathbf{b} \in \operatorname{Col} A$ $\iff$ $\mathbf{b} \perp \operatorname{Nul} A^T$. This proves the sufficiency claimed in the left null space topic.
- Minimum-norm solution. Among all solutions $\mathbf{p} + \operatorname{Nul} A$ of a consistent system, exactly one lies in $\operatorname{Row} A$. It is the shortest solution, because adding a perpendicular null vector can only increase the length (Pythagoras). The pseudoinverse produces this solution (Sections 9.5 and 11.2).
import numpy as np
from scipy.linalg import null_space, orth
A = np.array([[1., 2., 0., 1.],
[2., 4., 1., 4.],
[3., 6., 1., 5.]])
Row = orth(A.T) # orthonormal basis of Row A (in R^4)
Nul = null_space(A) # orthonormal basis of Nul A (in R^4)
Col = orth(A) # orthonormal basis of Col A (in R^3)
LNul = null_space(A.T) # orthonormal basis of Nul A^T (in R^3)
print(Row.shape[1], Nul.shape[1], Col.shape[1], LNul.shape[1]) # 2 2 2 1
print(np.allclose(Row.T @ Nul, 0), np.allclose(Col.T @ LNul, 0)) # True True: perpendicular pairs
# Split x into its row-space and null-space parts; A only sees x_r
x = np.array([1., 1., 1., 1.])
x_r = Row @ (Row.T @ x) # orthogonal projection onto Row A (Section 9.2)
x_n = x - x_r
print(np.allclose(A @ x_n, 0), np.allclose(A @ x_r, A @ x), np.isclose(x_r @ x_n, 0)) # True True True
# Solvability: b is in Col A iff b is perpendicular to the left null space
for b in [np.array([1., 0., 1.]), np.array([1., 1., 1.])]:
print(b, np.isclose(LNul[:, 0] @ b, 0))
# [1. 0. 1.] True
# [1. 1. 1.] False
# The minimum-norm solution lies in Row A, and it is shorter than any other solution
b = np.array([1., 0., 1.])
x_min = np.linalg.pinv(A) @ b
x_other = x_min + Nul @ np.array([1., -2.]) # another solution: add a null space vector
print(np.allclose(A @ x_min, b), np.allclose(A @ x_other, b)) # True True
print(np.allclose(Nul.T @ x_min, 0), np.linalg.norm(x_min) < np.linalg.norm(x_other)) # True True
Key takeaways
- $\operatorname{Row} A \perp \operatorname{Nul} A$ in $\mathbb{R}^n$ and $\operatorname{Col} A \perp \operatorname{Nul} A^T$ in $\mathbb{R}^m$; each pair fills its space as a direct sum.
- Each vector splits as $\mathbf{x} = \mathbf{x}_r + \mathbf{x}_n$, and $A\mathbf{x} = A\mathbf{x}_r$.
- $A$ maps $\operatorname{Row} A$ one-to-one onto $\operatorname{Col} A$: an invertible core of size $r$.
- $A\mathbf{x} = \mathbf{b}$ is solvable exactly when $\mathbf{b} \perp \operatorname{Nul} A^T$; the unique solution in $\operatorname{Row} A$ is the shortest one.
- Existence is governed by $\operatorname{Col} A$ and $\operatorname{Nul} A^T$; uniqueness is governed by $\operatorname{Nul} A$.
🧪 Practice
- For $A = \begin{bmatrix} 1 & 2 \ 2 & 4 \end{bmatrix}$, find all four fundamental subspaces, sketch them in two copies of $\mathbb{R}^2$, and check both orthogonality relations.
- Show directly from the definitions that if $A\mathbf{x} = \mathbf{b}$ and $A^T\mathbf{y} = \mathbf{0}$, then $\mathbf{y} \cdot \mathbf{b} = 0$.
- Find the minimum-norm solution of the single equation $x_1 + x_2 + x_3 = 3$ by using the fact that it lies in $\operatorname{Row} A$, and verify that it is shorter than the solution $(3, 0, 0)$.
- Interview: Explain the "four fundamental subspaces" picture in two minutes to a colleague who knows only how to solve $A\mathbf{x} = \mathbf{b}$. Which subspace decides whether a solution exists, which decides whether it is unique, and how do their dimensions follow from the rank? Hint: existence: $\mathbf{b} \in \operatorname{Col} A$, equivalently $\mathbf{b} \perp \operatorname{Nul} A^T$; uniqueness: $\operatorname{Nul} A = {\mathbf{0}}$; dimensions $r$, $r$, $n - r$, $m - r$.
<a id="7-linear-transformations"></a>