1.6 The Exchange Theorem and Dimension

Every finite-dimensional space has a basis, and usually a great many of them. This section proves that they all have the same length, so that the length is a property of the space and not of the basis we happened to pick. That number is the dimension. The key step is the Steinitz Exchange Theorem, the most important proof of the chapter. With it we build the everyday tools of dimension counting: size bounds, “count instead of check”, extension of independent lists to bases, and dimensions of subspaces.

1.6.1. How big is a vector space?

We would like to say that a plane is smaller than space, and that $M_2(\mathbb{R})$ and $\mathbb{R}[x]_{\le 3}$ are, in some sense, the same size. The naive measure is the number of elements. It fails at once: $\mathbb{R}^2$ , $M_2(\mathbb{R})$ , and $\mathbb{R}[x]_{\le 3}$ are all infinite sets, and counting elements cannot tell them apart.

A better measure counts how many vectors it takes to build everything, without waste, which is the length of a basis. The standard bases give $\mathbb{R}^2 : 2, \qquad M_2(\mathbb{R}) : 4 \;\; (\mathbf{E}_{11}, \mathbf{E}_{12}, \mathbf{E}_{21}, \mathbf{E}_{22}), \qquad \mathbb{R}[x]_{\le 3} : 4 \;\; (1, x, x^2, x^3).$ This matches intuition: a matrix $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ and a polynomial $a + bx + cx^2 + dx^3$ are both described by four free numbers.

But there is a gap. A space has many bases. We counted the standard basis of $\mathbb{R}^2$ ; the basis $((1, 1), (1, -1))$ also has length 2, but what guarantees that no basis of $\mathbb{R}^2$ has length 3? If some space had bases of two different lengths, “the length of a basis” would be meaningless. So before we can define anything, we need the following.

Goal. Any two bases of a finite-dimensional vector space have the same length.

A basis is independent and spanning, and the goal follows from a single inequality about the two properties separately: an independent list is never longer than a spanning list. Granting this, take two bases $\mathcal{B}$ and $\mathcal{C}$ . Since $\mathcal{B}$ is independent and $\mathcal{C}$ spans, $\mathcal{B}$ is not longer than $\mathcal{C}$ . Swapping the roles, $\mathcal{C}$ is not longer than $\mathcal{B}$ . So they have the same length. Everything rests on the inequality.

1.6.2. The Steinitz Exchange Theorem

Why should an independent list be no longer than a spanning list? In $\mathbb{R}^2$ the spanning list $(\mathbf{e}_1, \mathbf{e}_2)$ has length 2, and three vectors in the plane always satisfy a linear relation, but “the plane is two-dimensional” is what we are trying to define, so we cannot use it. The idea is instead to feed the independent vectors into the spanning list one at a time, pushing out one spanning vector each time, while keeping the list spanning. If the independent vectors outnumbered the spanning ones, we would run out of vectors to push out.

Theorem 1.6.1 (Steinitz Exchange Theorem)

Let $V$ be a vector space over $F$ . Suppose that $(u_1, \dots, u_m)$ is a linearly independent list in $V$ and that $(w_1, \dots, w_n)$ is a list that spans $V$ . Then

(a) $m \le n$ , and
(b) after renumbering $w_1, \dots, w_n$ suitably, the list $(u_1, \dots, u_m, w_{m+1}, \dots, w_n)$ spans $V$ .

In words: an independent list is at most as long as a spanning list, and the independent vectors can replace $m$ of the spanning vectors without losing the spanning property. “Renumbering” means listing the $w$ ’s in a different order; which $w$ ’s get replaced depends on the $u$ ’s.

Idea. Picture a row of $n$ slots holding $w_1, \dots, w_n$ ; the row spans $V$ . We push $u_1$ into the row and push one $w$ out, then $u_2$ , and so on, keeping the row spanning after every exchange. Here is the picture for $m = 3$ , $n = 4$ , with the $w$ ’s numbered in the order they leave.

Diagram. Labels: after k, elem w_1, elem w_2, elem w_3, elem w_4, elem u_1, elem u_2, elem u_3, elem u_k in, elem w_k out, spans V, every row spans V

Which $w$ may leave? Write the incoming $u_{k+1}$ as a combination of the current row. Any $w$ with a nonzero coefficient can be solved for, so it lies in the span of the other entries together with $u_{k+1}$ , and removing it costs nothing. Such a $w$ must exist: otherwise $u_{k+1}$ would be a combination of $u_1, \dots, u_k$ alone, which independence forbids. In particular, while $u$ ’s remain to be inserted, a $w$ remains to be removed, and that is why $m \le n$ .

Step roadmap. Induction on the number $k$ of exchanges, with the invariant

$P(k)$ : $k \le n$ , and after renumbering the $w$ ’s, the list $(u_1, \dots, u_k, w_{k+1}, \dots, w_n)$ spans $V$ .

Step 1 is the base case $k = 0$ . Step 2 writes $u_{k+1}$ in the current list. Step 3 is the Claim that some remaining $w$ has a nonzero coefficient. Step 4 exchanges that $w$ for $u_{k+1}$ and checks the span.

Proof. We prove $P(k)$ for $k = 0, 1, \dots, m$ by induction on $k$ . The case $k = m$ is the theorem.

Step 1 (base case). For $k = 0$ the list in $P(0)$ is $(w_1, \dots, w_n)$ , which spans $V$ by hypothesis, and $0 \le n$ . So $P(0)$ holds.

Step 2. Let $0 \le k < m$ and suppose $P(k)$ holds. Renumber the $w$ ’s as $P(k)$ allows, so that $L_k = (u_1, \dots, u_k, w_{k+1}, \dots, w_n)$ spans $V$ . Since $k < m$ , the vector $u_{k+1}$ exists, and $u_{k+1} \in V = \operatorname{span}(L_k)$ . Hence there are scalars $a_1, \dots, a_k, b_{k+1}, \dots, b_n \in F$ with $u_{k+1} = a_1u_1 + \dots + a_ku_k + b_{k+1}w_{k+1} + \dots + b_nw_n. \tag{$\ast$}$ (If $k = n$ , the list $L_k$ contains no $w$ ’s and the second group of terms is empty.)

Step 3.

Claim. We have $k + 1 \le n$ , and $b_j \ne 0$ for some $j$ with $k + 1 \le j \le n$ .

Proof. Suppose not. Then either $k = n$ , so that there are no $b$ ’s at all, or $k < n$ and $b_{k+1} = \dots = b_n = 0$ . In both cases $(\ast)$ reads $u_{k+1} = a_1u_1 + \dots + a_ku_k$ . Therefore $a_1u_1 + \dots + a_ku_k + (-1)u_{k+1} + 0u_{k+2} + \dots + 0u_m = 0$ is a linear relation among $u_1, \dots, u_m$ in which the coefficient of $u_{k+1}$ is $-1 \ne 0$ . This contradicts the linear independence of $(u_1, \dots, u_m)$ . Hence there is at least one $w$ in $L_k$ , so $k + 1 \le n$ , and some $b_j$ with $j \ge k + 1$ is nonzero.

Step 4. Renumber $w_{k+1}, \dots, w_n$ among themselves so that $b_{k+1} \ne 0$ . This only changes the order of entries of $L_k$ , so $L_k$ still spans $V$ (the span of a list does not depend on the order of its entries), and $(\ast)$ still holds with the coefficients renumbered in the same way. Put $L_{k+1} = (u_1, \dots, u_{k+1}, w_{k+2}, \dots, w_n).$ Since $b_{k+1} \ne 0$ , the scalar $b_{k+1}^{-1}$ exists, and solving $(\ast)$ for $w_{k+1}$ gives $w_{k+1} = b_{k+1}^{-1}\big( u_{k+1} - a_1u_1 - \dots - a_ku_k - b_{k+2}w_{k+2} - \dots - b_nw_n \big).$ The right side is a combination of the entries of $L_{k+1}$ , so $w_{k+1} \in \operatorname{span}(L_{k+1})$ . By Theorem 1.3.5, inserting $w_{k+1}$ into $L_{k+1}$ does not change the span: $\operatorname{span}(L_{k+1}) = \operatorname{span}(u_1, \dots, u_{k+1}, w_{k+1}, w_{k+2}, \dots, w_n).$ The list on the right contains every entry of $L_k$ , so its span is a subspace containing all entries of $L_k$ , and hence contains $\operatorname{span}(L_k) = V$ by Theorem 1.3.1. Therefore $\operatorname{span}(L_{k+1}) = V$ . Together with $k + 1 \le n$ from the Claim, this is $P(k + 1)$ .

By induction, $P(m)$ holds: $m \le n$ , and after renumbering the $w$ ’s, $(u_1, \dots, u_m, w_{m+1}, \dots, w_n)$ spans $V$ . This proves the theorem.

Part (a) is the inequality our goal needed. Part (b), the exchange itself, is a bonus that we will spend later in this section, to extend independent lists to bases.

Warning. The $\mathbf{w}$ that leaves must have a nonzero coefficient; an arbitrary $\mathbf{w}$ will not do. In $\mathbb{R}^2$ , take the spanning list $(\mathbf{w}_1, \mathbf{w}_2) = ((1, 0), (0, 1))$ and the independent vector $\mathbf{u}_1 = (1, 0) = 1\mathbf{w}_1 + 0\mathbf{w}_2$ . Exchanging $\mathbf{u}_1$ for $\mathbf{w}_1$ gives $((1, 0), (0, 1))$ , which spans. Exchanging $\mathbf{u}_1$ for $\mathbf{w}_2$ , whose coefficient is $0$ , gives $((1, 0), (1, 0))$ , which does not reach $(0, 1)$ .

The theorem already settles questions that would otherwise need a computation.

Quick check. Can the four polynomials $1 + x$ , $x + x^2$ , $x^2 + 1$ , $1 + x + x^2$ be linearly independent in $\mathbb{R}[x]_{\le 2}$ ?

Solution. No. The list $(1, x, x^2)$ spans $\mathbb{R}[x]_{\le 2}$ and has length $3$ , so by Theorem 1.6.1 every independent list there has length at most $3 < 4$ . Indeed $(1 + x) + (x + x^2) + (x^2 + 1) - 2(1 + x + x^2) = 0$ .

1.6.3. Dimension

The goal of the section is now one line away.

Theorem 1.6.2 (Basis Theorem)

Let $V$ be a finite-dimensional vector space. Then $V$ has a basis, and any two bases of $V$ have the same length.

Proof. By Corollary 1.5.5, $V$ has a basis. Let $(v_1, \dots, v_n)$ and $(w_1, \dots, w_m)$ be bases of $V$ . The first is linearly independent and the second spans $V$ , so $n \le m$ by Theorem 1.6.1. Swapping the roles of the two bases gives $m \le n$ . Hence $m = n$ .

We started from a question: how big is a vector space? The Basis Theorem says that one number, the length of a basis, answers it without depending on any choice. So we give that number a name.

The dimension of a space is the number of vectors in any basis: how many independent directions the space has.

Definition 1.6.1 (Dimension)

Let $V$ be a finite-dimensional vector space over $F$ . The dimension of $V$ over $F$ , written $\dim_F V$ or simply $\dim V$ , is the length of any basis of $V$ .

In words: pick a basis of $V$ , any basis at all, and count its vectors. The dimension is defined only for finite-dimensional spaces (Definition 1.3.4); a space spanned by no finite list is infinite-dimensional, and we do not assign it a number here. The subscript $F$ records the field of scalars, which, as we will see, matters.

Well-definedness. Two things could go wrong with “the length of any basis”: there might be no basis to count, or different bases might give different counts. The first is ruled out by Corollary 1.5.5 and the second by Theorem 1.6.2. That is exactly what the word any in the definition needs.

Example (Dimensions of the Running Examples)

Find the dimension of each space.

(a) $F^n$ , $M_{m \times n}(F)$ , and $F[x]_{\le n}$ .
(b) The zero space $\{0\}$ .
(c) $\mathbb{C}$ over $\mathbb{C}$ , and $\mathbb{C}$ over $\mathbb{R}$ .
(d) $U = \{ \mathbf{A} \in M_2(\mathbb{R}) : \mathbf{A}^{\top} = \mathbf{A} \}$ , the symmetric $2 \times 2$ real matrices.
(e) $\mathbb{Q}(\sqrt 2) = \{ a + b\sqrt 2 : a, b \in \mathbb{Q} \}$ over $\mathbb{Q}$ (Example ( $\mathbb{Q}(\sqrt{2})$ over $\mathbb{Q}$ )).

Solution. In each case we exhibit one basis and count it.

(a) The standard bases of Example (Standard Bases) have lengths $n$ , $mn$ , and $n + 1$ . So $\dim F^n = n$ , $\dim M_{m \times n}(F) = mn$ , and $\dim F[x]_{\le n} = n + 1$ .
(b) The empty list is a basis of $\{0\}$ (Example (Three More Bases)), so $\dim \{0\} = 0$ .
(c) Over $\mathbb{C}$ , the list $(1)$ is a basis of $\mathbb{C}$ : every $z$ equals $z \cdot 1$ , and $z \cdot 1 = 0$ forces $z = 0$ . So $\dim_\mathbb{C} \mathbb{C} = 1$ . Over $\mathbb{R}$ , the list $(1, i)$ is a basis (Example (Three More Bases)), so $\dim_\mathbb{R} \mathbb{C} = 2$ .
(d) A symmetric matrix has the form $\begin{pmatrix} a & b \\ b & d \end{pmatrix} = a\mathbf{E}_{11} + b(\mathbf{E}_{12} + \mathbf{E}_{21}) + d\mathbf{E}_{22}$ , and this combination is the zero matrix only when $a = b = d = 0$ . So $(\mathbf{E}_{11}, \mathbf{E}_{12} + \mathbf{E}_{21}, \mathbf{E}_{22})$ is a basis of $U$ , as in Exercise (B3: Symmetric Matrices), and $\dim U = 3$ .
(e) Every element is $a \cdot 1 + b\sqrt 2$ with $a, b \in \mathbb{Q}$ , so $(1, \sqrt 2)$ spans. Let $a + b\sqrt 2 = 0$ with $a, b \in \mathbb{Q}$ . If $b \ne 0$ , then $\sqrt 2 = -a/b \in \mathbb{Q}$ , contradicting Theorem 0.2.3. So $b = 0$ , and then $a = 0$ . Hence $(1, \sqrt 2)$ is a basis, and $\dim_\mathbb{Q} \mathbb{Q}(\sqrt 2) = 2$ .

The zero space in (b) is the degenerate case: it has dimension $0$ because its basis is empty, not because it has no elements. It has one element, $0$ .

Nonexample by minimal change. Remove the degree bound from $F[x]_{\le n}$ . The space $F[x]$ is not spanned by any finite list (Theorem 1.3.3), so it has no finite basis and no dimension in the sense of Definition 1.6.1. The hypothesis “finite-dimensional” in the Basis Theorem is exactly what fails.

Why this definition. Why a basis, and not some other list? Spanning lists can be made as long as we like by repeating vectors, and independent lists can be made as short as we like by deleting vectors, so neither length alone is an invariant. A basis sits exactly where the two meet: it is the longest possible independent list and the shortest possible spanning list, as we prove next. And why not count elements? Over $\mathbb{R}$ every nonzero space is infinite, so the count says nothing. Over a finite field the count does carry information, but it is determined by the dimension; see Exercise (C3: Counting Elements over a Finite Field).

Warning. The dimension of $F[x]_{\le n}$ is $n + 1$ , not $n$ . The basis $(1, x, \dots, x^n)$ has one vector for each exponent $0, 1, \dots, n$ , and the constant $1$ is easy to forget. For instance $\dim \mathbb{R}[x]_{\le 2} = 3$ .

Warning. Dimension depends on the field. The set $\mathbb{C}$ has dimension $1$ over $\mathbb{C}$ but dimension $2$ over $\mathbb{R}$ , because over $\mathbb{R}$ the scalar $i$ is no longer available and $i$ must be counted as a separate basis vector. When more than one field is in sight, write $\dim_F$ .

Quick check. What are $\dim M_{2 \times 3}(F)$ and $\dim F[x]_{\le 5}$ ? Which of them equals $\dim F^6$ ?

Solution. $\dim M_{2 \times 3}(F) = 2 \cdot 3 = 6$ and $\dim F[x]_{\le 5} = 5 + 1 = 6$ . Both equal $\dim F^6 = 6$ .

1.6.4. Size bounds

The first payoff turns the Exchange Theorem into statements about the number $\dim V$ .

Theorem 1.6.3 (Size Bounds)

Let $V$ be a vector space over $F$ with $\dim V = n$ .

(a) Every linearly independent list in $V$ has length at most $n$ . Hence every list in $V$ of length greater than $n$ is linearly dependent.
(b) Every list that spans $V$ has length at least $n$ . Hence no list of length less than $n$ spans $V$ .

Proof. Let $\mathcal{B}$ be a basis of $V$ ; it has length $n$ .

(a) Let $\mathcal{L}$ be an independent list of length $\ell$ . Since $\mathcal{B}$ spans $V$ , Theorem 1.6.1 gives $\ell \le n$ . The second sentence is the contrapositive.
(b) Let $\mathcal{L}$ be a list of length $\ell$ that spans $V$ . Since $\mathcal{B}$ is independent, Theorem 1.6.1 gives $n \le \ell$ . The second sentence is the contrapositive.

So in a space of dimension $n$ , $\text{length of an independent list} \;\le\; n \;\le\; \text{length of a spanning list}.$ This settles many questions with no computation. The four vectors $(1, 2, 3)$ , $(4, 5, 6)$ , $(7, 8, 9)$ , $(1, 0, 0)$ in $\mathbb{R}^3$ are dependent, because $4 > 3$ . Three matrices never span $M_2(F)$ , because $3 < 4$ .

1.6.5. Count instead of check

To show a list is a basis we normally check two things, independence and spanning. When the length of the list equals the dimension, one check is enough. This is one of the most used facts in the book.

Theorem 1.6.4 (Count Instead of Check)

Let $V$ be a vector space with $\dim V = n$ , and let $\mathcal{L} = (v_1, \dots, v_n)$ be a list in $V$ of length exactly $n$ .

(a) If $\mathcal{L}$ is linearly independent, then $\mathcal{L}$ is a basis of $V$ .
(b) If $\mathcal{L}$ spans $V$ , then $\mathcal{L}$ is a basis of $V$ .

Idea. For (a), the exchange part of Theorem 1.6.1 does the work: we can push all $n$ vectors of $\mathcal{L}$ into a basis of length $n$ , and then no old vectors are left, so $\mathcal{L}$ alone spans. For (b), sift $\mathcal{L}$ : the result is a basis, so it has length $n$ , so nothing was discarded.

Proof.

(a) Let $(w_1, \dots, w_n)$ be a basis of $V$ ; in particular it spans $V$ . Since $\mathcal{L}$ is independent of length $n$ , Theorem 1.6.1 (b) with $m = n$ says that, after renumbering the $w$ ’s, the list $(v_1, \dots, v_n, w_{n+1}, \dots, w_n)$ spans $V$ . This list contains no $w$ ’s: it is $\mathcal{L}$ . So $\mathcal{L}$ is independent and spans $V$ , and it is a basis.
(b) By Theorem 1.5.4, $\mathcal{L}$ contains a sub-list that is a basis of $V$ . By Theorem 1.6.2, that sub-list has length $\dim V = n$ . The only sub-list of length $n$ of a list of length $n$ is the list itself. Hence $\mathcal{L}$ is a basis.

The theorem lets us choose the easier check, and independence is almost always easier: it is a single equation equal to $0$ , while spanning asks us to solve for an arbitrary vector.

Example (A Basis by Counting)

Show that $(1, \; 1 + x, \; (1 + x)^2)$ is a basis of $\mathbb{R}[x]_{\le 2}$ .

Solution. By Example (Dimensions of the Running Examples), $\dim \mathbb{R}[x]_{\le 2} = 3$ , and the list has length $3$ . So by Theorem 1.6.4 (a) it suffices to check independence. Let $a \cdot 1 + b(1 + x) + c(1 + x)^2 = 0.$ Expanding, the left side is $(a + b + c) + (b + 2c)x + cx^2$ . Comparing coefficients with the zero polynomial: $c = 0$ ; then $b + 2c = 0$ gives $b = 0$ ; then $a + b + c = 0$ gives $a = 0$ . Hence the list is independent, with $3 = \dim \mathbb{R}[x]_{\le 2}$ elements, and therefore it is a basis.

We never had to show that every polynomial of degree at most 2 is a combination of $1, 1 + x, (1 + x)^2$ . The dimension count did it for us.

1.6.6. Extending to a basis

Sifting finds a basis inside a spanning list. The opposite direction starts from an independent list and grows it into a basis. This is the tool behind every dimension formula later in the book: start from a basis of the smallest space, then extend.

Theorem 1.6.5 (Basis Extension Theorem)

Let $V$ be a finite-dimensional vector space with $\dim V = n$ , and let $(u_1, \dots, u_m)$ be a linearly independent list in $V$ . Then $m \le n$ , and there are vectors $v_{m+1}, \dots, v_n \in V$ such that $(u_1, \dots, u_m, v_{m+1}, \dots, v_n)$ is a basis of $V$ . Moreover, the $v$ ’s can be chosen from any given basis of $V$ .

Proof. Let $(w_1, \dots, w_n)$ be a basis of $V$ . It spans $V$ , so by Theorem 1.6.1, $m \le n$ , and after renumbering the $w$ ’s the list $(u_1, \dots, u_m, w_{m+1}, \dots, w_n)$ spans $V$ . This list has length $m + (n - m) = n = \dim V$ , so it is a basis by Theorem 1.6.4 (b). Take $v_j = w_j$ for $m < j \le n$ .

Alternatively, sift the list $(u_1, \dots, u_m, w_1, \dots, w_n)$ . It spans $V$ , and sifting keeps every $u_k$ : the sub-list $(u_1, \dots, u_k)$ is independent (Exercise (B3: Sub-Lists)), so $u_k \notin \operatorname{span}(u_1, \dots, u_{k-1})$ by Lemma 1.5.3. Sifting has the advantage of telling us which $w$ ’s to add.

Example (Extending an Independent List)

Extend the list $((1, 1, 0), (0, 1, 1))$ to a basis of $\mathbb{R}^3$ .

Solution. The list is independent: $a(1, 1, 0) + b(0, 1, 1) = (a, a + b, b) = \mathbf{0}$ forces $a = b = 0$ . By Theorem 1.6.5, one vector from the standard basis will do, so we try $\mathbf{e}_1$ . Let $a(1, 1, 0) + b(0, 1, 1) + c(1, 0, 0) = (a + c, \; a + b, \; b) = (0, 0, 0).$ Then $b = 0$ , so $a = 0$ from the second entry, so $c = 0$ from the first. Hence the extended list is independent, with $3 = \dim \mathbb{R}^3$ elements, and therefore a basis by Theorem 1.6.4 (a).

The extension is far from unique. The same computation with $\mathbf{e}_2$ gives $(a, a + b + c, b) = \mathbf{0}$ , and with $\mathbf{e}_3$ gives $(a, a + b, b + c) = \mathbf{0}$ ; both force $a = b = c = 0$ . So any one of $\mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3$ completes this list to a basis.

1.6.7. Largest independent lists and smallest spanning lists

We claimed that a basis is where independence and spanning meet. Here is the precise statement. It does not need finite dimension, and it is the form of “basis” that generalizes to infinite-dimensional spaces later in this chapter.

Call an independent list $(v_1, \dots, v_n)$ in $V$ maximal independent if for every $v \in V$ the longer list $(v_1, \dots, v_n, v)$ is dependent. Call a spanning list minimal spanning if deleting any one of its entries gives a list that does not span $V$ .

Theorem 1.6.6 (Maximal Independent and Minimal Spanning Lists)

Let $V$ be a vector space and $\mathcal{L} = (v_1, \dots, v_n)$ a list in $V$ .

(a) $\mathcal{L}$ is a basis of $V$ if and only if $\mathcal{L}$ is maximal independent.
(b) $\mathcal{L}$ is a basis of $V$ if and only if $\mathcal{L}$ is minimal spanning.

Proof.

(a) $(\Rightarrow)$ Let $\mathcal{L}$ be a basis and $v \in V$ . Then $v \in \operatorname{span}(\mathcal{L}) = V$ , so $(v_1, \dots, v_n, v)$ is dependent by Lemma 1.5.3. Hence $\mathcal{L}$ is maximal independent.
$(\Leftarrow)$ Let $\mathcal{L}$ be maximal independent and $v \in V$ . The list $(v_1, \dots, v_n, v)$ is dependent while $\mathcal{L}$ is independent, so $v \in \operatorname{span}(\mathcal{L})$ by Lemma 1.5.3. Hence $\mathcal{L}$ spans $V$ , and $\mathcal{L}$ is a basis.
(b) $(\Rightarrow)$ Let $\mathcal{L}$ be a basis, and suppose that deleting $v_j$ gives a list that still spans $V$ . Then $v_j = \sum_{i \ne j} c_iv_i$ for some scalars, so $\sum_{i \ne j} c_iv_i + (-1)v_j = 0$ , a linear relation with the coefficient $-1 \ne 0$ . This contradicts independence. Hence $\mathcal{L}$ is minimal spanning.

$(\Leftarrow)$ Let $\mathcal{L}$ be minimal spanning. By Theorem 1.5.4, some sub-list $S$ of $\mathcal{L}$ is a basis of $V$ . Suppose $S \ne \mathcal{L}$ . Then $S$ omits some entry $v_j$ , so every entry of $S$ is an entry of the list $\mathcal{L}'$ obtained by deleting $v_j$ . By Theorem 1.3.1, $\operatorname{span}(\mathcal{L}')$ contains $\operatorname{span}(S) = V$ , so $\mathcal{L}'$ spans $V$ , contradicting minimality. Hence $S = \mathcal{L}$ , and $\mathcal{L}$ is a basis.

“Maximal” means “cannot be enlarged”, which is different from “longest possible”. In a finite-dimensional space the two agree: by Theorem 1.6.3 a longest independent list has length $\dim V$ , and by Theorem 1.6.4 every independent list of that length is a basis.

1.6.8. Dimensions of subspaces

A subspace should be no bigger than the space containing it. Proving this needs care, because of a tempting circular argument.

Theorem 1.6.7 (Dimension of a Subspace)

Let $V$ be a finite-dimensional vector space and $U$ a subspace of $V$ . Then $U$ is finite-dimensional, and $\dim U \le \dim V$ .

Idea. The tempting proof is: “take a basis of $U$ ; it is independent in $V$ , so its length is at most $\dim V$ ”. But we do not yet know that $U$ has a basis. Corollary 1.5.5 needs a finite spanning list of $U$ , and that is exactly what we are trying to prove. So we build from below instead. Independent lists inside $U$ are independent in $V$ , so their lengths are bounded by $\dim V$ . Take one of the largest possible length. If it did not span $U$ , we could append a vector of $U$ outside its span and get a longer one.

Proof. Let $n = \dim V$ . Independence of a list depends only on its vectors and the operations of $V$ , which $U$ shares, so every independent list in $U$ is an independent list in $V$ , and has length at most $n$ by Theorem 1.6.3. The empty list is independent in $U$ . Hence the set of lengths of independent lists in $U$ is a nonempty set of integers in $\{0, 1, \dots, n\}$ , and it has a largest element $k \le n$ . Choose an independent list $(u_1, \dots, u_k)$ in $U$ of this length.

We claim $\operatorname{span}(u_1, \dots, u_k) = U$ . Since $U$ is a subspace containing every $u_i$ , Theorem 1.3.1 gives $\operatorname{span}(u_1, \dots, u_k) \subseteq U$ . Conversely, let $u \in U$ , and suppose $u \notin \operatorname{span}(u_1, \dots, u_k)$ . By Lemma 1.5.3, $(u_1, \dots, u_k, u)$ is an independent list in $U$ of length $k + 1$ , contradicting the maximality of $k$ . Hence $u \in \operatorname{span}(u_1, \dots, u_k)$ .

Therefore $(u_1, \dots, u_k)$ spans $U$ , so $U$ is finite-dimensional (Definition 1.3.4), and the list is a basis of $U$ . Hence $\dim U = k \le n = \dim V$ .

When the dimensions are equal, there is no room left.

Theorem 1.6.8 (Equal Dimension Forces Equality)

Let $V$ be a finite-dimensional vector space and $U$ a subspace of $V$ . If $\dim U = \dim V$ , then $U = V$ .

Proof. Let $n = \dim U = \dim V$ ; $U$ is finite-dimensional by Theorem 1.6.7. Let $(u_1, \dots, u_n)$ be a basis of $U$ (Corollary 1.5.5). It is an independent list in $V$ of length $n = \dim V$ , so it is a basis of $V$ by Theorem 1.6.4 (a). Hence $V = \operatorname{span}(u_1, \dots, u_n) \subseteq U$ , where the inclusion is Theorem 1.3.1 (3) applied to the subspace $U$ . Since also $U \subseteq V$ , we get $U = V$ .

This is the dimension version of “count instead of check”: to prove two subspaces are equal, prove one inclusion and compare dimensions. It is usually much less work than proving both inclusions.

Quick check. Let $U$ be a subspace of $\mathbb{R}[x]_{\le 2}$ that contains $1$ , $1 + x$ , and $(1 + x)^2$ . Must $U = \mathbb{R}[x]_{\le 2}$ ?

Solution. Yes. By Example (A Basis by Counting), $(1, 1 + x, (1 + x)^2)$ is independent, and it lies in $U$ , so $\dim U \ge 3$ by Theorem 1.6.3 applied in $U$ (which is finite-dimensional by Theorem 1.6.7). Also $\dim U \le \dim \mathbb{R}[x]_{\le 2} = 3$ . So $\dim U = 3$ , and Theorem 1.6.8 gives $U = \mathbb{R}[x]_{\le 2}$ .

Warning. Both hypotheses of Theorem 1.6.8 matter. Containment is needed: the $xy$ -plane and the $xz$ -plane in $\mathbb{R}^3$ both have dimension 2, but neither contains the other, and they are different. Without finite dimension it fails too. In $F[x]$ , the subspace $U$ of polynomials with constant coefficient $0$ has the basis-like list $x, x^2, x^3, \dots$ , which matches $1, x, x^2, \dots$ one for one; yet $1 \notin U$ . Later in this chapter we make this precise for infinite-dimensional spaces.

1.6.9. Exercises

A. Check your understanding

Exercise (A1)

(a) State the Steinitz Exchange Theorem.
(b) True or false: $\dim \mathbb{R}[x]_{\le 3} = 3$ . Justify your answer.
(c) True or false: in a vector space of dimension $3$ , every spanning list of length $3$ is a basis. Justify your answer.
(d) True or false: $M_2(\mathbb{R})$ contains a linearly independent list of length $5$ . Justify your answer.
(e) True or false: if $U$ and $W$ are subspaces of $\mathbb{R}^4$ with $\dim U = \dim W = 2$ , then $U = W$ . Justify your answer.
(f) What are $\dim_\mathbb{C} \mathbb{C}^2$ and $\dim_\mathbb{R} \mathbb{C}^2$ ?

Solution.

(a) See Theorem 1.6.1: if $(u_1, \dots, u_m)$ is independent and $(w_1, \dots, w_n)$ spans $V$ , then $m \le n$ , and after renumbering the $w$ ’s, $(u_1, \dots, u_m, w_{m+1}, \dots, w_n)$ spans $V$ .
(b) False. The basis $(1, x, x^2, x^3)$ has length $4$ , so $\dim \mathbb{R}[x]_{\le 3} = 4$ .
(c) True, by Theorem 1.6.4 (b).
(d) False. $\dim M_2(\mathbb{R}) = 4$ , and by Theorem 1.6.3 (a) every list of length $5 > 4$ is dependent.
(e) False. The subspaces $\operatorname{span}(\mathbf{e}_1, \mathbf{e}_2)$ and $\operatorname{span}(\mathbf{e}_3, \mathbf{e}_4)$ both have dimension $2$ , but $\mathbf{e}_1$ lies in the first and not in the second. Theorem 1.6.8 needs one subspace to be contained in the other.
(f) $\dim_\mathbb{C} \mathbb{C}^2 = 2$ , with basis $(\mathbf{e}_1, \mathbf{e}_2)$ . Over $\mathbb{R}$ , the list $(\mathbf{e}_1, i\mathbf{e}_1, \mathbf{e}_2, i\mathbf{e}_2)$ is a basis: every $(a + bi, c + di)$ with $a, b, c, d \in \mathbb{R}$ equals $a\mathbf{e}_1 + b(i\mathbf{e}_1) + c\mathbf{e}_2 + d(i\mathbf{e}_2)$ , and this is $\mathbf{0}$ only if $a + bi = 0$ and $c + di = 0$ , that is, $a = b = c = d = 0$ . So $\dim_\mathbb{R} \mathbb{C}^2 = 4$ .

B. Practice

Exercise (B1: Dimension and a Basis of a Subspace)

Find a basis and the dimension of each subspace.

(a) $U_1 = \{ (x_1, x_2, x_3, x_4) \in \mathbb{R}^4 : x_1 + x_2 = 0 \text{ and } x_3 - x_4 = 0 \}$ .
(b) $U_2 = \{ \mathbf{A} \in M_3(\mathbb{R}) : \operatorname{tr} \mathbf{A} = 0 \}$ .
(c) $U_3 = \{ p \in \mathbb{R}[x]_{\le 3} : p(1) = p(-1) = 0 \}$ .

Solution.

(a) A vector lies in $U_1$ exactly when $x_2 = -x_1$ and $x_3 = x_4$ , that is, when it equals $(x_1, -x_1, x_4, x_4) = x_1(1, -1, 0, 0) + x_4(0, 0, 1, 1).$ So $((1, -1, 0, 0), (0, 0, 1, 1))$ spans $U_1$ . It is independent: $a(1, -1, 0, 0) + b(0, 0, 1, 1) = (a, -a, b, b) = \mathbf{0}$ forces $a = b = 0$ . Hence it is a basis, and $\dim U_1 = 2$ .
(b) Write $\mathbf{A} = (a_{ij})$ . The condition $a_{11} + a_{22} + a_{33} = 0$ says $a_{33} = -a_{11} - a_{22}$ , so $\mathbf{A} = \sum_{i \ne j} a_{ij}\mathbf{E}_{ij} + a_{11}(\mathbf{E}_{11} - \mathbf{E}_{33}) + a_{22}(\mathbf{E}_{22} - \mathbf{E}_{33}).$ All eight matrices on the right have trace $0$ , so the list of the six $\mathbf{E}_{ij}$ with $i \ne j$ , followed by $\mathbf{E}_{11} - \mathbf{E}_{33}$ and $\mathbf{E}_{22} - \mathbf{E}_{33}$ , spans $U_2$ . For independence, let $\sum_{i \ne j} c_{ij}\mathbf{E}_{ij} + d_1(\mathbf{E}_{11} - \mathbf{E}_{33}) + d_2(\mathbf{E}_{22} - \mathbf{E}_{33}) = \mathbf{O}$ . The entry $(i, j)$ with $i \ne j$ of the left side is $c_{ij}$ , the entry $(1, 1)$ is $d_1$ , and the entry $(2, 2)$ is $d_2$ ; all must be $0$ . Hence the list is a basis, and $\dim U_2 = 8$ .
(c) Let $p = a_0 + a_1x + a_2x^2 + a_3x^3$ . Then $p(1) = a_0 + a_1 + a_2 + a_3$ and $p(-1) = a_0 - a_1 + a_2 - a_3$ . Adding and subtracting, $p \in U_3$ exactly when $a_0 + a_2 = 0$ and $a_1 + a_3 = 0$ . Hence $p \in U_3$ exactly when $p = -a_2 - a_3x + a_2x^2 + a_3x^3 = a_2(x^2 - 1) + a_3(x^3 - x).$ So $(x^2 - 1, x^3 - x)$ spans $U_3$ . It is independent: $a(x^2 - 1) + b(x^3 - x) = 0$ has $x^3$ -coefficient $b$ and $x^2$ -coefficient $a$ , so $a = b = 0$ . Hence it is a basis, and $\dim U_3 = 2$ .

Exercise (B2: Extending to a Basis of

\mathbb{R}^4

)

Show that $((1, 1, 0, 0), (0, 1, 1, 0))$ is linearly independent, and extend it to a basis of $\mathbb{R}^4$ using vectors from the standard basis.

Solution. Let $\mathbf{u}_1 = (1, 1, 0, 0)$ and $\mathbf{u}_2 = (0, 1, 1, 0)$ . If $a\mathbf{u}_1 + b\mathbf{u}_2 = (a, a + b, b, 0) = \mathbf{0}$ , then $a = b = 0$ , so the list is independent. By Theorem 1.6.5, two standard basis vectors complete it; we sift $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{e}_1, \mathbf{e}_2, \mathbf{e}_3, \mathbf{e}_4)$ to find which.

$\mathbf{u}_1 \ne \mathbf{0}$ : keep. $\mathbf{u}_2 \notin \operatorname{span}(\mathbf{u}_1)$ , since a multiple $(a, a, 0, 0)$ of $\mathbf{u}_1$ has third entry $0$ : keep.
$\mathbf{e}_1$ : if $(a, a + b, b, 0) = (1, 0, 0, 0)$ , then $a = 1$ and $b = 0$ , but then $a + b = 1 \ne 0$ . So $\mathbf{e}_1 \notin \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2)$ : keep.
$\mathbf{e}_2 = \mathbf{u}_1 - \mathbf{e}_1$ : discard.
$\mathbf{e}_3 = -\mathbf{u}_1 + \mathbf{u}_2 + \mathbf{e}_1$ , since $-(1, 1, 0, 0) + (0, 1, 1, 0) + (1, 0, 0, 0) = (0, 0, 1, 0)$ : discard.
$\mathbf{e}_4$ : every combination of $\mathbf{u}_1, \mathbf{u}_2, \mathbf{e}_1$ has fourth entry $0$ : keep.

The sifted list $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{e}_1, \mathbf{e}_4)$ is independent by Theorem 1.5.4. It has $4 = \dim \mathbb{R}^4$ entries, so it is a basis of $\mathbb{R}^4$ by Theorem 1.6.4 (a).

Exercise (B3: Count Instead of Check)

Show that $(1, \; x - 1, \; (x - 1)^2)$ is a basis of $\mathbb{R}[x]_{\le 2}$ . Hence find the coordinate vector of $x^2$ with respect to this basis.

Solution. Let $a + b(x - 1) + c(x - 1)^2 = 0$ . Expanding, $(a - b + c) + (b - 2c)x + cx^2 = 0$ . Comparing coefficients, $c = 0$ , then $b = 2c = 0$ , then $a = b - c = 0$ . So the list is independent, with $3 = \dim \mathbb{R}[x]_{\le 2}$ elements, and it is a basis by Theorem 1.6.4 (a).

Writing $x = (x - 1) + 1$ , $x^2 = \big((x - 1) + 1\big)^2 = 1 + 2(x - 1) + (x - 1)^2.$ Hence the coordinate vector of $x^2$ is $(1, 2, 1)$ .

C. Going deeper

Exercise (C1: Symmetric and Skew-Symmetric Matrices)

Let $n \ge 1$ . For a field $F$ , let $U_+$ and $U_-$ be the subspaces of symmetric and of skew-symmetric matrices in $M_n(F)$ (Definition 0.9.11): $U_+ = \{ \mathbf{A} : \mathbf{A}^{\top} = \mathbf{A} \}$ and $U_- = \{ \mathbf{A} : \mathbf{A}^{\top} = -\mathbf{A} \}$ .

(a) For $F = \mathbb{R}$ , prove that $\dim U_+ = \frac{n(n + 1)}{2}$ .
(b) For $F = \mathbb{R}$ , prove that $\dim U_- = \frac{n(n - 1)}{2}$ .
(c) For $F = \mathbb{F}_2$ , show that $U_- = U_+$ , and find its dimension. Which step of (b) fails?

Solution.

(a) Consider the list $\mathcal{S}$ consisting of $\mathbf{E}_{ii}$ for $1 \le i \le n$ and $\mathbf{E}_{ij} + \mathbf{E}_{ji}$ for $1 \le i < j \le n$ . Each is symmetric. If $\mathbf{A} = (a_{ij})$ is symmetric, then $a_{ji} = a_{ij}$ , so $\mathbf{A} = \sum_{i} a_{ii}\mathbf{E}_{ii} + \sum_{i < j} a_{ij}(\mathbf{E}_{ij} + \mathbf{E}_{ji}),$ because both sides have $a_{ij}$ in entry $(i, j)$ and $a_{ij} = a_{ji}$ in entry $(j, i)$ . So $\mathcal{S}$ spans $U_+$ . If $\sum_i c_{ii}\mathbf{E}_{ii} + \sum_{i < j} c_{ij}(\mathbf{E}_{ij} + \mathbf{E}_{ji}) = \mathbf{O}$ , then for $i \le j$ the entry $(i, j)$ of the left side is $c_{ij}$ , so every coefficient is $0$ . Hence $\mathcal{S}$ is a basis, of length $n + \frac{n(n - 1)}{2} = \frac{n(n + 1)}{2}$ .
(b) If $\mathbf{A}^{\top} = -\mathbf{A}$ , then comparing diagonal entries gives $a_{ii} = -a_{ii}$ , so $2a_{ii} = 0$ , and $a_{ii} = 0$ because $2 \ne 0$ in $\mathbb{R}$ . Off the diagonal, $a_{ji} = -a_{ij}$ . Hence $\mathbf{A} = \sum_{i < j} a_{ij}(\mathbf{E}_{ij} - \mathbf{E}_{ji}).$ Each $\mathbf{E}_{ij} - \mathbf{E}_{ji}$ is skew-symmetric, so these matrices span $U_-$ , and as in (a) the entry $(i, j)$ with $i < j$ of a combination is its coefficient, so they are independent. There are $\frac{n(n - 1)}{2}$ pairs $i < j$ , so $\dim U_- = \frac{n(n - 1)}{2}$ .
(c) In $\mathbb{F}_2$ , $-1 = 1$ , so $-\mathbf{A} = \mathbf{A}$ for every matrix $\mathbf{A}$ , and the conditions $\mathbf{A}^{\top} = -\mathbf{A}$ and $\mathbf{A}^{\top} = \mathbf{A}$ coincide. Hence $U_- = U_+$ over $\mathbb{F}_2$ , which has dimension $\frac{n(n + 1)}{2}$ by the argument of (a), which works over any field. The step of (b) that fails is “ $2a_{ii} = 0$ implies $a_{ii} = 0$ ”, which divides by $2 = 0$ . For example, $\mathbf{I}_n \in U_-$ over $\mathbb{F}_2$ , although its diagonal entries are not $0$ .

Exercise (C2: A complex space viewed over the reals)

Let $V$ be a vector space over $\mathbb{C}$ with $\dim_\mathbb{C} V = n$ . Restricting the scalars to real numbers makes $V$ a vector space over $\mathbb{R}$ . Prove that $\dim_\mathbb{R} V = 2n$ .

Hint: start from a basis $(v_1, \dots, v_n)$ over $\mathbb{C}$ , and consider the vectors $iv_k$ .

Solution. Let $(v_1, \dots, v_n)$ be a basis of $V$ over $\mathbb{C}$ . We show that $\mathcal{B} = (v_1, iv_1, \dots, v_n, iv_n)$ is a basis of $V$ over $\mathbb{R}$ .

Spanning. Let $v \in V$ . Then $v = \sum_k z_kv_k$ with $z_k \in \mathbb{C}$ . Write $z_k = a_k + b_ki$ with $a_k, b_k \in \mathbb{R}$ . By the distributive and associative axioms of scalar multiplication, $z_kv_k = a_kv_k + (b_ki)v_k = a_kv_k + b_k(iv_k)$ . Hence $v = \sum_k \big(a_kv_k + b_k(iv_k)\big)$ , a real combination of $\mathcal{B}$ .

Independence. Let $\sum_k \big(a_kv_k + b_k(iv_k)\big) = 0$ with $a_k, b_k \in \mathbb{R}$ . Reading the same axioms backwards, $\sum_k (a_k + b_ki)v_k = 0$ . Since $(v_1, \dots, v_n)$ is independent over $\mathbb{C}$ , every $a_k + b_ki = 0$ , so $a_k = b_k = 0$ .

Hence $\mathcal{B}$ is a basis over $\mathbb{R}$ of length $2n$ , and $\dim_\mathbb{R} V = 2n$ .

Exercise (C3: Counting Elements over a Finite Field)

Let $p$ be a prime.

(a) Let $V$ be a vector space over $\mathbb{F}_p$ with $\dim V = k$ . Prove that $V$ has exactly $p^k$ elements.
(b) Deduce that no vector space over $\mathbb{F}_2$ has exactly $6$ elements.
(c) Let $K$ be a finite field that contains $\mathbb{F}_p$ , with the same addition and multiplication. Explain why $K$ is a finite-dimensional vector space over $\mathbb{F}_p$ , and deduce that $K$ has $p^k$ elements for some integer $k \ge 1$ .

Hint: for (a), use coordinates.

Solution.

(a) Let $\mathcal{B}$ be a basis of $V$ , of length $k$ . By Theorem 1.5.2, $v \mapsto [v]_{\mathcal{B}}$ is a bijection from $V$ to $\mathbb{F}_p^k$ : every column is the coordinate vector of exactly one vector. So $V$ has as many elements as $\mathbb{F}_p^k$ . A column in $\mathbb{F}_p^k$ is a choice of $k$ entries, each from the $p$ elements of $\mathbb{F}_p$ , so there are $p^k$ columns. Hence $V$ has $p^k$ elements.
(b) A vector space over $\mathbb{F}_2$ with finitely many elements is spanned by the finite list of all its elements, so it is finite-dimensional, of some dimension $k$ . By (a) it has $2^k$ elements. Since $6$ is not a power of $2$ , no such space has $6$ elements.
(c) Define scalar multiplication $\mathbb{F}_p \times K \to K$ by the multiplication of $K$ . The vector space axioms are then instances of the field axioms of $K$ : addition in $K$ is commutative and associative with zero and negatives, multiplication is associative, $1 \cdot a = a$ , and multiplication distributes over addition. So $K$ is a vector space over $\mathbb{F}_p$ . It is spanned by the finite list of all its elements, so it is finite-dimensional; let $k = \dim_{\mathbb{F}_p} K$ . By (a), $K$ has $p^k$ elements. Since $K$ contains $0 \ne 1$ , it is not the zero space, so $k \ge 1$ .