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?

  • $\begingroup$ Are you dealing exclusively with finite dimensional vector spaces? $\endgroup$
    – M. Vinay
    Jun 9 '14 at 9:04

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.

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


$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.