Suppose someone hands you the three vectors \begin{align*} v_1 &= (1, 0, 0), \quad v_2 = (0, 1, 0), \quad v_3 = (0, 0, 1) \end{align*} in $\mathbb{R}^3$ and asks: "Do these span the space? Are any of them redundant?" Both questions feel easy here. But now consider the four vectors \begin{align*} w_1 &= (1, 2, 3), \quad w_2 = (0, 1, 2), \quad w_3 = (1, 1, 1), \quad w_4 = (2, 3, 4) \end{align*} and the same questions become substantially harder. Is every vector in $\mathbb{R}^3$ a linear combination of the $w_i$? Can any one of them be removed without losing span? These are not separate puzzles — they are two faces of a single underlying concept: the **basis**. A basis for a vector space is a set of vectors that is simultaneously large enough to span the space (every vector can be expressed as a linear combination) and small enough to be irredundant (no vector is a combination of the others). This double requirement is the source of all the theory: it forces a precise notion of "size" for a vector space, independent of coordinate choices, and it makes coordinate representations unique. The **dimension** of a space is the number of vectors in any basis, and the remarkable fact — which requires proof — is that this number does not depend on which basis you choose. [example: Redundancy in $\mathbb{R}^2$] Consider the three vectors \begin{align*} u_1 &= (1, 0), \quad u_2 = (0, 1), \quad u_3 = (1, 1). \end{align*} They span $\mathbb{R}^2$ — every $(a, b) = a\, u_1 + b\, u_2$ — but they are not a basis, because $u_3 = u_1 + u_2$. Dropping $u_3$ leaves $\{u_1, u_2\}$, which still spans $\mathbb{R}^2$ and has no redundancies: neither $u_1$ nor $u_2$ is a scalar multiple of the other. The pair $\{u_1, u_2\}$ is a basis. The lesson is that three vectors in a two-dimensional space must be linearly dependent — you cannot have three irredundant vectors when only two directions exist. [/example] This page develops the theory of bases and dimension from scratch, building through three stages: the formal definition and its equivalent characterizations, the key theorems on existence and invariance of dimension, and the rich geometry that dimension controls — subspaces, complements, and rank. ## Definition The concept of a basis rests on two properties that must hold simultaneously. Before giving the formal definition, it helps to state each property separately and understand what fails when only one holds. A spanning set can always be found — take all vectors in the space. But a spanning set may be wildly redundant. On the other hand, a linearly independent set can always be found — take a single nonzero vector. But a linearly independent set may be far too small to reach every vector in the space. A basis asks for both at once: no redundancy, and full reach. [definition: Basis] Let $V$ be a vector space over a field $F$. A **basis** for $V$ is a subset $\mathcal{B} \subset V$ such that: 1. $\mathcal{B}$ is **linearly independent**: for any finite collection $v_1, \ldots, v_k \in \mathcal{B}$ and scalars $c_1, \ldots, c_k \in F$, \begin{align*} c_1 v_1 + c_2 v_2 + \cdots + c_k v_k = 0 \implies c_1 = c_2 = \cdots = c_k = 0. \end{align*} 2. $\mathcal{B}$ **spans** $V$: every $v \in V$ can be written as a finite linear combination \begin{align*} v = c_1 v_1 + c_2 v_2 + \cdots + c_k v_k \end{align*} for some $v_1, \ldots, v_k \in \mathcal{B}$ and $c_1, \ldots, c_k \in F$. [/definition] The two conditions together force something striking: every vector has a *unique* representation in terms of the basis. This is the fundamental reason bases are useful — they give a coordinate system. [quotetheorem:372] Uniqueness follows immediately from linear independence: subtracting gives $\sum_{i=1}^n (c_i - d_i) b_i = 0$, and linear independence forces each $c_i - d_i = 0$. The scalars $(c_1, \ldots, c_n)$ are called the **coordinates** of $v$ with respect to the basis $\mathcal{B}$. Once a basis is chosen, a vector space of dimension $n$ is indistinguishable from $F^n$ as far as linear algebra is concerned. [remark: Basis as a Minimal Spanning Set and Maximal Independent Set] A basis admits two equivalent characterizations that make its extremal nature precise. A spanning set $\mathcal{B}$ for $V$ is a basis if and only if no proper subset of $\mathcal{B}$ still spans $V$ (minimality). Equivalently, a linearly independent set $\mathcal{B}$ is a basis if and only if no proper superset of $\mathcal{B}$ remains linearly independent (maximality). These equivalences are exercises in unfolding the definitions, but they clarify why a basis is exactly the right size: too few vectors and you miss part of the space; too many and you introduce dependence. [/remark] [example: Standard Bases] Several natural bases appear throughout mathematics: **Standard basis for $\mathbb{R}^n$.** The vectors $e_i \in \mathbb{R}^n$ with $(e_i)_j = \delta_{ij}$ (Kronecker delta) form the standard basis $\{e_1, \ldots, e_n\}$. Linear independence holds because \begin{align*} \sum_{i=1}^n c_i e_i = (c_1, c_2, \ldots, c_n) = 0 \implies c_1 = \cdots = c_n = 0. \end{align*} Spanning holds because any $(a_1, \ldots, a_n) = \sum_{i=1}^n a_i e_i$. **Standard basis for polynomials.** In the space $\mathbb{R}[t]_{\le n}$ of polynomials of degree at most $n$, the monomials $\{1, t, t^2, \ldots, t^n\}$ form a basis. Independence follows from the fact that $c_0 + c_1 t + \cdots + c_n t^n = 0$ as a polynomial identity forces all $c_i = 0$ (a nonzero polynomial of degree $n$ has at most $n$ roots, so it cannot be identically zero unless all coefficients vanish). Spanning holds because every polynomial of degree $\le n$ is by definition a linear combination of $\{1, t, \ldots, t^n\}$. **Trigonometric basis.** In the space of functions spanned by $\{\cos(k\theta)\}_{k=0}^n \cup \{\sin(k\theta)\}_{k=1}^n$ over $\mathbb{R}$, these $2n+1$ functions form a basis. The independence argument uses the orthogonality of these functions under the integral inner product on $[0, 2\pi]$, which we develop in the section on inner products below. [/example] ## Existence and the Steinitz Exchange Lemma When does a basis exist, and how many elements must it have? For finite-dimensional spaces the answers are clean: a basis always exists, and all bases have the same number of elements. The key tool is the **Steinitz Exchange Lemma**, which makes precise how one can swap vectors between a spanning set and a linearly independent set while preserving the span. Before stating the lemma, notice what could go wrong without it. If a linearly independent set and a spanning set have different sizes, the relationship between them is not obvious. The lemma resolves this by showing that independent sets can never be larger than spanning sets — any independent set can be "absorbed" into any spanning set by a sequence of exchanges. [quotetheorem:373] The proof proceeds by induction on $m$. The base case $m = 0$ is vacuous. For the inductive step, one writes $u_{m+1}$ as a linear combination of the current spanning set; since $u_{m+1}$ is not in the span of $\{u_1, \ldots, u_m\}$ (by linear independence), at least one $w_j$ in the combination must have a nonzero coefficient, and that $w_j$ can be replaced by $u_{m+1}$ without disrupting span. The induction terminates after $m$ steps. The Steinitz Lemma has an immediate corollary that is one of the most important facts in linear algebra. [quotetheorem:915] To see why: let $\mathcal{B}_1$ and $\mathcal{B}_2$ be two finite bases. Since $\mathcal{B}_1$ is linearly independent and $\mathcal{B}_2$ spans $V$, the Steinitz Lemma gives $|\mathcal{B}_1| \le |\mathcal{B}_2|$. Symmetrically, since $\mathcal{B}_2$ is independent and $\mathcal{B}_1$ spans, $|\mathcal{B}_2| \le |\mathcal{B}_1|$. Hence $|\mathcal{B}_1| = |\mathcal{B}_2|$. This invariance is what makes the definition of dimension possible. [definition: Dimension] Let $V$ be a vector space over $F$ that admits a finite basis. The **dimension** of $V$, written $\dim V$ or $\dim_F V$, is the number of elements in any basis for $V$. If $V$ has no finite basis, $V$ is said to be **infinite-dimensional**. [/definition] The definition is well-posed precisely because of the Invariance Theorem: the dimension does not depend on which basis we choose. This is not obvious — it requires proof — and the Steinitz Lemma provides that proof. [example: Computing Dimensions] **Polynomials.** The space $\mathbb{R}[t]_{\le n}$ has dimension $n+1$: the basis $\{1, t, \ldots, t^n\}$ has $n+1$ elements. Note that $\mathbb{R}[t]$ (polynomials of all degrees) is infinite-dimensional, since for any finite set of polynomials $\{p_1, \ldots, p_k\}$, the polynomial $t^{N+1}$ lies outside their span whenever $N$ exceeds all degrees of $p_1, \ldots, p_k$. **Matrices.** The space $M_{m \times n}(F)$ of $m \times n$ matrices has dimension $mn$: the basis consists of the elementary matrices $E_{ij}$ ($1$ in position $(i,j)$, zeros elsewhere), of which there are $mn$. **Solutions to linear systems.** The solution set of a homogeneous linear system $Ax = 0$ with $A \in M_{m \times n}(F)$ is a subspace of $F^n$. If $A$ has rank $r$, then this solution space (the **null space** of $A$) has dimension $n - r$. We will prove this as part of the Rank-Nullity Theorem below. [/example] [explanation: Why Finite-Dimensionality Is Not Automatic] Not every vector space is finite-dimensional. The space $C([0, 1])$ of continuous functions $f: [0,1] \to \mathbb{R}$ is infinite-dimensional: for each $n \in \mathbb{N}$, the polynomials $\{1, t, t^2, \ldots, t^n\}$ are independent, so there is no finite spanning set (a finite spanning set would impose an upper bound on the number of independent vectors). Similarly, $\ell^2 = \{(a_1, a_2, \ldots) : \sum_{i=1}^\infty a_i^2 < \infty\}$ is infinite-dimensional: the sequences $e_i$ (with $1$ in position $i$ and $0$ elsewhere) form an independent family of any finite size. Infinite-dimensional spaces require significantly more care: existence of bases (Hamel bases) relies on the Axiom of Choice, and the resulting bases are typically uncountable and non-constructive. For this reason, much of analysis works with other structures (Schauder bases, frames) rather than Hamel bases. On this page, "basis" always means a Hamel basis unless otherwise specified. [/explanation] ## Completing and Trimming: The Two Directions The Steinitz Lemma encodes two fundamental operations: extending a linearly independent set to a basis, and extracting a basis from a spanning set. Together, these show that bases arise naturally from both directions. Given a linearly independent set $S$ in a finite-dimensional space $V$, can we always extend it to a full basis? Given a spanning set $T$, can we always trim it down to a basis? The answer to both is yes, and the proofs are constructive algorithms. [quotetheorem:3270] [quotetheorem:3271] The extraction algorithm is greedy: initialize $\mathcal{B} = \varnothing$ and process the $w_i$ in order. Add $w_i$ to $\mathcal{B}$ if it is not in the span of the vectors already in $\mathcal{B}$; otherwise discard $w_i$. At the end, $\mathcal{B}$ spans $V$ (since every discarded vector was already in the span of retained ones) and is independent (since each vector added was outside the span of previous ones). The set $\mathcal{B}$ is a basis. [example: Extracting a Basis from a Redundant Set] Return to the vectors from the opening: \begin{align*} w_1 &= (1, 2, 3), \quad w_2 = (0, 1, 2), \quad w_3 = (1, 1, 1), \quad w_4 = (2, 3, 4). \end{align*} We apply the extraction algorithm. Start with $\mathcal{B} = \{w_1\}$. Add $w_2$ since $(0,1,2)$ is not a scalar multiple of $(1,2,3)$: $\mathcal{B} = \{w_1, w_2\}$. Now check $w_3 = (1,1,1)$: is $(1,1,1) = a(1,2,3) + b(0,1,2)$ for some $a, b$? The system gives $a = 1$, $2a + b = 1$, $3a + 2b = 1$, so $b = -1$ and $3(1) + 2(-1) = 1$. Yes, $w_3 = w_1 - w_2$, so discard $w_3$. Check $w_4 = (2,3,4)$: is $(2,3,4) = a(1,2,3) + b(0,1,2)$? Then $a = 2$, $2a + b = 3 \implies b = -1$, and $3a + 2b = 4$. Yes, $w_4 = 2w_1 - w_2$, so discard $w_4$. The extracted basis is $\{w_1, w_2\} = \{(1,2,3), (0,1,2)\}$. Since we extracted two vectors from a subspace of $\mathbb{R}^3$, the span of $\{w_1, w_2, w_3, w_4\}$ has dimension 2 — it is a plane in $\mathbb{R}^3$, not the full space. The vectors $\{w_1, \ldots, w_4\}$ do not span $\mathbb{R}^3$. [/example] [illustration:spanning-plane-r3] These two theorems have a corollary that is frequently useful in practice: to show a set $S$ with exactly $\dim V = n$ elements is a basis, it suffices to check either linear independence or spanning — not both. [quotetheorem:3272] This is enormously useful: to verify that $n$ specific vectors form a basis for an $n$-dimensional space, you only need to check independence (which is usually easier to verify directly) or spanning (which is sometimes easier). You never need to check both. ## Subspaces, Sum, and the Dimension Formula The theory of dimension becomes much richer when applied to subspaces and their relationships. The central result here is the **Dimension Formula** (also called the inclusion-exclusion formula for subspaces), which quantifies how two subspaces overlap. Before the formula, we need to know that subspaces of finite-dimensional spaces are themselves finite-dimensional, and that their dimension is bounded. [quotetheorem:375] The proof is constructive: any linearly independent set in $W$ is also independent in $V$, and by the Steinitz Lemma any independent set in $V$ has at most $n$ elements. So build a basis for $W$ by successively adding independent vectors — the process must terminate in at most $n$ steps. The boundary case is equally important: if $\dim W = \dim V = n$, then a basis for $W$ has $n$ elements and spans $W$. But a spanning set of size $n = \dim V$ that lies in $V$ must span all of $V$ (by the Dimension Count Criterion). Hence $W = V$. Now for the formula itself. Given two subspaces $U$ and $W$ of $V$, how should we form a subspace that contains both? The naive candidate is the union $U \cup W$, but the union of two subspaces is almost never a subspace: in $\mathbb{R}^2$, take $U = \operatorname{span}\{e_1\}$ and $W = \operatorname{span}\{e_2\}$; then $e_1 \in U$ and $e_2 \in W$, but $e_1 + e_2 \notin U \cup W$. The correct operation is the sum $U + W$, which takes all pairwise sums and thereby closes under addition. It is the smallest subspace of $V$ that contains both $U$ and $W$, and it is this object whose dimension obeys a clean formula. The intersection $U \cap W$ is also a subspace, and the four quantities $\dim U$, $\dim W$, $\dim(U+W)$, $\dim(U \cap W)$ are linked by an exact identity. [definition: Sum of Subspaces] Let $V$ be a vector space and $U, W \subset V$ subspaces. The **sum** of $U$ and $W$ is \begin{align*} U + W &= \{u + w : u \in U, \, w \in W\}. \end{align*} The sum $U + W$ is the smallest subspace of $V$ containing both $U$ and $W$. [/definition] [quotetheorem:376] The formula is an analogue of inclusion-exclusion for sets: $|A \cup B| = |A| + |B| - |A \cap B|$. But the proof is more delicate because the "union" of two subspaces need not be a subspace; one works with $U + W$ instead. The proof builds a basis in stages. Let $\{x_1, \ldots, x_k\}$ be a basis for $U \cap W$. Since $U \cap W \subset U$, extend this to a basis $\{x_1, \ldots, x_k, u_1, \ldots, u_p\}$ for $U$; similarly extend to a basis $\{x_1, \ldots, x_k, w_1, \ldots, w_q\}$ for $W$. The claim is that \begin{align*} \{x_1, \ldots, x_k, u_1, \ldots, u_p, w_1, \ldots, w_q\} \end{align*} is a basis for $U + W$. Spanning is clear. For independence, if \begin{align*} \sum_{i=1}^k a_i x_i + \sum_{j=1}^p b_j u_j + \sum_{l=1}^q c_l w_l &= 0, \end{align*} rearranging gives $\sum c_l w_l = -\sum a_i x_i - \sum b_j u_j \in U$. But $\sum c_l w_l \in W$ as well, so it lies in $U \cap W$ and can be written as $\sum d_i x_i$. Then $\sum c_l w_l - \sum d_i x_i = 0$, and independence within $W$ forces all $c_l = 0$ and all $d_i = 0$. Back-substituting, $\sum a_i x_i + \sum b_j u_j = 0$, and independence within $U$ forces all $a_i = b_j = 0$. The basis has $k + p + q$ elements, so $\dim(U + W) = k + p + q = (k + p) + (k + q) - k = \dim U + \dim W - \dim(U \cap W)$. [example: Intersecting Planes in $\mathbb{R}^4$] Let $U$ and $W$ be subspaces of $\mathbb{R}^4$ defined by: \begin{align*} U &= \operatorname{span}\{(1,0,1,0),\, (0,1,0,1)\}, \\ W &= \operatorname{span}\{(1,1,0,0),\, (0,0,1,1)\}. \end{align*} Each has dimension 2. The Dimension Formula predicts $\dim(U + W) = 2 + 2 - \dim(U \cap W)$. To find $U \cap W$, a vector $v \in U \cap W$ must satisfy $v = a(1,0,1,0) + b(0,1,0,1) = c(1,1,0,0) + d(0,0,1,1)$ for some $a, b, c, d$. Setting components equal: \begin{align*} a &= c, \quad b = c, \quad a = d, \quad b = d. \end{align*} So $a = b = c = d$. The intersection is therefore $\{a(1,1,1,1) : a \in \mathbb{R}\} = \operatorname{span}\{(1,1,1,1)\}$, which has dimension 1. The Dimension Formula gives $\dim(U + W) = 2 + 2 - 1 = 3$. Indeed, $U + W$ is spanned by the four given vectors together with $(1,1,1,1)$ — but $(1,1,1,1)$ is already in $U + W$, and the four generators span a 3-dimensional space. One can verify that $(1,0,1,0)$, $(0,1,0,1)$, $(1,1,0,0)$ are independent and together span $U + W$. [/example] ## Direct Sums and Complements The Dimension Formula is most elegant when $U \cap W = \{0\}$, in which case $\dim(U + W) = \dim U + \dim W$. This case is so important that it receives its own name. [definition: Direct Sum] Let $V$ be a vector space and $U, W$ subspaces of $V$. The sum $U + W$ is a **direct sum**, written $V = U \oplus W$, if $U \cap W = \{0\}$. In this case, every $v \in V$ has a unique decomposition $v = u + w$ with $u \in U$ and $w \in W$. [/definition] The uniqueness of decomposition follows from the trivial intersection: if $u_1 + w_1 = u_2 + w_2$ then $u_1 - u_2 = w_2 - w_1 \in U \cap W = \{0\}$, so $u_1 = u_2$ and $w_1 = w_2$. Direct sums encode the absence of overlap. When two subspaces have no overlap (other than the zero vector), they are completely independent of each other in a precise sense. The dimension is then simply additive. [quotetheorem:3273] This is the special case $\dim(U \cap W) = \dim\{0\} = 0$ in the Dimension Formula. Given a subspace $U \subset V$, does a complement always exist? The answer is yes, but in a general vector space it is not unique — there are many subspaces $W$ with $V = U \oplus W$. [quotetheorem:3274] The construction: take a basis $\{u_1, \ldots, u_k\}$ for $U$ and extend it to a basis $\{u_1, \ldots, u_k, w_1, \ldots, w_{n-k}\}$ for $V$. Set $W = \operatorname{span}\{w_1, \ldots, w_{n-k}\}$. Then $U \cap W = \{0\}$ (any vector in the intersection would have two representations in the full basis, contradicting uniqueness), so $V = U \oplus W$ and $\dim W = n - k$. [remark: Non-uniqueness of Complements] While a complement always exists, it is never unique unless $U = \{0\}$ or $U = V$. In $\mathbb{R}^2$ with $U = \operatorname{span}\{(1,0)\}$, any line through the origin that is not $U$ is a complement. The $y$-axis $\operatorname{span}\{(0,1)\}$ is one; $\operatorname{span}\{(1,1)\}$ is another. Without additional structure (such as an inner product), there is no canonical choice. In an inner product space, the **orthogonal complement** $U^\perp$ is the canonical choice, and it is the subject of the page on orthogonality. [/remark] ## Rank and the Rank-Nullity Theorem The most important application of dimension theory to linear maps is the **Rank-Nullity Theorem**, which governs the dimensions of the kernel and image of a linear map. It is the cornerstone of the theory of linear equations. Let $T: V \to W$ be a linear map between vector spaces. Two subspaces naturally associated to $T$ are its kernel and its image: [definition: Kernel and Image of a Linear Map] Let $T: V \to W$ be a linear map. The **kernel** of $T$ is \begin{align*} \ker(T) &= \{v \in V : T(v) = 0\}, \end{align*} which is a subspace of $V$. The **image** (or **range**) of $T$ is \begin{align*} \operatorname{Range}(T) &= \{T(v) : v \in V\} = \{w \in W : w = T(v) \text{ for some } v \in V\}, \end{align*} which is a subspace of $W$. The **nullity** of $T$ is $\dim(\ker T)$ and the **rank** of $T$ is $\dim(\operatorname{Range}(T))$. [/definition] The kernel measures how far $T$ is from being injective: $T$ is injective if and only if $\ker(T) = \{0\}$, i.e., nullity zero. The image measures the reach of $T$: $T$ is surjective if and only if $\operatorname{Range}(T) = W$. [quotetheorem:916] The proof constructs a basis explicitly. Let $\{u_1, \ldots, u_k\}$ be a basis for $\ker(T)$, and extend to a basis $\{u_1, \ldots, u_k, v_1, \ldots, v_m\}$ for $V$. The claim is that $\{T(v_1), \ldots, T(v_m)\}$ is a basis for $\operatorname{Range}(T)$. Spanning: any $T(v) = T(\sum a_i u_i + \sum b_j v_j) = \sum b_j T(v_j)$ since each $T(u_i) = 0$. Independence: if $\sum c_j T(v_j) = 0$, then $T(\sum c_j v_j) = 0$, so $\sum c_j v_j \in \ker(T)$, so $\sum c_j v_j = \sum d_i u_i$ for some $d_i$, so $\sum c_j v_j - \sum d_i u_i = 0$. By independence of the full basis, all $c_j = d_i = 0$. Hence $\{T(v_1), \ldots, T(v_m)\}$ is a basis for $\operatorname{Range}(T)$, and $\dim V = k + m = \operatorname{nullity}(T) + \operatorname{rank}(T)$. [example: Rank-Nullity for a Differentiation Map] Let $V = \mathbb{R}[t]_{\le 3}$ (polynomials of degree $\le 3$, dimension 4) and define the differentiation map \begin{align*} D: V &\to V \\ p(t) &\mapsto p'(t). \end{align*} Note $D$ maps into $\mathbb{R}[t]_{\le 2} \subset V$ (since differentiation reduces degree by 1). The kernel $\ker(D)$ consists of polynomials with $p'(t) = 0$, i.e., constant polynomials $\{c : c \in \mathbb{R}\} = \operatorname{span}\{1\}$. So $\operatorname{nullity}(D) = 1$. By Rank-Nullity, $\operatorname{rank}(D) = \dim V - \operatorname{nullity}(D) = 4 - 1 = 3$. We can verify: $\operatorname{Range}(D) = \{p' : p \in V\} = \{at^2 + bt + c : a,b,c \in \mathbb{R}\} = \mathbb{R}[t]_{\le 2}$, and indeed $\dim(\mathbb{R}[t]_{\le 2}) = 3$. The map $D$ is not injective ($\ker D \ne \{0\}$) and is not surjective onto $V$ ($D$ cannot produce $t^3$), but it is surjective onto $\mathbb{R}[t]_{\le 2}$. [/example] [example: Rank-Nullity and Linear Systems] Let $A \in M_{m \times n}(F)$ be a matrix and consider the linear map $T_A: F^n \to F^m$ defined by $T_A(x) = Ax$. Then: - $\ker(T_A)$ is the null space of $A$, written $\ker(A) = \{x \in F^n : Ax = 0\}$. - $\operatorname{Range}(T_A)$ is the column space of $A$, spanned by the columns of $A$. If $A$ has rank $r$ (meaning $r$ linearly independent rows, equivalently $r$ linearly independent columns), then $\dim(\operatorname{Range}(T_A)) = r$ and the Rank-Nullity Theorem gives $\dim(\ker(T_A)) = n - r$. Concretely, if $A$ is a $4 \times 5$ matrix of rank 3, the null space of $A$ has dimension $5 - 3 = 2$. The system $Ax = 0$ has a two-dimensional solution space, and the system $Ax = b$ (when consistent) has solutions forming a coset of this two-dimensional space. This underpins the fundamental theorem of linear algebra: the number of free variables in a linear system is exactly the nullity of the coefficient matrix. [/example] [quotetheorem:389] This is a non-obvious symmetry: the dimension of the column space equals the dimension of the row space, even though these are subspaces of completely different ambient spaces ($F^m$ and $F^n$ respectively). The proof proceeds by row reduction and shows that row operations do not change the column rank. ## Change of Basis Different choices of basis for the same space lead to different coordinate representations of vectors and linear maps. Understanding how coordinates transform under a change of basis is essential for working with matrices. Why would one want to change basis? The most compelling reason is that the right choice of basis can make a linear operator look simple. A general linear operator $T: V \to V$ is represented by some matrix in the standard basis — possibly dense with nonzero entries and offering no obvious structure. But if $T$ is diagonalizable, there exists a basis of eigenvectors in which the matrix of $T$ is diagonal: the action of $T$ becomes multiplication by scalars, and powers $T^k$, exponentials $e^{tT}$, and spectral properties are all immediately readable. Passing to the eigenbasis is a change of basis, and the change of basis matrix encodes exactly how to convert coordinates between the old representation and the new one. Even when $T$ is not diagonalizable, one can choose bases adapted to the Jordan normal form or to the geometry of the problem. Change of basis is the tool that separates intrinsic properties of an operator — its eigenvalues, determinant, characteristic polynomial — from the accidental features of a particular coordinate system. Suppose $\mathcal{B} = \{b_1, \ldots, b_n\}$ and $\mathcal{C} = \{c_1, \ldots, c_n\}$ are two bases for a finite-dimensional vector space $V$. If $v \in V$ has coordinate vector $(x_1, \ldots, x_n)$ in the $\mathcal{B}$-basis, what are its coordinates in the $\mathcal{C}$-basis? [definition: Change of Basis Matrix] Let $V$ be an $n$-dimensional vector space over $F$ with bases $\mathcal{B} = \{b_1, \ldots, b_n\}$ and $\mathcal{C} = \{c_1, \ldots, c_n\}$. The **change of basis matrix** from $\mathcal{B}$ to $\mathcal{C}$, written $P_{\mathcal{B} \to \mathcal{C}}$, is the $n \times n$ matrix whose $j$-th column is the coordinate vector of $b_j$ expressed in the $\mathcal{C}$-basis: \begin{align*} b_j &= \sum_{i=1}^n (P_{\mathcal{B} \to \mathcal{C}})_{ij} \, c_i. \end{align*} [/definition] The change of basis matrix is always invertible: $(P_{\mathcal{B} \to \mathcal{C}})^{-1} = P_{\mathcal{C} \to \mathcal{B}}$. This follows from the fact that expressing each $b_j$ in the $\mathcal{C}$-basis and then converting back must return the original. [quotetheorem:3275] The second formula, $[T]_\mathcal{C} = P [T]_\mathcal{B} P^{-1}$, is the definition of **similar matrices**: two matrices $A$ and $B$ are similar if $B = PAP^{-1}$ for some invertible $P$. Similar matrices represent the same linear operator in different bases, and they share all intrinsic properties of the operator: determinant, trace, characteristic polynomial, eigenvalues. [example: Change of Basis in $\mathbb{R}^2$] Let $V = \mathbb{R}^2$ with standard basis $\mathcal{B} = \{e_1, e_2\} = \{(1,0), (0,1)\}$ and new basis $\mathcal{C} = \{c_1, c_2\} = \{(1,1), (1,-1)\}$. Express $e_1$ and $e_2$ in terms of $\mathcal{C}$. We need $e_1 = \alpha c_1 + \beta c_2$, so \begin{align*} (1, 0) &= \alpha(1,1) + \beta(1,-1) = (\alpha + \beta, \alpha - \beta). \end{align*} Solving: $\alpha + \beta = 1$ and $\alpha - \beta = 0$, giving $\alpha = \beta = 1/2$. Similarly, $e_2 = \frac{1}{2}c_1 - \frac{1}{2}c_2$. The change of basis matrix is \begin{align*} P_{\mathcal{B} \to \mathcal{C}} &= \begin{pmatrix} 1/2 & 1/2 \\ 1/2 & -1/2 \end{pmatrix}. \end{align*} For example, the vector $v = (3, 1)$ has $\mathcal{B}$-coordinates $(3, 1)^\top$. In the $\mathcal{C}$-basis: \begin{align*} [v]_\mathcal{C} &= P_{\mathcal{B} \to \mathcal{C}} \begin{pmatrix} 3 \\ 1 \end{pmatrix} = \begin{pmatrix} 1/2 \cdot 3 + 1/2 \cdot 1 \\ 1/2 \cdot 3 - 1/2 \cdot 1 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \end{pmatrix}. \end{align*} Indeed, $v = (3,1) = 2(1,1) + 1(1,-1) = 2c_1 + c_2$. The formula gives the correct coordinates. [/example] [illustration:change-of-basis-r2] The theory of change of basis is the bridge between the abstract, coordinate-free world of vector spaces and the concrete, computational world of matrices. A linear operator is an intrinsic object; its matrix is a representation that depends on a choice of basis. The Rank-Nullity Theorem, the Dimension Formula, and the invariance of dimension all describe intrinsic properties — properties that are the same in every coordinate system. ## When Dimension Reasoning Goes Wrong Dimension arguments are so clean that it is tempting to apply them carelessly. The following examples show concretely where the reasoning breaks down. [example: The Union Fallacy] A common mistake is to conflate the sum $U + W$ with the union $U \cup W$. Suppose a student reasons: "I have a 2-dimensional subspace $U$ and a 2-dimensional subspace $W$ inside $\mathbb{R}^3$, and they are different, so together they must span $\mathbb{R}^3$." The error is the word "together." The set $U \cup W$ is not a subspace, and the student is implicitly imagining the sum $U + W$ — but the Dimension Formula gives $\dim(U + W) = 2 + 2 - \dim(U \cap W)$. If $U$ and $W$ are two distinct planes through the origin in $\mathbb{R}^3$, they intersect in a line, so $\dim(U \cap W) = 1$ and $\dim(U + W) = 3$. But if both planes happen to contain the same line — say $U = \operatorname{span}\{e_1, e_2\}$ and $W = \operatorname{span}\{e_1, e_3\}$ — then $U \cap W = \operatorname{span}\{e_1\}$, and $\dim(U + W) = 3$. The conclusion is correct here, but it is correct for the right reason (the intersection is only 1-dimensional), not because the spaces are "different." Now change the example: let $U = W = \operatorname{span}\{e_1, e_2\}$. Now $\dim U = \dim W = 2$, but $U \cap W = U$ has dimension 2, so $\dim(U + W) = 2 + 2 - 2 = 2$. The "sum" of $U$ with itself is just $U$ — you get no new vectors at all. The moral: you cannot count dimensions of subspaces by simply adding, without subtracting the overlap. [/example] [example: Dimension Count Criterion Applied in the Wrong Space] The Dimension Count Criterion says: if $V$ has dimension $n$ and $S$ is a set of $n$ vectors in $V$, then $S$ is a basis iff $S$ is independent iff $S$ spans $V$. A student tries to apply this as follows: "The space $W = \operatorname{span}\{e_1, e_2\}$ inside $\mathbb{R}^3$ has dimension 2. The two vectors $v_1 = (1, 1, 0)$ and $v_2 = (0, 1, 0)$ are linearly independent, so they form a basis for $\mathbb{R}^3$." The count is wrong: $W$ has dimension 2, but $\mathbb{R}^3$ has dimension 3, and two vectors can never span $\mathbb{R}^3$. The criterion applies within a fixed ambient space $V$ — it does not say that $n$ independent vectors in a subspace of $V$ span all of $V$. More subtly: suppose a student writes down $n$ vectors in $V$ and verifies they are pairwise non-parallel (no two are scalar multiples of each other). This is not the same as linear independence. In $\mathbb{R}^3$, the three vectors $v_1 = (1,0,0)$, $v_2 = (0,1,0)$, $v_3 = (1,1,0)$ are pairwise non-parallel, but $v_3 = v_1 + v_2$, so they are linearly dependent and do not form a basis for any 3-dimensional space. Pairwise non-parallelism is a strictly weaker condition than linear independence once $n \ge 3$. [/example] [remark: The Rank-Nullity Theorem Does Not Apply to Non-Linear Maps] The Rank-Nullity Theorem is a theorem about linear maps. For a non-linear map $f: \mathbb{R}^n \to \mathbb{R}^m$, there is no analogue: the preimage $f^{-1}(0)$ is not generally a subspace and may have any topology. For instance, the map $f: \mathbb{R}^2 \to \mathbb{R}$ defined by $f(x, y) = x^2 + y^2 - 1$ has $f^{-1}(0)$ equal to the unit circle, a 1-dimensional manifold, but $\mathbb{R}^2$ has dimension 2 and $\mathbb{R}$ has dimension 1, so the "rank-nullity" formula $2 = \dim(\ker f) + \dim(\operatorname{Range}(f))$ would give $\dim(\ker f) = 1$ — which happens to match the circle's dimension for a different reason (the implicit function theorem), but only by coincidence and not as an application of the theorem. [/remark] ## Connections to Broader Mathematics The concept of dimension as developed on this page — the cardinality of a Hamel basis, defined for vector spaces over an arbitrary field — extends in several directions, each requiring genuinely new ideas. [remark: Functional Analysis: Infinite Dimensions and Topological Bases] In infinite-dimensional spaces (Hilbert spaces, Banach spaces), Hamel bases exist by the Axiom of Choice but are analytically useless: a Hamel basis for $L^2([0,1])$ is uncountable and non-constructive. The correct substitute is a **Schauder basis** — a countable sequence $(e_n)$ such that every element $x$ in the space has a unique norm-convergent expansion $x = \sum_{n=1}^\infty c_n e_n$. The trigonometric functions $\{1, \cos(n\theta), \sin(n\theta)\}_{n \ge 1}$ form a Schauder basis for $L^2([0, 2\pi])$, which is the content of $L^2$ Fourier series theory. The notion of "dimension" in this context becomes the **topological dimension** of the space (the minimum cardinality of a Schauder basis, or equivalently the density character), and separable Hilbert spaces all have topological dimension $\aleph_0$, even though their Hamel dimension is $2^{\aleph_0}$. The machinery of functional analysis — spectral theory, compact operators, the Fredholm alternative — all depend on this distinction. [/remark] [remark: Field Extensions: Dimension as Degree] In abstract algebra, a field extension $K / k$ makes $K$ into a vector space over $k$. The dimension $[K : k] := \dim_k K$ is called the **degree** of the extension and is one of the central invariants in Galois theory. The Tower Law — if $k \subset E \subset K$ are fields, then $[K : k] = [K : E][E : k]$ — is exactly the multiplicativity of dimension in a tower of vector spaces. The classical impossibility proofs (trisection of an angle, duplication of the cube) reduce to showing that the degree $[\mathbb{Q}(\alpha) : \mathbb{Q}]$ for the relevant algebraic number $\alpha$ is not a power of 2, which would be required for a ruler-and-compass construction. Here, dimension is not merely a bookkeeping device — it is the engine of the proof. [/remark] [remark: Representation Theory: Modules over Non-Fields] When the scalar ring is not a field but a more general ring $R$, the notion of a "vector space" becomes an $R$-module, and the clean theory of bases can break down: a free module has a well-defined rank (the cardinality of a basis), but not every module is free, and rank alone does not determine the isomorphism type. The study of how groups and algebras act on vector spaces — representation theory — uses the dimension of a representation (as a vector space over $\mathbb{C}$) as a fundamental invariant: it appears in character tables, in Burnside's theorem on solvability of groups of order $p^a q^b$, and in the Artin–Wedderburn theorem classifying semisimple algebras. [/remark] ## References Axler, S., *Linear Algebra Done Right* (2015). Halmos, P. R., *Finite-Dimensional Vector Spaces* (1958). Horn, R. A. and Johnson, C. R., *Matrix Analysis* (2013). Lang, S., *Linear Algebra* (1987). Roman, S., *Advanced Linear Algebra* (2008).