# 4.11 Extending to a basis

Our goal in this section is to show that every linearly independent sequence in a finite-dimensional vector space can be extended, by adding some more vectors to the sequence, to a basis.

## 4.11.1 The extension lemma

###### Lemma 4.11.1.

Suppose $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ is a linearly independent sequence in a vector space $V$, and $\mathbf{u}\in V$. Then $\mathbf{u}\notin\operatorname{span}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$ implies $\mathbf{v}_{1},\ldots,\mathbf{v}_{n},\mathbf{u}$ is linearly independent.

###### Proof.

We prove the contrapositive, which is that if $\mathbf{v}_{1},\ldots,\mathbf{v}_{n},\mathbf{u}$ is linearly dependent then $\mathbf{u}\in\operatorname{span}(\mathbf{v}_{1},\ldots,\mathbf{v}_{n})$.

Suppose $\mathbf{v}_{1},\ldots,\mathbf{v}_{n},\mathbf{u}$ is linearly dependent. There are scalars $\lambda,\lambda_{1},\ldots,\lambda_{n}$, not all of which are zero, such that

 $\lambda\mathbf{u}+\sum_{i=1}^{n}\lambda_{i}\mathbf{v}_{i}=\mathbf{0}_{V}.$

$\lambda$ can’t be zero, for then this equation would say that $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$ was linearly dependent. Therefore we can rearrange to get

 $\mathbf{u}=-\lambda^{-1}\sum_{i=1}^{n}\lambda_{i}\mathbf{v}_{i}=\sum_{i=1}^{n}% -\lambda^{-1}\lambda_{i}\mathbf{v}_{i}\in\operatorname{span}(\mathbf{v}_{1},% \ldots,\mathbf{v}_{n})$

as required. ∎

## 4.11.2 Every linearly independent sequence can be extended to a basis

###### Proposition 4.11.2.

Let $\mathbf{l}_{1},\ldots,\mathbf{l}_{n}$ be a linearly independent sequence of elements of a finite-dimensional vector space $V$. Then there is a basis of $V$ containing $\mathbf{l}_{1},\ldots,\mathbf{l}_{n}$.

###### Proof.

: Let $\mathcal{L}=\mathbf{l}_{1},\ldots,\mathbf{l}_{n}$. Since $V$ is finite-dimensional there are elements $\mathbf{v}_{1},\ldots,\mathbf{v}_{m}$ of $V$ that span $V$.

Define a sequence of sequences of elements of $V$ as follows: $\mathcal{S}_{0}=\mathcal{L}$, and for $i\geqslant 0$,

 $\mathcal{S}_{i+1}=\begin{cases}\mathcal{S}_{i}&\text{if }\mathbf{v}_{i+1}\in% \operatorname{span}\mathcal{S}_{i}\\ \mathcal{S}_{i},\mathbf{v}_{i+1}&\text{otherwise.}\end{cases}$

Here $\mathcal{S}_{i},\mathbf{v}_{i+1}$ just means take the sequence $\mathcal{S}_{i}$ and add $\mathbf{v}_{i+1}$ on to the end.

Note that in either case $\mathbf{v}_{i+1}\in\operatorname{span}\mathcal{S}_{i+1}$, and also that $\mathcal{S}_{0}\subseteq\mathcal{S}_{1}\subseteq\cdots\subseteq\mathcal{S}_{m}$.

Each sequence $\mathcal{S}_{i}$ is linearly independent by the extension lemma, Lemma 4.11.1 and in particular $\mathcal{S}_{m}$ is linearly independent. Furthermore $\operatorname{span}\mathcal{S}_{m}$ contains the spanning sequence $\{\mathbf{v}_{1},\ldots,\mathbf{v}_{m}\}$ because for each $i$ we have $\mathbf{v}_{i}\in\operatorname{span}\mathcal{S}_{i}\subseteq\operatorname{span% }\mathcal{S}_{m}$, so since subspaces are closed under taking linear combinations, $\operatorname{span}\mathcal{S}_{m}=V$. Therefore $\mathcal{S}_{m}$ is a basis containing $\mathcal{L}$. This completes the proof. ∎

As a corollary, we can prove that every finite-dimensional vector space has a basis. Start with any nonzero vector you like — this forms a linearly independent sequence of length 1. The above result lets us extend that to a basis, and in particular, a basis exists.

###### Example 4.11.1.

Consider the sequence of elements $\mathcal{L}=\mathbf{l}_{1},\mathbf{l}_{2}$ where $\mathbf{l}_{1}=(0,1,1,0)$, $\mathbf{l}_{2}=(1,0,1,0)$ of the vector space $V$ of all width 4 row vectors with real number entries. It’s easy to check that they are linearly independent. We are going to use the procedure above, together with the spanning sequence

 $\displaystyle\mathbf{v}_{1}=(1,0,0,0),\mathbf{v}_{2}=(0,1,0,0)$ $\displaystyle\mathbf{v}_{3}=(0,0,1,0),\mathbf{v}_{4}=(0,0,0,1)$

of $V$ to produce a basis of $V$ containing $\mathcal{L}$.

We begin with the sequence $\mathcal{S}_{0}=\mathcal{L}$. To find $\mathcal{S}_{1}$ we have to determine if $\mathbf{v}_{1}\in\operatorname{span}\mathcal{S}_{0}$. It isn’t (to see this, show that the system of linear equations

 $\mathbf{v}_{1}=a\mathbf{l}_{1}+b\mathbf{l}_{2}$

has no solutions), so $\mathcal{S}_{1}$ is $\mathcal{S}_{0}$ with $\mathbf{v}_{1}$ added, which is $\mathbf{l}_{1},\mathbf{l}_{2},\mathbf{v}_{1}$.

To find $\mathcal{S}_{2}$ we have to determine if $\mathbf{v}_{2}\in\operatorname{span}\mathcal{S}_{2}$. It is, because

 $\mathbf{v}_{2}=(0,1,0,0)=\mathbf{l}_{1}-\mathbf{l}_{2}+\mathbf{v}_{1}$

so $\mathcal{S}_{2}$ is the same as $\mathcal{S}_{1}$.

To find $\mathcal{S}_{3}$ we have to determine if $\mathbf{v}_{3}\in\operatorname{span}\mathcal{S}_{3}$. It is, because

 $\mathbf{v}_{3}=\mathbf{l}_{2}-\mathbf{v}_{1}$

so $\mathcal{S}_{3}$ is the same as $\mathcal{S}_{2}$.

Finally to find $\mathcal{S}_{4}$ we have to determine if $\mathbf{v}_{4}\in\operatorname{span}\mathcal{S}_{3}$. It is not (no linear combination of $\mathcal{S}_{3}$ can have a nonzero entry in the last position), so $\mathcal{S}_{4}$ is $\mathcal{S}_{3}$ with $\mathbf{v}_{4}$ added. We have run out of $\mathbf{v}_{i}$s, so $\mathcal{S}_{4}$ is the required basis containing $\mathcal{L}$.