Basis, Dimension and Coordinates in a Basis

Span (Chapter 2) tells us how to generate a subspace from a set of vectors, but says nothing about efficiency — a spanning set can carry redundant vectors. This chapter isolates the notion of a maximally efficient, non-redundant spanning set — a basis — and proves the single theorem that makes "dimension" a well-defined number rather than a vague intuition: the Steinitz exchange lemma. Everything that follows in this course (rank-nullity, matrix representations, eigenspaces) is stated in terms of dimension, so this chapter's proofs are load-bearing for the rest of the block.

Have to hand: span and the subspace test (Chapter 2), and comfort manipulating finite lists of vectors and linear combinations.

1. Linear Independence

Definition. A list of vectors $v_1,\dots,v_n \in V$ is linearly independent if the only solution of $a_1v_1+\cdots+a_nv_n = 0$ (in scalars $a_i$) is $a_1=\cdots=a_n=0$. A list that is not linearly independent is linearly dependent: some nontrivial combination (not all $a_i=0$) equals $0$.

Equivalently (and this is the form used constantly in proofs): $v_1,\dots,v_n$ are linearly dependent if and only if some $v_k$ is a linear combination of the others. (Proof: if $a_1v_1+\cdots+a_nv_n=0$ with some $a_k\ne0$, solve for $v_k = -a_k^{-1}\sum_{i\ne k}a_iv_i$, using that $a_k^{-1}$ exists since $\mathbb{F}$ is a field. Conversely if $v_k=\sum_{i\ne k} c_iv_i$, then $\sum_{i\ne k}c_iv_i + (-1)v_k = 0$ is a nontrivial relation, since the coefficient of $v_k$ is $-1\ne0$.)

A single nonzero vector is always linearly independent (if $av=0$ with $v\ne0$, then $a=0$: if $a\ne0$ it would have an inverse $a^{-1}$, giving $v=a^{-1}(av)=a^{-1}\cdot0=0$, a contradiction). Any list containing the zero vector is linearly dependent: $1\cdot0=0$ is a nontrivial relation (coefficient $1\ne0$ on the zero vector).

Worked example. Are $(1,1,0),(0,1,1),(1,0,-1)$ linearly independent in $\mathbb{R}^3$? Solve $a(1,1,0)+b(0,1,1)+c(1,0,-1)=0$: componentwise, $a+c=0$, $a+b=0$, $b-c=0$. From the first, $c=-a$; from the second, $b=-a$; substituting into the third, $-a-(-a)=0$, automatically satisfied. So $(a,b,c)=(a,-a,-a)$ for any $a$ — e.g. $a=1$ gives the nontrivial relation $(1,1,0)-(0,1,1)-(1,0,-1)=0$ (check: $(1-0-1, 1-1-0, 0-1+1)=(0,0,0)$ ✓). The list is linearly dependent.

2. Basis

Definition. A list $v_1,\dots,v_n$ of vectors in $V$ is a basis of $V$ if it is linearly independent and spans $V$.

A basis is simultaneously "just enough" to span (linear independence rules out redundancy) and "enough" to span (the spanning condition). The standard basis $e_1,\dots,e_n$ of $\mathbb{F}^n$ (with $e_i$ having $1$ in position $i$ and $0$ elsewhere) is the model example: independence and spanning are both immediate from writing $(a_1,\dots,a_n)=\sum a_ie_i$ uniquely.

Proposition (uniqueness of representation). $v_1,\dots,v_n$ is a basis of $V$ if and only if every $w \in V$ can be written as $w = a_1v_1+\cdots+a_nv_n$ for a unique choice of scalars $a_1,\dots,a_n$.

Proof. ($\Rightarrow$) Spanning gives existence of some representation. For uniqueness, suppose $w=\sum a_iv_i = \sum b_iv_i$. Subtracting, $\sum (a_i-b_i)v_i = 0$; by linear independence, $a_i-b_i=0$ for every $i$, so $a_i=b_i$. ($\Leftarrow$) Existence of a representation for every $w$ is exactly the spanning condition. For independence: if $\sum a_iv_i=0$, this is a representation of $0$; but $0=\sum 0\cdot v_i$ is also a representation of $0$, so by uniqueness $a_i=0$ for all $i$. $\blacksquare$

This is the practical meaning of a basis: it turns every vector into a unique list of numbers (its coordinates), which is what makes matrix computations possible at all (Chapter 5).

3. The Steinitz Exchange Lemma

This is the technical heart of the chapter — the single lemma from which "dimension is well-defined" and "every independent list extends to a basis" both follow.

Theorem (Steinitz Exchange Lemma). Suppose $u_1,\dots,u_m$ is linearly independent in $V$ and $w_1,\dots,w_n$ spans $V$. Then $m \le n$, and (after reordering the $w_j$ if necessary) $u_1,\dots,u_m,w_{m+1},\dots,w_n$ spans $V$.

Proof (by induction on $k=0,1,\dots,m$, showing at each stage that $u_1,\dots,u_k,w_{k+1},\dots,w_n$ spans $V$, after suitable reordering of the remaining $w$'s).

Base case $k=0$: $w_1,\dots,w_n$ spans $V$ by hypothesis.

Inductive step: suppose $0\le k<m$ and that, after reordering the $w$'s, the list $u_1,\dots,u_k,w_{k+1},\dots,w_n$ spans $V$ (here $k\le n$). Since this list spans $V$, write $u_{k+1} = a_1u_1+\cdots+a_ku_k + b_{k+1}w_{k+1}+\cdots+b_nw_n.$ If every $b_j=0$ here, then $u_{k+1}$ is a linear combination of $u_1,\dots,u_k$ alone, giving a nontrivial relation among $u_1,\dots,u_{k+1}$ (coefficient $-1$ on $u_{k+1}$), contradicting linear independence of $u_1,\dots,u_m$. This also shows $k<n$ must hold at this point (if $k=n$ there would be no $w_j$ left to supply a nonzero $b_j$, forcing the contradiction immediately — this is exactly where $m\le n$ is captured: the induction cannot proceed past $k=n$, so it must terminate with $k=m\le n$). So some $b_j \ne 0$; reorder so $b_{k+1}\ne0$. Then $w_{k+1}$ can be solved for: $w_{k+1} = b_{k+1}^{-1}\big(u_{k+1} - a_1u_1-\cdots-a_ku_k - b_{k+2}w_{k+2}-\cdots-b_nw_n\big)$. Since $u_1,\dots,u_k,w_{k+1},\dots,w_n$ spans $V$ and $w_{k+1}$ is itself a linear combination of $u_1,\dots,u_{k+1},w_{k+2},\dots,w_n$, substituting shows $u_1,\dots,u_{k+1},w_{k+2},\dots,w_n$ also spans $V$. This completes the induction. $\blacksquare$

Corollary (dimension is well-defined). Any two bases of a finite-dimensional vector space $V$ have the same number of elements.

Proof. Let $v_1,\dots,v_m$ and $w_1,\dots,w_n$ both be bases. Since $v_1,\dots,v_m$ is independent and $w_1,\dots,w_n$ spans, the exchange lemma gives $m\le n$. Symmetrically, since $w_1,\dots,w_n$ is independent and $v_1,\dots,v_m$ spans, $n \le m$. Hence $m=n$. $\blacksquare$

Definition. This common number is the dimension of $V$, written $\dim V$. (A vector space with a finite spanning list is called finite-dimensional; otherwise infinite-dimensional — $\mathcal{P}(\mathbb{F})$ and $\mathcal{F}(S,\mathbb{F})$ for infinite $S$ are the standard examples of the latter, and are outside the scope of the exchange-lemma argument above, which assumes a finite spanning list exists.)

4. Existence of a Basis; Extension and Reduction

Theorem (spanning list reduces to a basis). Every finite spanning list of a nonzero vector space $V$ contains a sub-list that is a basis of $V$.

Proof sketch. If the spanning list $w_1,\dots,w_n$ is already independent, it is a basis. Otherwise some $w_k$ is a linear combination of the others (Section 1); removing it leaves a strictly shorter list that still spans $V$ (any combination using $w_k$ can be rewritten using only the others). Repeat; since the list is finite and shrinks each time, the process terminates in an independent spanning list — a basis. $\blacksquare$

Theorem (independent list extends to a basis). Every linearly independent list in a finite-dimensional $V$ extends to a basis of $V$.

Proof sketch. If $u_1,\dots,u_k$ does not already span $V$, some $v \in V$ is not in $\operatorname{span}(u_1,\dots,u_k)$; then $u_1,\dots,u_k,v$ is still independent (if a relation involved $v$ with nonzero coefficient, $v$ could be solved for in terms of the $u_i$, contradicting $v\notin\operatorname{span}$; if not, the relation reduces to one among the $u_i$ alone, contradicting their independence). Repeat; the exchange lemma bounds the length of any independent list by $\dim V$, so the process terminates in a basis. $\blacksquare$

Worked example. Extend $u_1=(1,1,0)$ to a basis of $\mathbb{R}^3$. Since $u_1\ne0$, it's independent. Is $e_2=(0,1,0) \in \operatorname{span}(u_1)$? No — $\operatorname{span}(u_1)$ is the line $\{(t,t,0)\}$, and $(0,1,0)$ is not of this form. So $u_1,e_2$ is independent. Is $e_3=(0,0,1)\in\operatorname{span}(u_1,e_2)=\{(t,t,0)+s(0,1,0)\}=\{(t,t+s,0)\}$, i.e. all vectors with third coordinate $0$? No. So $u_1,e_2,e_3$ is independent, and since $\dim\mathbb{R}^3=3$ and we have $3$ independent vectors, by the exchange lemma applied with the spanning standard basis ($m=3=n$ forces the list itself spans, else it could be extended past dimension $3$, contradiction) — $u_1,e_2,e_3$ is a basis.

5. Dimension Formulas for Subspaces

Proposition. If $U$ is a subspace of a finite-dimensional $V$, then $U$ is finite-dimensional and $\dim U \le \dim V$, with equality iff $U=V$.

Proof sketch. Any independent list in $U$ is independent in $V$, hence has length $\le \dim V$ by the exchange lemma; so $U$ has a longest independent list, which must span $U$ (else it could be extended, Section 4), giving a basis of $U$ of length $\le \dim V$. If $\dim U = \dim V$, a basis of $U$ is an independent list in $V$ of length $\dim V$; by the exchange lemma argument, it must already span $V$ (an independent list of length $\dim V$ that failed to span could be extended to a longer independent list, exceeding $\dim V$, a contradiction), so $U=V$. $\blacksquare$

Proposition (dimension of a direct sum). If $V = U_1\oplus U_2$ (both finite-dimensional), then $\dim V = \dim U_1+\dim U_2$.

Proof sketch. Let $u_1,\dots,u_p$ be a basis of $U_1$ and $w_1,\dots,w_q$ a basis of $U_2$. The combined list spans $V=U_1+U_2$ (any $v=x+y$, $x\in U_1,y\in U_2$, is a combination of the $u_i$ and $w_j$). For independence: if $\sum a_iu_i + \sum b_jw_j=0$, then $\sum a_iu_i = -\sum b_jw_j \in U_1\cap U_2=\{0\}$, so $\sum a_iu_i=0$ and $\sum b_jw_j=0$ separately; independence of each basis forces all $a_i=b_j=0$. So the combined list is a basis of $V$ of length $p+q$. $\blacksquare$

Common Exam Pitfalls

• Treating "spans" and "basis" as synonyms. A spanning list need not be independent; a basis is a spanning list that is also independent — both properties must be checked.
• Checking only spanning, or only independence, when asked to verify a basis. Both halves of the definition are required, and each needs its own argument.
• Forgetting that dimension is only well-defined because of the exchange lemma. "Two bases of the same space always have the same size" is a theorem, not an obvious fact — citing it without the lemma is incomplete.
• Assuming any $n$ vectors in an $n$-dimensional space form a basis. This is false: a dependent list of $n$ vectors is not a basis even though it has the "right" count. What is true (by the exchange lemma and the extension theorem of Section 4) is that a list of exactly $\dim V$ vectors is a basis if and only if it is independent, if and only if it spans — but one of the two properties must still be verified.
• Misapplying the exchange lemma's inequality direction. It is the independent list's length that is bounded by the spanning list's length ($m \le n$), not the other way around.
• Losing track of uniqueness of coordinates. A vector has a unique representation only relative to a fixed basis; changing the basis changes the coordinates entirely (the subject of Chapter 5).

Summary

• Linear independence: $\sum a_iv_i=0 \implies$ all $a_i=0$; equivalently, no $v_k$ is a combination of the others.
• Basis: a linearly independent spanning list; equivalently, a list giving every vector a unique coordinate representation.
• Steinitz exchange lemma: an independent list of length $m$ and a spanning list of length $n$ satisfy $m\le n$, and $u$'s can replace $w$'s one at a time while preserving spanning.
• Dimension is well-defined: any two bases of $V$ have the same length $\dim V$, a direct corollary of the exchange lemma applied both ways.
• Every finite spanning list reduces to a basis; every independent list extends to a basis (in finite dimension).
• $\dim U \le \dim V$ for a subspace $U\subseteq V$, with equality iff $U=V$; and $\dim(U_1\oplus U_2)=\dim U_1+\dim U_2$.