# Prove that there is a subset of $T$, which, together with $S$, is again a basis of $E$.

Suppose $S$ is a set of linearly independent vectors in $E$, and suppose $T$ is a basis of $E$. Prove that there is a subset of $T$, which, together with $S$, is again a basis of $E$. --Linear Algebra by Werner Greub.

Where should I start with please?

• Are you dealing exclusively with finite dimensional vector spaces? Jun 9 '14 at 9:04

## 2 Answers

I'll assume your space $E$ is finite dimensional.

I'll do it by induction. Let $S=\{v_1,\dots,v_m\}$ and, for $0\le k\le m$, set $$S_k=\{v_j:1\le j\le k\}.$$ In particular, $S_0=\emptyset$.

We'll prove that, if $k\le n$, where $n=\dim E$, there is a subset $T_k$ of $T$ such that $S_k\cup T_k$ is a basis of $E$.

The base step consists in choosing $T_0=T$. Now suppose we have the thesis for $k$; if $k=n$, we are done, so we can suppose $k<n$.

By the induction hypothesis, $$v_{k+1}=\alpha_1 v_1+\dots+\alpha_k v_k+\beta_1 w_1+\dots+\beta_{n-k}w_k$$ where $T_k=\{w_1,\dots,w_{n-k}\}$. One of the coefficients $\beta_1,\dots,\beta_{n-k}$ must be nonzero, since $S$ is linearly independent. We can rename the indices so that $\beta_1\ne0$, which allows us to write the above relation as $$w_1=\alpha_1'+\dots+\alpha_k'+\alpha_{k+1}'v_{k+1}+\beta_2'w_2+\dots+\beta_{n-k}'w_{n-k}$$ It's easy to prove now that $T_{k+1}=\{w_2,\dots,w_{n-k}\}$ is a good choice for completing our task.

• What if I tell you that E is infinite dimensional? Jun 9 '14 at 10:44
• @pxc3110 The claim wouldn't be true, IIRC. Jun 9 '14 at 11:51
• how can I prove that $T_{k+1} \cup S_{k+1}$ generates E? Apr 2 '20 at 16:22
• @jacques99 It is a linearly independent set with $n$ elements. Apr 2 '20 at 16:33
• and why they are linearly independent? Apr 2 '20 at 16:36

This is problem 9 of section §3 of Chapter 1 in the last (4th) edition of Greub's "Linear Algebra". Here's my answer:

(Note that the case of finite $$S$$ amounts to Steinitz's replacement theorem).

Let $$Z$$ be the subspace of $$E$$ generated by $$S$$. If $$Z=E$$, then we may take $$\emptyset\subseteq T$$ and we are done. So assume $$Z\subsetneq E$$. It follows that some element of $$T$$ lies outside $$Z$$ (otherwise any vector in $$E$$, being a linear combination of the elements of $$T$$, would also lie in $$Z$$, contradicting $$Z\subsetneq E$$), say $$v\in T\smallsetminus Z$$.

Let $$\mathscr{M}(T,Z) \doteq\left\{ T'\subseteq T\mid T'\text{ is linearly independent mod }Z\right\}$$.

It is clear that $$\left\{ v\right\} \in\mathscr{M}(T,Z)$$ (since $$v\notin Z$$, we have $$\lambda v\in Z\iff\lambda=0$$), so $$\mathscr{M}(T,Z)$$ is nonempty. Now $$\mathscr{M}(T,Z)$$ is partially ordered by inclusion, and every chain $$\mathscr{C}_{i}\subseteq\mathscr{M}(T,Z)$$ has an upper bound $$\bigcup_{T'\in\mathscr{C}_{i}}T'$$. Indeed, every finite subset of $$\bigcup_{T'\in\mathscr{C}_{i}}T'$$ is contained in some element of the chain $$\mathscr{C}_{i}$$ and hence linearly independent $$\text{mod }Z$$, so $$\bigcup_{T'\in\mathscr{C}_{i}}T'$$ is itself linearly independent $$\text{mod }Z$$, whence $$\bigcup_{T'\in\mathscr{C}_{i}}T'\in\mathscr{M}(T,Z)$$. It follows by Zorn's lemma that there's a maximal element (with respect to inclusion) of $$\bigcup_{T'\in\mathscr{C}_{i}}T'\in\mathscr{M}(T,Z)$$, call it $$T'_{\Omega}$$. Now take any $$x\in E\smallsetminus T'_{\Omega}$$. Then, by maximality of $$T'_{\Omega}$$, the set $$T'_{\Omega}\cup\left\{ x\right\}$$ must be linearly dependent $$\text{mod }Z$$, so for some scalars $$\xi^{v}$$, not all zero, we have:

$$\xi x + \sum_{x_{v}\in T'_{\Omega}}\xi^{v}x_{v}\in Z$$.

But if we had $$\xi=0$$, it would follow that, for some scalars $$\xi^{v}$$, not all zero, we have $$\sum_{x_{v}\in T'_{\Omega}}\xi^{v}x_{v}\in Z$$, contradicting the linear independence $$(\text{mod }Z)$$ of $$T'_{\Omega}$$. Hence $$\xi\neq0$$. It now follows that

$$\xi x-\sum_{x_{v}\in T'_{\Omega}}(-\xi^{v})x_{v}\in Z$$

$$x-\sum_{x_{v}\in T'_{\Omega}}\xi^{-1}(-\xi^{v})x_{v}\in Z$$.

Let $$z\in Z$$ be the left side in the last display. Then, for any $$x\in E\smallsetminus T'_{\Omega}$$, and setting $$\eta^{v}=(\xi^{x})^{-1}(-\xi^{v})$$, we have:

$$x=\sum_{x_{v}\in T'_{\Omega}}\eta^{v}x_{v}+z$$

$$x=\sum_{x_{v}\in T'_{\Omega}}\eta^{v}x_{v}+\sum_{y_{w}\in S}\alpha^{w}y_{w}$$

for some scalars $$\alpha^{w}\in\varGamma$$. Thus $$T'_{\Omega}\cup S$$ generates all $$x\in E\smallsetminus T'_{\Omega}$$. But, trivially, it generates all of $$T'_{\Omega}$$ as well. So $$T'_{\Omega}\cup S$$ is a system of generators for $$E$$. Now suppose that

$$\sum_{x_{v}\in T'_{\Omega}}\beta^{v}x_{v}+\sum_{y_{w}\in S}\gamma^{w}y_{w}=0$$

Then

$$\sum_{x_{v}\in T'_{\Omega}}\beta^{v}x_{v}=-\sum_{y_{w}\in S}\gamma^{w}y_{w}\in Z$$

so, since $$T'_{\Omega} \in \mathscr{M}(T,Z)$$ is linearly indepedent $$\text{mod } Z$$, we have

$$\sum_{x_{v}\in T'_{\Omega}}\beta^{v}x_{v}=0$$. Since $$T'_{\Omega}\subseteq T$$, it is a linearly independent set, so all $$\beta^{v}$$'s are zero. Since $$S$$ is also linearly independent, this in turn implies that all $$\gamma^{w}$$'s are zero as well. So the system of generators $$T'_{\Omega}\cup S$$ is linearly independent, and hence a basis. This completes the proof.