The Dimension of a Vector Space

In the prior subsection we defined the basis of a vector space, and we saw that a space can have many different bases. For example, following the definition of a basis, we saw three different bases for $\mathbb {R} ^{2}$. So we cannot talk about "the" basis for a vector space. True, some vector spaces have bases that strike us as more natural than others, for instance, $\mathbb {R} ^{2}$'s basis ${\mathcal {E}}_{2}$ or $\mathbb {R} ^{3}$'s basis ${\mathcal {E}}_{3}$ or ${\mathcal {P}}_{2}$'s basis $\langle 1,x,x^{2}\rangle$. But, for example in the space $\{a_{2}x^{2}+a_{1}x+a_{0}\,{\big |}\,2a_{2}-a_{0}=a_{1}\}$, no particular basis leaps out at us as the most natural one. We cannot, in general, associate with a space any single basis that best describes that space.

We can, however, find something about the bases that is uniquely associated with the space. This subsection shows that any two bases for a space have the same number of elements. So, with each space we can associate a number, the number of vectors in any of its bases.

This brings us back to when we considered the two things that could be meant by the term "minimal spanning set". At that point we defined "minimal" as linearly independent, but we noted that another reasonable interpretation of the term is that a spanning set is "minimal" when it has the fewest number of elements of any set with the same span. At the end of this subsection, after we have shown that all bases have the same number of elements, then we will have shown that the two senses of "minimal" are equivalent.

Before we start, we first limit our attention to spaces where at least one basis has only finitely many members.

Definition 2.1: A vector space is finite-dimensional if it has a basis with only finitely many vectors.

(One reason for sticking to finite-dimensional spaces is so that the representation of a vector with respect to a basis is a finitely-tall vector, and so can be easily written.) From now on we study only finite-dimensional vector spaces. We shall take the term "vector space" to mean "finite-dimensional vector space". Other spaces are interesting and important, but they lie outside of our scope.

To prove the main theorem we shall use a technical result.

Lemma 2.2 (Exchange Lemma): Assume that $B=\langle {\vec {\beta }}_{1},\dots ,{\vec {\beta }}_{n}\rangle$ is a basis for a vector space, and that for the vector ${\vec {v}}$ the relationship ${\vec {v}}=c_{1}{\vec {\beta }}_{1}+c_{2}{\vec {\beta }}_{2}+\cdots +c_{n}{\vec {\beta }}_{n}$ has $c_{i}\neq 0$. Then exchanging ${\vec {\beta }}_{i}$ for ${\vec {v}}$ yields another basis for the space.

Proof: Call the outcome of the exchange ${\hat {B}}=\langle {\vec {\beta }}_{1},\dots ,{\vec {\beta }}_{i-1},{\vec {v}},{\vec {\beta }}_{i+1},\dots ,{\vec {\beta }}_{n}\rangle$.

We first show that ${\hat {B}}$ is linearly independent. Any relationship $d_{1}{\vec {\beta }}_{1}+\dots +d_{i}{\vec {v}}+\dots +d_{n}{\vec {\beta }}_{n}={\vec {0}}$ among the members of ${\hat {B}}$, after substitution for ${\vec {v}}$,

$d_{1}{\vec {\beta }}_{1}+\dots +d_{i}\cdot (c_{1}{\vec {\beta }}_{1}+\dots +c_{i}{\vec {\beta }}_{i}+\dots +c_{n}{\vec {\beta }}_{n})+\dots +d_{n}{\vec {\beta }}_{n}={\vec {0}}\qquad \qquad (*)$

gives a linear relationship among the members of $B$. The basis $B$ is linearly independent, so the coefficient $d_{i}c_{i}$ of ${\vec {\beta }}_{i}$ is zero. Because $c_{i}$ is assumed to be nonzero, $d_{i}=0$. Using this in equation $(*)$ above gives that all of the other $d$'s are also zero. Therefore ${\hat {B}}$ is linearly independent.

We finish by showing that ${\hat {B}}$ has the same span as $B$. Half of this argument, that $[{\hat {B}}]\subseteq [B]$, is easy; any member $d_{1}{\vec {\beta }}_{1}+\dots +d_{i}{\vec {v}}+\dots +d_{n}{\vec {\beta }}_{n}$ of $[{\hat {B}}]$ can be written $d_{1}{\vec {\beta }}_{1}+\dots +d_{i}\cdot (c_{1}{\vec {\beta }}_{1}+\dots +c_{n}{\vec {\beta }}_{n})+\dots +d_{n}{\vec {\beta }}_{n}$, which is a linear combination of linear combinations of members of $B$, and hence is in $[B]$. For the $[B]\subseteq [{\hat {B}}]$ half of the argument, recall that when ${\vec {v}}=c_{1}{\vec {\beta }}_{1}+\dots +c_{n}{\vec {\beta }}_{n}$ with $c_{i}\neq 0$, then the equation can be rearranged to ${\vec {\beta }}_{i}=(-c_{1}/c_{i}){\vec {\beta }}_{1}+\dots +(1/c_{i}){\vec {v}}+\dots +(-c_{n}/c_{i}){\vec {\beta }}_{n}$. Now, consider any member $d_{1}{\vec {\beta }}_{1}+\dots +d_{i}{\vec {\beta }}_{i}+\dots +d_{n}{\vec {\beta }}_{n}$ of $[B]$, substitute for ${\vec {\beta }}_{i}$ its expression as a linear combination of the members of ${\hat {B}}$, and recognize (as in the first half of this argument) that the result is a linear combination of linear combinations, of members of ${\hat {B}}$, and hence is in $[{\hat {B}}]$.

Theorem 2.3: In any finite-dimensional vector space, all of the bases have the same number of elements.

Proof: Fix a vector space with at least one finite basis. Choose, from among all of this space's bases, one $B=\langle {\vec {\beta }}_{1},\dots ,{\vec {\beta }}_{n}\rangle$ of minimal size. We will show that any other basis $D={\langle {\vec {\delta }}_{1},{\vec {\delta }}_{2},\ldots \rangle }$ also has the same number of members, $n$. Because $B$ has minimal size, $D$ has no fewer than $n$ vectors. We will argue that it cannot have more than $n$ vectors.

The basis $B$ spans the space and ${\vec {\delta }}_{1}$ is in the space, so ${\vec {\delta }}_{1}$ is a nontrivial linear combination of elements of $B$. By the Exchange Lemma, ${\vec {\delta }}_{1}$ can be swapped for a vector from $B$, resulting in a basis $B_{1}$, where one element is ${\vec {\delta }}$ and all of the $n-1$ other elements are ${\vec {\beta }}$'s.

The prior paragraph forms the basis step for an induction argument. The inductive step starts with a basis $B_{k}$ (for $1\leq k<n$) containing $k$ members of $D$ and $n-k$ members of $B$. We know that $D$ has at least $n$ members so there is a ${\vec {\delta }}_{k+1}$. Represent it as a linear combination of elements of $B_{k}$. The key point: in that representation, at least one of the nonzero scalars must be associated with a ${\vec {\beta }}_{i}$ or else that representation would be a nontrivial linear relationship among elements of the linearly independent set $D$. Exchange ${\vec {\delta }}_{k+1}$ for ${\vec {\beta }}_{i}$ to get a new basis $B_{k+1}$ with one ${\vec {\delta }}$ more and one ${\vec {\beta }}$ fewer than the previous basis $B_{k}$.

Repeat the inductive step until no ${\vec {\beta }}$'s remain, so that $B_{n}$ contains ${\vec {\delta }}_{1},\dots ,{\vec {\delta }}_{n}$. Now, $D$ cannot have more than these $n$ vectors because any ${\vec {\delta }}_{n+1}$ that remains would be in the span of $B_{n}$ (since it is a basis) and hence would be a linear combination of the other ${\vec {\delta }}$'s, contradicting that $D$ is linearly independent.

Again, although we sometimes say "finite-dimensional" as a reminder, in the rest of this book all vector spaces are assumed to be finite-dimensional. An instance of this is that in the next result the word "space" should be taken to mean "finite-dimensional vector space".

The main result of this subsection, that all of the bases in a finite-dimensional vector space have the same number of elements, is the single most important result in this book because, as Example 2.9 shows, it describes what vector spaces and subspaces there can be. We will see more in the next chapter.