Spanning sets
We have just learned about the concept of a vector space, and seen many examples of them. The next idea we want to discuss is that of spanning and spanning sets. In other words, the span of a set of vectors are the vectors we can obtain by taking linear combinations of them. The mathematical definition is as follows.
Definition
Let \(V \) be a vector space. Let \(S = \{v_1,\dots,v_k \}\) be a set of \(k\) vectors from \(V\). Then the span of the set \(S\), usually denoted by \(\langle S \rangle \) or \(\text{span}(S)\) is \(\langle S \rangle = \{ \lambda_1 v_1 + \dots + \lambda_n v_n : \lambda_i \in \mathbb{F} \} \). That is, the set of all vectors that can be obtained by taking linear combinations of the vectors from the set \(S \).
Moreover, we say a set \(S \) is spanning if \(\langle S \rangle = V \), that is, every vector in our vector space \(V \)can be obtained by taking linear combinations of elements from \(S \).
Let us now give plenty of examples to really get to grips with this definition.
Example 1
\(V = \left\{ \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} : a_i \in \mathbb{F} \right\}.\) Recall that we usually write \(\mathbb{F}^3\) to denote this vector space. Let \(S = \left\{v_1 = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, v_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\right\}\).
Let us calculate \(\langle S \rangle\). Let \(\lambda, \mu \in \mathbb{F}\), then we have \(\lambda \cdot \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} + \mu \cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \lambda \\ \mu \\ 0 \end{pmatrix}\) and therefore \(\langle S \rangle = \left\{\begin{pmatrix} \lambda \\ \mu \\ 0 \end{pmatrix} : \lambda,\mu \in \mathbb{F} \right\}\).
Finally, notice that, for example, \(\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \not\in \langle S \rangle\) so \(S\) is not a spanning set.
Example 2
Let \(V = \mathbb{R}[x]_{\leq 2}\) be the set of polynomials with coefficients in the real numbers \(\mathbb{R}\) of degree less than or equal to \(2\). Let our set be \(S = \{1,x,x^2\}\). What is \(\langle S \rangle?\)
Well, any polynomial of degree less than or equal to 2 (a.k.a any element in \(V\)) is of the form \(ax^2 + bx + c\) for some values \(a,b,c \in \mathbb{R}\), but notice such a vector is a linear combination of \(\{1,x,x^2\}\). Therefore every vector can be written as a linear combination of the vectors in \(\langle S \rangle\) is so \(S\) is a spanning set.
Example 3
\(V = \left\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix} : a,b,c,d \in \mathbb{R} \right\}\) be the set of \(2 \times 2\) matrices over the real numbers. We saw in exercise 1 of the previous section that this is a vector space. Let \(S = \left\{ \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix} \right\}\). What is \(\langle S \rangle\)?
By definition, \(\langle S \rangle\) is given by vectors of the form \(\alpha \cdot \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + \beta \cdot \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} + \gamma \cdot \begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix}\) \(= \begin{pmatrix} \alpha + 4\gamma & \beta + \gamma \\ 0 & 0 \end{pmatrix}\), where \(\alpha,\beta,\gamma \in \mathbb{R}\) are real numbers. By relabelling our variables we conclude that \(\langle S \rangle = \left\{\begin{pmatrix} \lambda & \mu \\ 0 & 0 \end{pmatrix} : \lambda,\mu \in \mathbb{R} \right\}\).
Observe in the previous example that had we left \(\begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix}\) out of our set \(S\), and just considered the span of \(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\) and \(\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}\) instead, we would have obtained the same result. So what is happening here?
The answer is that \(\begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix}\) is itself a linear combination of \(\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}\) and \(\begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}\). Therefore the matrix \(\begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix}\) is redundant. In other words, our set \(S\) is not as efficient as it could be, as if we throw \(\begin{pmatrix} 4 & 1 \\ 0 & 0 \end{pmatrix}\) out of our set \(S\), the remaining vectors give us the same span. We state this as a lemma. (The first lemma of the course!)
Lemma
Let \(V \) be a vector space. Let \(S = \{v_1,\dots,v_k \}\) and \(T = \{v_1,\dots,v_k,w \}\). Suppose that \(w\) is a linear combination of the \(v_i\), i.e. \(w \in \langle S \rangle\). Then \(\langle S \rangle = \langle T \rangle\) .
Proof
The idea behind the proof is to show that the two sets, \(\langle S \rangle\) and \(\langle T \rangle\), are equal. There is a standard technique for doing this which involves showing that both sets are subsets of each other, and therefore concluding that they must in fact be equal.
First, let’s show that \(\langle S \rangle \subseteq \langle T \rangle\). Any element in \(\langle S \rangle \) is of the form \(\alpha_1 v_1 + \dots \alpha_k v_k\) for some scalars \(\alpha_i \in \mathbb{F}\). But we can also write this element as \(\alpha_1 v_1 + \dots \alpha_k v_k + 0 \cdot w \) and so it is also in \(\langle T \rangle\). Therefore any element in \(\langle S \rangle\) is also an element of \( \langle T \rangle\), i.e. \(\langle S \rangle \subseteq \langle T \rangle \).
We are left to show that \(\langle T \rangle \subseteq \langle S \rangle\). By assumption we have \(w = \lambda_1v_1 + \dots \lambda_k v_k\) for some scalars \(\lambda \in \mathbb{F}\). Consider an arbitrary element of \(\langle T \rangle\), then we may write it in the form \(\alpha_1 v_1 + \dots \alpha_k v_k + \beta \cdot w \) for some scalars \(\alpha_i,\beta \in \mathbb{F}\). Now we substitute our expression for \(w \) as a linear combination of the \(v_i\) to write this element as
\(\alpha_1 v_1 + \dots \alpha_k v_k + \beta \cdot (\lambda_1v_1 + \dots \lambda_k v_k) = (\alpha_1 + \beta \lambda_1) v_1 + \dots (\alpha_k + \beta \lambda) v_k.\)
Therefore this element is a linear combination of the \(v_i \), that is, it is in \(\langle S \rangle\). Thus we have \(\langle T \rangle \subseteq \langle S \rangle\) and the proof is complete.
Linear independence
We wish to make more sense of what happened in our previous example. As although there’s nothing wrong per se, we would like to have a measure of how “efficient” a set of vectors are at spanning. This is where linear (in)dependence comes in!
Definition
Let \(V \) be a vector space. Let \(v_1,\dots,v_k \) be a sequence of vectors. We say that \(v_1, \dots, v_k \) are linearly independent if the following equivalent statements hold:
- No \( v_i \) is a linear combination of the others.
- The only sequence of scalars \(\alpha_i \) satisfying \( \alpha_1 v_1 + \dots + \alpha_k v_k = 0 \) is \(\alpha_1 = \dots = \alpha_k = 0\).
We say they are linearly dependent if the statements don’t hold.
Let us now see this idea in practice with a couple of examples.
Example 4
Let \(V = \mathbb{R}^3\) and let \(S = \left\{ \begin{pmatrix} 1 \\ 0 \\ 2 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, \begin{pmatrix} 2 \\ 3 \\ 1 \end{pmatrix} \right\}\). Does the set \(S\) contain linearly independent vectors or not?
We wish to find solutions to \(\alpha \cdot \begin{pmatrix} 1 \\ 0 \\ 2 \end{pmatrix} + \beta \cdot \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} + \gamma \cdot \begin{pmatrix} 2 \\ 3 \\ 1 \end{pmatrix}\) \(= \begin{pmatrix} \alpha + \beta + 2 \gamma \\ \beta + 3\gamma \\ 2 \alpha + \beta + \gamma \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}\).
This is a simultaneous equation in \(3\) variables which we can solve to find a non-trivial solution \(\alpha = -1, \beta = 3, \gamma = -1\). Therefore the set \(S\) contains linearly dependent vectors.
Note: If we consider vectors in \(\mathbb{R}^n\) we will be faced with solving \(n\) simultaneous equations in \(n\) variables, which as you can imagine can be quite tedious, however not to fear! In section 5 we will discuss Gaussian elimination, a way to solve simultaneous equations using matrices and so called row operations. For now, however, we shall stick to checking if vectors are linearly independent by solving simultaneous equations the old-fashioned way.
Example 5
Let \(V = \mathbb{C}[x]_{\leq 3}\) be the space of polynomials with degree less than or equal to 3 with complex coefficients. Consider the set \(S = \big\{i , (3+2i)x, 7ix^2 + 2\big\}\). Check if this set of vectors is linearly independent or not.
Once again let us consider solutions to \(\alpha(i) + \beta ((3+2i)x) + \gamma (7ix^2 + 2) =\) \((i \alpha + 2 \gamma) + ((3+2i)\beta)x + 7i \gamma x^2 = 0\).
When solving such solutions for polynomials we use a technique known as comparing coefficients, the idea is that if two polynomials are equal, then the coefficients in each degree must be equal. Observe that \(0\) may be viewed as a polynomial, with coefficient \(0\) in all degrees.
Comparing the degree \(2\) part of the left-hand side with the right-hand side yields \(7i \gamma = 0\), and so \(\gamma = 0\). Substituting this into the constant part of the polynomial reveals that \(\alpha = 0\) too. Finally, by comparing the degree \(1\) part we must have \((3+2i)\beta = 0\) and so \(\beta = 0\). Therefore the only solution to the equation of interest is to set all scalars to be \(0\). Therefore, the set \(S\) contains linearly independent vectors.
Bases
We have now discussed the span of a set, and in particular, defined a set to be spanning if the span of the set equalled the whole space. We also discussed whether a set is linearly independent, which can be thought of as a measure of how efficient a set is at spanning. Now it is time to combine these two ideas, resulting in what is called a basis of a space.
Definition
Let \(V \) be a vector space, and let \(S \) be a set of vectors. Then we say \(S \) (or rather the vectors in \(S \)) is a basis of \(V \) if \(S \) is a spanning set and the vectors in \(S \) are linearly independent.
In essence, a basis of a vector space is a spanning set which is as efficient as possible – every vector in the basis set contributes something to the span. In the next example, we give potentially the most important basis of the vector space \(\mathbb{F}^n\).
Example 6
Let \(V = \mathbb{F}^n\) and let \(\mathcal{E} = \left\{\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, \dots , \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix} \right\}.\) Then \(\mathcal{E}\) is a basis of \(V\), known as the standard basis.
It is standard practice to denote the vectors in the above example by \(e_1,\dots e_n\) respectively, that is, \(e_i\) is the vector with a \(1\) in position \(i\) and \(0\)s elsewhere. We will also adopt this practice.
We must show that \(\mathcal{E}\) is a spanning set, and also that it is linearly independent. I have included the details of these checks in the tab below.
Checking that \(\mathcal{E}\) is a basis.
We must check that it is spanning and linearly independent.
For spanning, let \(\begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix}\) be an arbitrary vector in \(\mathbb{F}^n\). Then we have \(\begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix} = a_1 e_1 + \dots a_n e_n\) and so every vector is in the span, i.e. \(\mathcal{E}\) is a spanning set.
For linear independence, suppose \(\lambda_1 e_1 + \dots \lambda_n e_n = 0\), then by comparing the \(i^{\text{th}}\) entry of both sides we see that \(\lambda_i = 0\). Therefore \(\lambda_1 = \dots = \lambda_n = 0\) is the only solution and so \(S\) consists of a linearly independent set of vectors.
Note: You may have noticed that the ‘n’ appearing in \(\mathbb{F}^n\) is the same ‘n’ appearing in \(\mathcal{E} = \{e_1,\dots e_n\}\). This is no accident, as we will soon see. But first, one more example.
Example 7
\(V = \mathbb{C}^3\). Let \(S = \left\{ \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix},\begin{pmatrix} i \\ 0 \\ 2 + 3i \end{pmatrix},\begin{pmatrix} 0 \\ 1 \\ -2i \end{pmatrix} \right\}\). Check whether \(S\) gives a basis of \(V\) or not.
Let us check that \(S\) is a spanning set first. Let \(\begin{pmatrix} a_1 + b_1i \\ a_2 + b_2i \\ a_3 + b_3i \end{pmatrix}\) be an arbitrary vector in \(V\). Then we must find real numbers \(\lambda_1,\lambda_2,\lambda_3,\mu_1,\mu_2,\mu_3\) such that
One solves the simultaneous equations and obtains:
\(\lambda_1 = \frac{1}{3}a_1 – \frac{1}{2}b_1 + \frac{1}{3}a_2 + \frac{1}{6}b_3\)
\(\lambda_2 = -\frac{1}{2}a_1 + \frac{2}{3}b_1 – \frac{1}{3}b_2 + \frac{1}{6}a_3\)
\(\lambda_3 = -\frac{2}{3}a_1 + b_1 + \frac{1}{3}a_2 – \frac{1}{3}b_3\)
\(\mu_1 = \frac{1}{2}a_1 + \frac{1}{3}b_1 + \frac{1}{3}b_2 – \frac{1}{6}a_3\)
\(\mu_2 = -\frac{2}{3}a_1 – \frac{1}{2}b_1 + \frac{1}{3}a_2 + \frac{1}{6}b_3 \)
\(\mu_3 = -a_1 – \frac{2}{3}b_1 + \frac{1}{3}b_2 + \frac{1}{3}a_3\)
Phew! Therefore any arbitrary vector can be obtained as a (rather complicated) linear combination of the vectors in \(S\).
It remains to show linear independence. Luckily for us, the work is all but done since linear combinations which give the zero vector can be found by setting \(a_1 = a_2 = a_3 = b_1 = b_2 = b_3 = 0\), which in turn gives us \(\lambda_1 = \lambda_2 = \lambda_3 = \mu_1 = \mu_2 = \mu_3 = 0\), and so our set \(S\) is linearly independent. Since \(S\) is a linearly independent spanning set, it is by definition a basis of \(V\), and the example is complete.
Observe, once again that the size of the basis set of \(V = \mathbb{C}^3\) in the above example was \(3\). Is it the case that a basis set of \(\mathbb{C}^3\) is always of size \(3\)? In fact the answer is yes! We now work towards proving this result.
First we state the prove the very useful Steinitz exchange lemma, from which lots of consequences about spanning, linear independence and bases will follow.
Lemma (Steinitz Exchange Lemma)
Let \(V \) be a vector space. Suppose \(S = \{s_1,\dots, s_m \} \) is a set of linearly independent vectors. Further suppose that \(T = \{t_1,\dots,t_n \} \) is a spanning set. Then:
- \( m \leq n \)
- There exists a relabelling of the vectors of \( T \) such that \(\{s_1,\dots, s_m, t_{m+1},\dots t_n \} \) spans \( V \).
Explanation and proof
Before giving the proof, I believe it is worthwhile to discuss a little bit what this result is saying.
Part 1. says that any linearly independent set must be smaller or equal in size to any spanning set. Intuitively, this makes sense, as it is normal to think of linearly independent sets as being small, and spanning sets being large.
Part 2. deserves more of an explanation, for example, why are we relabelling vectors? What is that about? Well, this is just an equivalent way of saying that there is a subset of \(n-m \) vectors of \(T \) which we can join onto \(S \) to create a set that is spanning. The relabelling is saying nothing more than “Once you find the \(m-n \) vectors you wish to add to \(S \), relabel the vectors of \(T \) so that our desired vectors have subscripts \(m+1,\dots, n\)”.
Finally, there is more to this result than first meets the eye, and I think this is often overlooked. The result is saying that if you take any linearly independent set, and any spanning set, and the difference in size between them is \(m-n \), then there exists \(m-n \) vectors of your spanning set which you can add to your linearly independent set to make a new spanning set. Neat, huh!
Now let’s give the proof. After looking at various proofs I settled on this proof from wikipedia, as I felt it was the slickest.
The proof proceeds by induction on \(m \), the size of our linearly independent set. We use \(S = \{s_1,\dots, s_m \} \) to denote the linearly independent set, and \(T = \{t_1,\dots,t_n \} \) to denote the spanning set, just as in the statement of the lemma.
Base case: \(m = 0 \). Part 1. holds because the size of our linearly independent set is \(0 \). Part 2 holds because \(T \) is spanning, and we can take all the vectors in \(T \) to join onto the empty set \(S \).
Assumption: Suppose the result is true for linearly independent sets \(S \) of size \(m-1 \).
Inductive step: We now want to prove the result for linearly independent sets \(S \) of size \(m\). Consider the subset \(\{s_1,\dots,s_{m-1}\} \subset S\) (i.e. removing the last vector). Then this is a linearly independent set of size \(m-1 \) and so there exists a relabelling of the vectors in \(T \) so that \(\{s_1,\dots,s_{m-1},t_m,\dots,t_n\} \subset S\) is a spanning set.
Now we want to somehow stick \(s_m \in S\) into this set. Observe that since \(s_m \in V \) and our set is spanning, there must exist scalars \(\alpha_i\), \(\beta_j\) such that
\(\displaystyle s_m = \sum_{i=1}^{m-1} \alpha_i s_i + \sum_{j=m}^{n} \beta_j t_j \)
Now, one the \(\beta_j \) must be non-zero, otherwise \(s_m \) would be a linear combination of \(s_1,\dots s_{m-1}\) and this would contradict the fact that \(S \) is a linearly independent set. Observe however that for a \(\beta_j \) to be non-zero it must actually exist, and since the \(j\) are such that \(m \leq j \leq n \) we must have \(m \leq n\). This proves part 1.
Finally, by relabelling \(t_m,\dots,t_n\) if necessary, we may assume that \(\beta_m \) is a non-zero scalar. Using our expression for \(s_m \) and rearranging we may write \(t_m \) as
\(t_m = \frac{1}{\beta_m} \big( s_m – \sum_{i=1}^{m-1} \alpha_i s_i – \) \(\sum_{j=m+1}^{n} \beta_j t_j \big)\)
Therefore \(t_m \in \text{span}\big\{s_1,\dots,s_{m-1},\) \(s_m,t_{m+1},\dots,t_n \big\}\). It follows that \(V = \text{span}\left\{ s_1,\dots,s_{m-1},t_m,\dots,t_n \right\} \)\(\subseteq \text{span}\left\{ s_1,\dots,s_m,t_{m+1},\dots,t_n \right\}. \)
That is, \(\left\{ s_1,\dots,,s_m,t_{m+1},\dots,t_n \right\}\) is a spanning set, as required.
That was a long proof, but now we reap the rewards. We begin, we show that all basis sets of a vector space must have the same size! And the best part is, thanks to the exchange lemma, the proof is a few lines long (and you could maybe even squeeze it into one.)
Lemma
Let \(V \) be a vector space, and suppose both \(\mathcal{B} = \left\{b_1,\dots, b_r\right\} \) and \(\mathcal{C} = \left\{c_1,\dots, c_s\right\} \) are bases sets of \(V\). Then \(r = s\). That is, the size of a basis set is well defined.
Proof
\(\mathcal{B}\) is a linearly independent set, and \(\mathcal{C}\) is a spanning set, so by the previous lemma \(r \leq s\).
On the other hand, \(\mathcal{C}\) is a linearly independent set, and \(\mathcal{B}\) is a spanning set, so by the previous lemma \(s \leq r\).
Therefore, \(r = s\).
This is great news. As it allows us to define the dimension of a vector space.
Definition
Let \(V \) be a vector space. Then the dimension of \(V \) is defined to be the size of any basis set.
Let us now find the dimensions of some commonly seen vector spaces.
Example 8
- Let \(V = \mathbb{F}^n\). Then we saw that \(\{e_1,\dots,e_n\}\) is a basis of \(V\) and so the dimension of \(\mathbb{F}^n\) is \(n\).
- \(V = \mathbb{F}[x]_{\leq n} \), the space of polynomials of degree less than or equal to \(n\). Then one can check that \(\{ 1,x,x^2,\dots,x^n\}\) is a basis for \(V\). (This is what is referred to as the standard basis for polynomials). Therefore the dimension of \(\mathbb{F}[x]_{\leq n} \) is \(n+1\).
By counting arguments, we can immediately deduce when certain sets of vectors are not linearly independent, or not spanning. In the particular case when we consider \(n\) vectors in an \(n\) dimensional vector space, the vectors span if and only if they are linearly independent. Let’s give the statement and proof.
Lemma
Let \(V\) be a vector space of dimension \(n\). Let \(S = \{s_1,\dots,s_m\}\) be a set of \(m \) vectors. Then:
- If \(m < n\) then \(S\) cannot be a spanning set.
- If \(m > n \) then \(S\) cannot be a linearly independent set.
- If \(m = n \) then the following are equivalent:
i) \(S\) is a basis
ii) \(S\) is a spanning set
iii) \(S\) is a linearly independent set.
Proof
- Let \(\mathcal{B}\) be a basis set of \(V\), in particular, it is a linearly independent set of \(n\) elements. If \(S\) is spanning we must have \(n < m \) by the exchange lemma. This is a contradiction.
- Very similar argument to part a. (but use the fact that \(\mathcal{B}\) is spanning instead.)
- It’s clear that i. implies ii. and i. implies iii. By definition we have (ii. and iii.) implies i. Therefore it remains to show that ii. if and only if iii. That is, we must show that a set of \(n\) vectors in \(n\) dimensional space are spanning if and only if they are linearly independent.
Thus, suppose \(S = \{s_1,\dots,s_n\}\) is linearly independent. Suppose in hopes of a contradiction that \(S\) is not spanning. Then there exists some vector \(v \in V \) such that \(v \not\in \text{span}(S) \). Therefore \(S \cup \{v\} = \{s_1,\dots,s_n,v\}\) is a linearly independent set in \(V \) of size \(n+1 \). Comparing this to a basis set of \(V \) (of size \(n \)) contradicts the exchange lemma. Thus \(S\) was spanning all along.
Conversely, suppose that \(S = \{s_1,\dots,s_n\}\) is spanning but not linearly independent. Then there exists an \(s_i \) which after relabelling we may assume is \(s_1 \) which is a linear combination of the others. Therefore we may remove it from the set and still get the same span. That is, we would have obtained a spanning set of size \(n-1 \), which comparing to a basis set would contradict the exchange lemma. Therefore \(S\) is linearly independent.
Thinking once again about part 2. of the Steinitz exchange lemma, it is saying that if we have a linearly independent set then we can extend it (i.e. add some vectors) to get a spanning set. A natural refinement of this is to ask whether every linearly independent set can be extended to not just a spanning set, but in fact a basis. The answer is yes, as we will soon see.
We can do something similar for spanning sets. Namely, if we have any spanning set we can remove some of the vectors to obtain a basis. We state these two facts as lemmas and give the proofs.
Lemma
Let \(V\) be a vector space of dimension \(n\). Let \(S = \{s_1,\dots,s_m\}\) be a linearly independent set. Then there exists (not unique) vectors \(v_{m+1}, \dots, v_n\) such that \(\{s_1,\dots,s_m,v_{m+1},\dots,v_n\}\) is a basis set of \(V\).
Proof
Consider a basis set \(\mathcal{B} = \{b_1,\dots,b_n\}\) of \(V \). By the exchange lemma there exists a reordering of the vectors in \(\mathcal{B}\) such that \(\{s_1,\dots,s_m,b_{m+1},\dots,b_n\}\) is a spanning set of \(V \). However, by the previous lemma, a set of \(n \) vectors in \(n \) dimensional space is spanning if and only if it is a basis. Thus we are done.
Note: In the proof, there was nothing special about which basis set we used. Therefore this technique to extend a linearly independent set to a basis works if you pick any basis set to work with.
Finally, we give a lemma saying that any spanning set can be reduced to a basis set.
Lemma
Let \(V\) be a vector space of dimension \(n\). Let \(S = \{s_1,\dots,s_n, \dots, s_m\}\) be a spanning set (so \(m \geq n\)). Then the vectors in \(S\) can be relabelled so that \(\{s_1,\dots,s_n\}\) is a basis of \(V\).
Proof
Consider each vector \(s_i \in S\) in turn. If it can be expressed as a linear combination of the others, we may remove it from our set and not change the span. Once we have made a full pass through all vectors in \(S\) we will have a spanning set in which all vectors are linearly independent, that is, a basis set.
Note: The reduction of a spanning set to a basis is not unique, choosing different orders of running through the elements of the set will result in different bases of the space.
Some examples are almost surely in order to see how these techniques work in practice. We give one example of each and give plenty more in the exercises section at the bottom of the section (which as usual come with full-worked solutions). Let’s start with extending a linearly independent set to a basis.
Example 9
Let \(V = \mathbb{R}^4\). Let \(S = \left\{ \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4\end{pmatrix}, \begin{pmatrix} -1 \\ 0 \\ 1 \\ 0 \end{pmatrix}\right\}.\) One readily checks that \(S\) is a linearly independent set.
Let \(\mathcal{E} = \{e_1,\dots,e_4\}\) be the standard basis. By the “extension lemma” we know that we can add \(2\) vectors from \(\mathcal{E}\) to \(S\) to obtain a basis (note that this is not unique).
We start by considering \(e_1\) (only because it’s first in the list, you can equally start with any vector you like). Specifically, we want to find whether or not it lies in the span of the vectors in \(S\). That is, we want to determine if there is a solution to
\(e_1 = \alpha \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4\end{pmatrix} + \beta \begin{pmatrix} -1 \\ 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} \alpha – \beta \\ 2\alpha \\ 3\alpha + \beta \\ 4\alpha \end{pmatrix}.\)
The second entry tells us we must have \(\alpha = 0\). The third entry then tells us we must have \(\beta = 0\). But then the top entry of the right-hand side is \(\alpha – \beta = 0-0 = 0\), which is not the first entry of \(e_1\), namely \(1\). Therefore there is no solution and so \(e_1\) is not in \(\text{span}(S)\) and so we append it to the set, we now have \(S’ = \left\{\begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}, \begin{pmatrix} -1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, e_1 \right\}\).
Now consider \(e_2\), we wish to determine if it is in the span of the vectors in \(S’\) (that is, our newly constructed set \(S \cup {e_1}\)).
Consider \(e_2 = \alpha \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4\end{pmatrix} + \beta \begin{pmatrix} -1 \\ 0 \\ 1 \\ 0 \end{pmatrix} + \gamma e_1 \)\(= \begin{pmatrix} \alpha – \beta + \gamma \\ 2\alpha \\ 3\alpha + \beta \\ 4\alpha \end{pmatrix} \)
Entry \(2\) implies that \(\alpha = \frac{1}{2}\), however entry \(4\) implies that \(\alpha = 0\), therefore there can be no solution and so \(e_2 \not \in \text{span}(S’)\). We append it to our set of vectors to obtain \(S” = \left\{\begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \end{pmatrix}, \begin{pmatrix} -1 \\ 0 \\ 1 \\ 0 \end{pmatrix}, e_1, e_2 \right\}\).
Finally, since this is a set of \(4\) vectors in \(4\) dimensional space which are linearly independent, they must be a basis and we are finished.
Example 10
Let \(V = \mathbb{R}[x]_{\leq 1}\) (of dimension 2). Let \(S= \left\{2 + x, 3 + 5x, -1 -4x \right\}.\) One checks that \(S\) is spanning. Let us reduce it to a basis of \(V\).
Consider the first vector in \(S\), namely \(2 + x\). We wish to find a solution to
One solves the simultaneous equations and finds that \(\alpha = \beta = 1\). Therefore the first vector in \(S\) is a linear combination of the other \(2\), so we throw it out, giving us a new set \(S’ = \{3+5x, -1 -4x\}\). Since this is a set of \(2\) vectors in a \(2\) dimensional space which spans, they must form a basis.
We finish this example by explicitly checking the set gives a basis. Indeed, for any polynomial of degree less than or equal to 1, say \(a + bx\), we have
To finish the section, recall that in example 7 we had to work hard to check that the given set of vectors was a basis. Therefore it is worth stating now without proof an equivalent condition for a set of vectors to be a basis of \(\mathbb{F}^n\) (and soon we will see how this can be extended to bases of any vector space). We will prove this result later in the course once we have developed some more machinery.
Lemma
Let \(V = \mathbb{F}^n\). Let \(S = \{s_1, \dots, s_n\}\) be a set of vectors in \(V\). Note that each \(s_i = \begin{pmatrix} s_{i_1} \\ \vdots \\ s_{i_n} \end{pmatrix}\). Then \(S\) is a basis set if and only if the matrix with columns given by the \(s_i \) i.e. \(\begin{pmatrix} | & \dots & | \\ s_1 & \dots & s_n \\ | & \dots & | \end{pmatrix}\) has non-zero determinant.
Proof
Later in the course.
To see this lemma in action, let us revisit example 7. Consider the matrix \(\begin{pmatrix} 1 & i & 0 \\ 2 & 0 & 1 \\ 3 & 2 + 3i & -2i \end{pmatrix}\). One computes the determinant (there are various methods, some of which we will discuss later in the course – you can even use an online matrix calculator) and gets \(-6\). Therefore the set of vectors \(\left\{\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}, \begin{pmatrix} i \\ 0 \\ 2+3i \end{pmatrix},\begin{pmatrix} 0 \\ 1 \\ -2i \end{pmatrix}\right\}\) gives a basis of \(\mathbb{C}^3\).
Summary and exercises
In this section we have seen what it means of a set of vectors in a vector space to be spanning, linearly independent and/or a basis of the space. We state and proved the Steinitz exchange lemma, which allowed us to define the dimension of a vector space as the size of a basis set. We also deduced various consequences of the exchange lemma, including how we can sometimes quickly determine if a set is not spanning or not linearly independent using size arguments.
Finally we seen that we can extend any linearly independent set to a basis, and also that we can reduce any spanning set to a basis. (We also give a nice equivalent way to check if a set of \(n\) vectors gives a basis for \(\mathbb{F}^n\), which we will prove later on).
Below are some exercises to test your understanding of the section. Full solutions are given for all exercises.
Exercise 1
Let \(V \) be a vector space. Let \(S = \{ v_1,\dots,v_k\}\) be a set of vectors with each \(v_i \in V\). Show that \(\langle S \rangle \) is a subspace of \(V \). Thus, spans of sets of vectors are subspaces.
Solution
Recall from section 1 that a subset \(W \subset V \) is a subspace if and only if for all vectors \(w,w’ \in W \) and scalars \(\alpha, \beta \in \mathbb{F} \) we have \(\alpha w + \beta w’ \in W\).
Indeed, let \(w, w’ \in \langle S \rangle \) and \(\alpha,\beta \in \mathbb{F} \). Then we may write \(w = \lambda_1 v_1 + \dots + \lambda_n v_n \) and \(w’ = \mu_1 v_1 + \dots + \mu_n v_n \). Then we have
and so \(\alpha w + \beta w’ \in \langle S \rangle \). Therefore \(\langle S \rangle \) is a subspace of \(V \).
Exercise 2
For each of the following sets of vectors in \(\mathbb{R}^3 \), check if they:
i. are linearly independent
ii. span \(\mathbb{R}^3 \)
iii. form a basis of \(\mathbb{R}^3 \)
Solution
- i. The vectors cannot be linearly independent as there are \(4 \) of them, and this would contradict the exchange lemma.
ii. We show that the set of vectors span \(\mathbb{R}^3 \) by checking that all elementary basis vectors lie in the span.
We clearly have \(e_1 \in \langle S \rangle \). Also observe that \(e_2 = 3 \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} – \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} – 2 e_1 \). Finally observe \(e_3 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} – e_1 – e_2 \). Therefore \(S \) spans.
iii. \(S \) cannot be a basis since it is not linearly independent. - Since we have a set of \(3 \) vectors in a \(3 \) dimensional space we know that \(i), ii), iii) \) are equivalent. Let’s use our determinant condition to check if the \(3 \) vectors form a basis.
Putting our vectors into the columns of a matrix and calculating the determinant gives \(\text{det}\begin{pmatrix} 4 & 1.5 & \pi \\ -2 & 0 & -0.25 \\ 1 & -1 & \sqrt{2} \end{pmatrix} \approx 9.15.\) We have that the determinant is non-zero and so \(S \) forms a basis set.
Exercise 3
Let \(V = \mathbb{C}[x]_{\leq 2} \). Let \(S = \{ 1+ 3x, ix\}\). Note that \(S \) is a linearly independent set. Use techniques discussed in this section to extend \(S \) to a basis.
Solution
We saw that any linearly independent set can be extended to a basis by taking any basis (in fact, any spanning set will do) of the space and appending vectors which are not in the span of our set until we have the correct amount of vectors.
For such questions, taking the standard basis is never a bad idea. Therefore let \(\mathcal{E} = \{1,x,x^2\}\) denote the standard basis of polynomials. Our set \(S \) currently has \(2 \) vectors in it, and we know any basis of a \(3\) dimensional space must have \(3 \) vectors, therefore we are looking for one more vector to append to our set.
We may as well work through the vectors in \(\mathcal{E}\) from left to right. Starting with \(1 \) we observe that \(1 = (1+3x) + 3i(ix) \). So \(1 \) is already in the span and therefore we do not append it. Now consider \(x\), we have \(x = -i(ix)\) and so once again \(x\) is in the span. We only have \(x^2 \) left to consider, by theoretical considerations \(x^2 \) must be the vector we append to our set, as otherwise we would not be able to extend our linearly independent set to a basis and the theorem would be wrong…. Indeed this is the case since there are no vectors (i.e. polynomials) in our set of degree \(2 \) and so \(x^2 \) cannot be in the span.
So we append \(x^2 \) to \(S \) to obtain the basis set \(\{ 1+3x, ix, x^2 \} \).