4 Linear algebra 4.11 Fundamental solutions are linearly independent 4.13 Finding dimensions

4.12 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.12.1 The extension lemma

Lemma 4.12.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.12.2 Every linearly independent sequence can be extended to a basis

Proposition 4.12.2.

Let $V$ be finite-dimensional and let $\mathbf{l}_{1},\ldots,\mathbf{l}_{n}$ be linearly independent. 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.12.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.12.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}$ .