Section 1.7 Basis and dimension
Next, we begin with an important result, sometimes known as the “Fundamental Theorem”:
Theorem 1.7.1. Fundamental Theorem (Steinitz Exchange Lemma).
Suppose \(V = \spn\{\vv_1,\ldots, \vv_n\}\text{.}\) If \(\{\ww_1,\ldots, \ww_m\}\) is a linearly independent set of vectors in \(V\text{,}\) then \(m\leq n\text{.}\)
Strategy.
We won’t give a complete proof of this theorem. The idea is straightforward, but checking all the details takes some work. Since \(\{\vv_1,\ldots, \vv_k\}\) is a spanning set, each of the vectors in our independent set can be written as a linear combination of \(\vv_1,\ldots, \vv_k\text{.}\) In particular, we can write
\begin{equation*}
\ww_1 = a_1\vv_1+a_2\vv_2+\cdots + a_n\vv_n
\end{equation*}
for scalars \(a_1,\ldots, a_n\text{,}\) and these scalars can’t all be zero. (Why? And why is this important?)
The next step is to argue that \(V=\{\ww_1,\vv_2,\ldots, \vv_n\}\text{;}\) that is, that we can replace \(\vv_1\) by \(\ww_1\) without changing the span. This will involve chasing some linear combinations, and remember that we need to check both inclusions to prove set equality. (This step requires us to have assumed that the scalar \(a_1\) is nonzero. Do you see why?)
Next, we similarly replace \(\vv_2\) with \(\ww_2\text{.}\) Note that we can write
\begin{equation*}
\ww_2=a\ww_1+b_2\vv_2+\cdots + b_n\vv_n\text{,}
\end{equation*}
and at least one of the
\(b_i\) must be nonzero. (Why can’t they all be zero? What does
Exercise 1.6.10 tell you about
\(\{\ww_1,\ww_2\}\text{?}\))
If we assume that \(b_2\) is one of the nonzero scalars, we can solve for \(\vv_2\) in the equation above, and replace \(\vv_2\) by \(\ww_2\) in our spanning set. At this point, you will have successfully argued that \(V=\spn\{\ww_1,\ww_2,\vv_3,\ldots, \vv_n\}\text{.}\)
Now, we repeat the process. If \(m\leq n\text{,}\) we eventually run out of \(\ww_i\) vectors, and all is well. The question is, what goes wrong if \(m\gt n\text{?}\) Then we run out of \(\vv_j\) vectors first. We’ll be able to write \(V=\spn\{\ww_1,\ldots, \ww_n\}\text{,}\) and there will be some vectors \(\ww_{n+1},\ldots, \ww_m\) leftover. Why is this a problem? (What assumption about the \(\ww_i\) will we contradict?)
If a set of vectors spans a vector space \(V\text{,}\) but it is not independent, we observed that it is possible to remove a vector from the set and still span \(V\) using a smaller set. This suggests that spanning sets that are also linearly independent are of particular importance, and indeed, they are important enough to have a name.
Definition 1.7.2.
Let \(V\) be a vector space. A set \(\mathcal{B}=\{\mathbf{e}_1,\ldots, \mathbf{e}_n\}\) is called a basis of \(V\) if \(\mathcal{B}\) is linearly independent, and \(\spn\mathcal{B} = V\text{.}\)
The importance of a basis is that vector vector \(\vv\in V\) can be written in terms of the basis, and this expression as a linear combination of basis vectors is unique. Another important fact is that every basis has the same number of elements.
Theorem 1.7.3. Invariance Theorem.
If \(\{\mathbf{e}_1,\ldots, \mathbf{e}_n\}\) and \(\{\mathbf{f}_1,\ldots, \mathbf{f}_m\}\) are both bases of a vector space \(V\text{,}\) then \(m=n\text{.}\)
Strategy.
One way of proving the equality
\(m=n\) is to show that
\(m\leq n\) and
\(m\geq n\text{.}\) We know that since both sets are bases, both sets are independent, and they both span
\(V\text{.}\) Can you see a way to use
Theorem 1.7.1 (twice)?
Proof.
Let
\(A=\{\mathbf{e}_1,\ldots, \mathbf{e}_n\}\) and let
\(B=\{\mathbf{f}_1,\ldots, \mathbf{f}_m\}\text{.}\) Since both
\(A\) and
\(B\) are bases, both sets are linearly independent, and both sets span
\(V\text{.}\) Since
\(A\) is independent and
\(\spn B=V\text{,}\) we must have
\(n\leq m\text{,}\) by
Theorem 1.7.1. Similarly, since
\(\spn A = V\) and
\(B\) is independent, we must have
\(n\geq m\text{,}\) and therefore,
\(n=m\text{.}\)
Suppose
\(V=\spn\{\vv_1,\ldots,\vv_n\}\text{.}\) If this set is not linearly independent,
Theorem 1.4.10 tells us that we can remove a vector from the set, and still span
\(V\text{.}\) We can repeat this procedure until we have a linearly independent set of vectors, which will then be a basis. These results let us make a definition.
Definition 1.7.4.
Let \(V\) be a vector space. If \(V\) can be spanned by a finite number of vectors, then we call \(V\) a finite-dimensional vector space. If \(V\) is finite-dimensional (and non-trivial), and \(\{\mathbf{e}_1,\ldots, \mathbf{e}_n\}\) is a basis of \(V\text{,}\) we say that \(V\) has dimension \(n\text{,}\) and write
\begin{equation*}
\dim V = n\text{.}
\end{equation*}
If \(V\) cannot be spanned by finitely many vectors, we say that \(V\) is infinite-dimensional.
Exercise 1.7.5.
Find a basis for \(U=\{X\in M_{22} \,|\, XA = AX\}\text{,}\) if \(A = \bbm 1\amp 1\\0\amp 0\ebm\)
Example 1.7.6. Standard bases.
Most of the vector spaces we work with come equipped with a standard basis. The standard basis for a vector space is typically a basis such that the scalars needed to express a vector in terms of that basis are the same scalars used to define the vector in the first place. For example, we write an element of \(\R^3\) as \((x,y,z)\) (or \(\langle x,y,z\rangle\text{,}\) or \(\begin{bmatrix}x\amp y\amp z\end{bmatrix}\text{,}\) or \(\begin{bmatrix}x\\y\\z\end{bmatrix}\)…). We can also write
\begin{equation*}
(x,y,z)=x(1,0,0)+y(0,1,0)+z(0,0,1)\text{.}
\end{equation*}
The set \(\{(1,0,0),(0,1,0),(0,0,1)\}\) is the standard basis for \(\R^3\text{.}\) In general, the vector space \(\R^n\) (written this time as column vectors) has standard basis
\begin{equation*}
\vece_1=\bbm 1\\0\\ \vdots \\0\ebm, \vece_2 = \bbm 0\\1\\ \vdots \\0\ebm, \ldots, \vece_n=\bbm 0\\0\\ \vdots \\1\ebm\text{.}
\end{equation*}
From this, we can conclude (unsurprisingly) that \(\dim \R^n = n\text{.}\)
Similarly, a polynomial \(p(x)\in P_n(\R)\) is usually written as
\begin{equation*}
p(x) = a_0+a_1x+a_2x^2+\cdots + a_nx^n\text{,}
\end{equation*}
suggesting the standard basis \(\{1,x,x^2,\ldots, x^n\}\text{.}\) As a result, we see that \(\dim P_n(\R)=n+1\text{.}\)
For one more example, we note that a \(2\times 2\) matrix \(A\in M_{22}(\R)\) can be written as
\begin{equation*}
\bbm a\amp b\\c\amp d\ebm = a\bbm 1\amp 0\\0\amp 0\ebm+b\bbm 0\amp 1\\0\amp 0\ebm +c\bbm 0\amp 0\\1\amp 0\ebm + d\bbm 0\amp 0\\0\amp 1\ebm\text{,}
\end{equation*}
which suggests a standard basis for \(M_{22}(\R)\text{,}\) with similar results for any other matrix space. From this, we can conclude (exercise) that \(\dim M_{mn}(\R)=mn\text{.}\)
Exercise 1.7.7.
Show that the following sets are bases of \(\R^3\text{.}\)
(a)
\(\{(1,1,0),(1,0,1),(0,1,1)\}\)
(b)
\(\{(-1,1,1),(1,-1,1),(1,1,-1)\}\)
The next two exercises are left to the reader to solve. In each case, your goal should be to turn the questions of independence and span into a system of equations, which you can then solve using the computer.
Exercise 1.7.8.
Show that the following is a basis of \(M_{22}\text{:}\)
\begin{equation*}
\left\{\bbm 1\amp 0\\0\amp 1\ebm, \bbm 0\amp 1\\1\amp 0\ebm, \bbm 1\amp 1\\0\amp 1\ebm, \bbm 1\amp 0\\0\amp 0\ebm\right\}\text{.}
\end{equation*}
Hint.
For independence, consider the linear combination
\begin{equation*}
w\bbm 1\amp 0\\0\amp 1\ebm + x\bbm 0\amp 1\\1\amp 0\ebm +y\bbm 1\amp 1\\0\amp 1\ebm +z\bbm 1\amp 0\\0\amp 0\ebm=\bbm 1\amp 0\\0\amp 1\ebm\text{.}
\end{equation*}
Combine the left-hand side, and then equate entries of the matrices on either side to obtain a system of equations.
Exercise 1.7.9.
Show that \(\{1+x,x+x^2,x^2+x^3,x^3\}\) is a basis for \(P_3\text{.}\)
Hint.
For independence, consider the linear combination
\begin{equation*}
a(1+x)+b(x+x^2)+c(x^2+x^3)+dx^3=0\text{.}
\end{equation*}
When dealing with polynomials, we need to collect like terms and equate coefficients:
\begin{equation*}
a\cdot 1 +(a+b)x+(b+c)x^2+(c+d)x^3=0\text{,}
\end{equation*}
so the coefficients \(a, a+b, b+c, c+d\) must all equal zero.
Exercise 1.7.10.
Find a basis and dimension for the following subspaces of \(P_2\text{:}\)
(a)
\(U_1 = \{a(1+x)+b(x+x^2)\,|\, a,b\in\R\}\)
(b)
\(U_2=\{p(x)\in P_2 \,|\, p(1)=0\}\)
(c)
\(U_3 = \{p(x)\in P_2 \,|\, p(x)=p(-x)\}\)
We’ve noted a few times now that if \(\ww\in\spn\{\vv_1,\ldots, \vv_n\}\text{,}\) then
\begin{equation*}
\spn\{\ww,\vv_1,\ldots, \vv_n\}=\spn\{\vv_1,\ldots, \vv_n\}
\end{equation*}
If \(\ww\) is not in the span, we can make another useful observation:
Lemma 1.7.11. Independent Lemma.
Suppose \(\{\vv_1,\ldots, \vv_n\}\) is a linearly independent set of vectors in a vector space \(V\text{.}\) If \(\uu\in V\) but \(\uu\notin \spn\{\vv_1,\ldots, \vv_n\}\text{,}\) then \(\{\uu,\vv_1,\ldots, \vv_n\}\) is independent.
Strategy.
We want to show that a set of vectors is linearly independent, so we should begin by setting a linear combination of these vectors equal to the zero vector. Our goal is to show that all the coefficients have to be zero.
Since the vector \(\uu\) is “special”, its coefficient gets a different treatment, using a familiar tautology: either this coefficient is zero, or it isn’t.
what if the coefficient of \(\uu\) is nonzero? Does that contradict one of our assumptions? If the coefficient of \(\uu\) is zero, then it disappears from our linear combination. What assumption applies to the remaining vectors?
Proof.
Suppose \(S=\{\vv_1,\ldots, \vv_n\}\) is independent, and that \(\uu\notin\spn S\text{.}\) Suppose we have
\begin{equation*}
a\uu+c_1\vv_1+c_2\vv_2+\cdots +c_n\mathbf{b}_n=\zer
\end{equation*}
for scalars \(a,c_1,\ldots, c_n\text{.}\) We must have \(a=0\text{;}\) otherwise, we can multiply by \(\frac1a\) and rearrange to obtain
\begin{equation*}
\uu = -\frac{c_1}{a}\vv_1-\cdots -\frac{c_n}{a}\vv_n\text{,}
\end{equation*}
but this would mean that \(\uu\in \spn S\text{,}\) contradicting our assumption.
With \(a=0\) we’re left with
\begin{equation*}
c_1\vv_1+c_2\vv_2+\cdots +c_n\mathbf{b}_n=\zer\text{,}
\end{equation*}
and since we assumed that the set \(S\) is independent, we must have \(c_1=c_2=\cdots=c_n=0\text{.}\) Since we already showed \(a=0\text{,}\) this shows that \(\{\uu,\vv_1,\ldots, \vv_n\}\) is independent.
This is, in fact, an “if and only if” result. If \(\uu\in\spn\{\vv_1,\ldots, \vv_n\}\text{,}\) then \(\{\uu,\vv_1,\ldots, \vv_n\}\) is not independent. Above, we argued that if \(V\) is finite dimensional, then any spanning set for \(V\) can be reduced to a basis. It probably won’t surprise you that the following is also true.
Lemma 1.7.12.
Let \(V\) be a finite-dimensional vector space, and let \(U\) be any subspace of \(V\text{.}\) Then any independent set of vectors \(\{\uu_1,\ldots, \uu_k\}\) in \(U\) can be enlarged to a basis of \(U\text{.}\)
Strategy.
We have an independent set of vectors that doesn’t span our subspace. That means there must be some vector in
\(U\) that isn’t in the span, so
Lemma 1.7.11 applies: we can add that vector to our set, and get a larger independent set.
Now it’s just a matter of repeating this process until we get a spanning set. But there’s one gap: how do we know the process has to stop? Why can’t we just keep adding vectors forever, getting larger and larger independent sets?
Proof.
This follows from
Lemma 1.7.11. If our independent set of vectors spans
\(U\text{,}\) then it’s a basis and we’re done. If not, we can find some vector not in the span, and add it to our set to obtain a larger set that is still independent. We can continue adding vectors in this fashion until we obtain a spanning set.
Note that this process must terminate: \(V\) is finite-dimensional, so there is a finite spanning set for \(V\text{.}\) By the Steinitz Exchange lemma, our independent set cannot get larger than this spanning set.
Theorem 1.7.13.
Any finite-dimensional (non-trivial) vector space \(V\) has a basis. Moreover:
If \(V\) can be spanned by \(m\) vectors, then \(\dim V\leq m\text{.}\)
Given an independent set \(I\) in \(V\) that does not span \(V\text{,}\) and a basis \(\mathcal{B}\) of \(V\text{,}\) we can enlarge \(I\) to a basis of \(V\) by adding elements of \(\mathcal{B}\text{.}\)
Strategy.
Much of this theorem sums up some of what we’ve learned so far: As long as a vector space
\(V\) contains a nonzero vector
\(\vv\text{,}\) the set
\(\{\vv\}\) is independent and can be enlarged to a basis, by
Lemma 1.7.12. The size of any spanning set is at least as big as the dimension of
\(V\text{,}\) by
Theorem 1.7.1.
To understand why we can enlarge a given independent set using elements of an
existing basis, we need to think about why there must be some vector in this basis that is not in the span of our independent set, so that we can apply
Lemma 1.7.12.
Proof.
Let
\(V\) be a finite-dimensional, non-trivial vector space. If
\(\vv\neq \zer\) is a vector in
\(V\text{,}\) then
\(\{\vv\}\) is linearly independent. By
Lemma 1.7.12, we can enlarge this set to a basis of
\(V\text{,}\) so
\(V\) has a basis.
Now, suppose
\(V = \spn\{\ww_1,\ldots, \ww_m\}\text{,}\) and let
\(B=\{\vv_1,\ldots, \vv_n\}\) be a basis for
\(V\text{.}\) By definition, we have
\(\dim V=n\text{,}\) and by
Theorem 1.7.1, since
\(B\) is linearly independent, we must have
\(n\leq m\text{.}\)
Let us now consider an independent set
\(I=\{\uu_1,\ldots, \uu_k\}\text{.}\) Since
\(I\) is independent and
\(B\) spans
\(V\text{,}\) we must have
\(k\leq n\text{.}\) If
\(\spn I\neq V\text{,}\) there must be some element of
\(B\) that is not in the span of
\(I\text{:}\) if every element of
\(B\) is in
\(\spn I\text{,}\) then
\(\spn I = \spn (B\cup I)\) by
Theorem 1.4.10. And since
\(B\) is a basis, it spans
\(V\text{,}\) so every element of
\(I\) is in the span of
\(B\text{,}\) and we similarly have that
\(\spn (B\cup I)=\spn B\text{,}\) so
\(\spn B=\spn I\text{.}\)
Since we can find an element of \(B\) that is not in the span of \(I\text{,}\) we can add that element to \(I\text{,}\) and the resulting set is still independent. If the new set spans \(V\text{,}\) we’re done. If not, we can repeat the process, adding another vector from \(B\text{.}\) Since the set \(B\) is finite, this process must eventually end.
Exercise 1.7.14.
Find a basis of \(M_{22}(\R)\) that contains the vectors
\begin{equation*}
\vv=\bbm 1\amp 1\\0\amp 0\ebm, \ww=\bbm 0\amp 1\\0\amp 1\ebm\text{.}
\end{equation*}
Exercise 1.7.15.
Extend the set \(\{1+x,x+x^2,x-x^3\}\) to a basis of \(P_3(\R)\text{.}\)
Exercise 1.7.16.
Give two examples of infinite-dimensional vector spaces. Support your answer.
Exercise 1.7.17.
Determine whether the following statements are true or false.
(a)
(b)
It is possible for a set of 2 vectors to be linearly independent in \(\R^3\text{.}\)
True.
There are many such examples, including \(\{(1,0,0),(0,1,0)\}\text{.}\)
False.
There are many such examples, including \(\{(1,0,0),(0,1,0)\}\text{.}\)
(c)
A set of 4 vectors can span \(\R^3\text{.}\)
True.
Add any vector you want to a basis for \(\R^3\text{,}\) and the resulting set will span.
False.
Add any vector you want to a basis for \(\R^3\text{,}\) and the resulting set will span.
(d)
It is possible for a set of 4 vectors to be linearly independent in \(\R^3\text{.}\)
True.
We know that 3 vectors can span \(\R^3\text{,}\) and an independent set cannot be larger than a spanning set.
False.
We know that 3 vectors can span \(\R^3\text{,}\) and an independent set cannot be larger than a spanning set.
Let’s recap our results so far:
A basis for a vector space \(V\) is an independent set of vectors that spans \(V\text{.}\)
The number of vectors in any basis of \(V\) is a constant, called the dimension of \(V\text{.}\)
The number of vectors in any independent set is always less than or equal to the number of vectors in a spanning set.
In a finite-dimensional vector space, any independent set can be enlarged to a basis, and any spanning set can be cut down to a basis by deleting vectors that are in the span of the remaining vectors.
Another important aspect of dimension is that it reduces many problems, such as determining equality of subspaces, to counting problems.
Theorem 1.7.18.
Let \(U\) and \(W\) be subspaces of a finite-dimensional vector space \(V\text{.}\)
If \(U\subseteq W\text{,}\) then \(\dim U\leq \dim W\text{.}\)
If \(U\subseteq W\) and \(\dim U=\dim W\text{,}\) then \(U=W\text{.}\)
Proof.
Suppose
\(U\subseteq W\text{,}\) and let
\(B=\{\uu_1,\ldots, \uu_k\}\) be a basis for
\(U\text{.}\) Since
\(B\) is a basis, it’s independent. And since
\(B\subseteq U\) and
\(U\subseteq W\text{,}\) \(B\subseteq W\text{.}\) Thus,
\(B\) is an independent subset of
\(W\text{,}\) and since any basis of
\(W\) spans
\(W\text{,}\) we know that
\(\dim U = k \leq \dim W\text{,}\) by
Theorem 1.7.1.
Suppose \(U\subseteq W\) and \(\dim U = \dim W\text{.}\) Let \(B\) be a basis for \(U\text{.}\) As above, \(B\) is an independent subset of \(W\text{.}\) If \(W\neq U\text{,}\) then there is some \(\ww\in W\) with \(\ww\notin U\text{.}\) But \(U=\spn B\text{,}\) so that would mean that \(B\cup \{\ww\}\) is a linearly independent set containing \(\dim U+1\) vectors. This is impossible, since \(\dim W=\dim U\text{,}\) so no independent set can contain more than \(\dim U\) vectors.
An even more useful counting result is the following:
Theorem 1.7.19.
Let \(V\) be an \(n\)-dimensional vector space. If the set \(S\) contains \(n\) vectors, then \(S\) is independent if and only if \(\spn S=V\text{.}\)
Strategy.
This result is a combination of three observations:
The dimension of \(V\) is the size of any basis
Any independent set can be enlarged to a basis, and cannot have more vectors than a basis.
Any spanning set contains a basis, and cannot have fewer vectors than a basis.
Proof.
If \(S\) is independent, then it can be extended to a basis \(B\) with \(S\subseteq B\text{.}\) But \(S\) and \(B\) both contain \(n\) vectors (since \(\dim V=n\)), so we must have \(S=B\text{.}\)
If \(S\) spans \(V\text{,}\) then \(S\) must contain a basis \(B\text{,}\) and as above, since \(S\) and \(B\) contain the same number of vectors, they must be equal.
Theorem 1.7.19 saves us a lot of time, since it tells us that, when we know the dimension of
\(V\text{,}\) we do not have to check both independence and span to confirm a basis; checking one of the two implies the other. (And usually independence is easier to check.)
We saw this in
Exercise 1.7.7: given a set of vectors in
\(\R^3\text{,}\) we form the matrix
\(A\) with these vectors as columns. This matrix becomes the coefficient matrix for the system of equations we obtain when checking for independence,
and for the system we obtain when checking for span. In both cases, the condition on
\(A\) is the same; namely, that it must be invertible.
Exercises Exercises
1.
2.
3.
True or false: if a set \(S\) of vectors is linearly independent in a vector space \(V\text{,}\) but \(S\) does not span \(V\text{,}\) then \(S\) can be extended to a basis for \(V\) by adding vectors.
True.
What if \(V\) is infinite-dimensional?
False.
What if \(V\) is infinite-dimensional?
4.
True or false: if \(V=\spn\{\vv_1,\vv_2,\vv_3\}\text{,}\) then \(\dim V=3\text{.}\)
True.
What if the set \(\{\vv_1,\vv_2,\vv_3\}\) is linearly dependent?
False.
What if the set \(\{\vv_1,\vv_2,\vv_3\}\) is linearly dependent?
5.
True or false: if \(U\) is a subspace of a vector space \(V\text{,}\) and \(U=\spn(S)\) for a finite set of vectors \(S\text{,}\) then \(S\) contains a basis for \(U\text{.}\)
True.
Since \(S\) is finite and spans \(U\text{,}\) the subspace \(U\) is finite-dimensional. If \(S\) is linearly dependent, we can remove vectors from \(S\) until we obtain a set that spans \(U\) and is linearly independent.
False.
Since \(S\) is finite and spans \(U\text{,}\) the subspace \(U\) is finite-dimensional. If \(S\) is linearly dependent, we can remove vectors from \(S\) until we obtain a set that spans \(U\) and is linearly independent.
6.
7.
8.