Proof of the Basis Extension Theorem

The Claim and Its Ingredients

A basis extension argument has two tasks: retain the independence of the original list, and add enough vectors to span the whole space. The key is to add a candidate only when it is not already in the span of the vectors selected so far. This choice preserves independence; a fixed spanning list ensures that the process has considered enough candidates to produce a spanning list.

Work over a scalar field \(\mathbb{F}\), which may be \(\mathbb{R}\) or \(\mathbb{C}\). For a list \((\mathbf{v}_1,\ldots,\mathbf{v}_k)\) in a vector space \(V\), its span is the set of all linear combinations of its entries. The list is independent if the only solution of \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k=\mathbf{0}\) is \(c_1=\cdots=c_k=0\). A basis is a list that is both independent and spanning. We use the convention that the span of the empty list is \(\{\mathbf{0}\}\), and that the empty list is independent.

In the finite-list version, “appended” means that the original entries remain in their original order, followed by the selected entries of the spanning list. The selection does not require a pre-existing basis containing the given independent list. Instead, it builds the required list while checking independence at each addition.

Why an Addition Preserves Independence

The test for adding a candidate is membership in the current span. The following lemma gives the reason for that test.

Proof. Suppose \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k+d\mathbf{w}=\mathbf{0}\). If \(d\ne0\), rearranging and dividing by \(d\) gives \(\mathbf{w}=-\frac{c_1}{d}\mathbf{v}_1-\cdots-\frac{c_k}{d}\mathbf{v}_k\), contradicting the assumption that \(\mathbf{w}\) is outside the current span. Therefore \(d=0\). The relation reduces to \(c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k=\mathbf{0}\), and independence of the original list gives \(c_1=\cdots=c_k=0\). Thus the enlarged list is independent. If \(k=0\), the same argument says that \(d\mathbf{w}=\mathbf{0}\) forces \(d=0\), since \(\mathbf{w}\notin\{\mathbf{0}\}\). \(\square\)

The condition “outside the current span” is essential. A candidate already in that span can be expressed using the selected vectors, which gives a dependence relation as soon as it is appended. The lemma addresses independence; the spanning list will ensure that enough candidates are available to reach all of \(V\).

The Selection Process and Its Proof

First suppose the fixed spanning set is given as a finite list \((\mathbf{w}_1,\ldots,\mathbf{w}_m)\). Start with the independent list \((\mathbf{v}_1,\ldots,\mathbf{v}_k)\). In order, inspect each \(\mathbf{w}_j\): append it if it is outside the span of the current list, and otherwise leave the list unchanged. The list is finite, so exactly \(m\) candidates are inspected. More importantly, the choice at each step has two complementary consequences: accepted candidates preserve independence, while skipped candidates are already represented by the current list.

Proof of the Basis Extension Theorem for a finite spanning list. Let \(L\) be the list at the end of the process. It is independent initially. Whenever the process appends an entry, that entry is outside the span of the current list, so the lemma shows that the new list is independent. Skipping an entry does not change the list. Therefore \(L\) is independent after all \(m\) inspections.

Now take any \(\mathbf{w}_j\) from the fixed spanning list. If it was appended, it is an entry of \(L\), hence belongs to \(\operatorname{span}(L)\). If it was skipped, then at the time it was inspected it belonged to the span of the current list. Every vector in that list remains in the final list, so the span of the current list is contained in \(\operatorname{span}(L)\). Thus \(\mathbf{w}_j\in\operatorname{span}(L)\) in either case. All entries of the fixed list lie in \(\operatorname{span}(L)\), and the fixed list spans \(V\); consequently \(V\subseteq\operatorname{span}(L)\). Conversely, \(L\) consists of vectors in \(V\), and a vector space contains every linear combination of its vectors, so \(\operatorname{span}(L)\subseteq V\). Hence \(L\) spans \(V\). Since \(L\) is both independent and spanning, it is a basis, and it contains the original list in its original order. \(\square\)

The theorem also works when the stated spanning set \(S\) is not finite. Because \(V\) is finite-dimensional, it has a finite basis \((\mathbf{b}_1,\ldots,\mathbf{b}_n)\). Each \(\mathbf{b}_i\) is a finite linear combination of elements of \(S\), by the definition of spanning set. Collect all the elements of \(S\) used in these finitely many expressions; their union is finite. It spans \(V\), since it spans every \(\mathbf{b}_i\), and every vector in \(V\) is a linear combination of the basis entries. Applying the finite-list construction to this finite collection produces an extension using only elements of the original \(S\).

Worked Applications of the Argument

Common Pitfall: Adding Every Generator

A tempting but incorrect variation is to append every entry of the fixed spanning list, whether or not it is already in the current span. For example, start in \(\mathbb{R}^2\) with \((1,1)\) and use \((\mathbf{e}_1,\mathbf{e}_2)\). Appending both candidates produces \(((1,1),\mathbf{e}_1,\mathbf{e}_2)\), but this list is dependent because \((1,1)-\mathbf{e}_1-\mathbf{e}_2=(0,0)\). The error is appending \(\mathbf{e}_2\) after \(\mathbf{e}_1\): already \(\mathbf{e}_2=(1,1)-\mathbf{e}_1\), so it adds no new direction and destroys independence. The correct process appends \(\mathbf{e}_1\), skips \(\mathbf{e}_2\), and returns the independent spanning list \(((1,1),\mathbf{e}_1)\).

The proof depends on testing each candidate against the current span, not just against the original list. Each accepted vector preserves independence relative to everything already selected. Each skipped vector remains representable by the final list. Those two facts establish the two defining requirements of a basis without relying on a dimension count.