I saw the following proof of the fact that each finite spanning set $S$ of a vector space $V$ has a subset $B\subseteq S$, which is a basis of $V$.

Lemma. If $T$ is a minimal spanning set (i.e., $T$ is a spanning set and there is no spanning set which is a proper subset of $T$), then $T$ is a basis.

Proof. We have to show that $T$ is linearly independent. If not, then there is an $x\in T$ such that $x$ is a linear combination of $T\setminus\{x\}$. But then $T\setminus\{x\}$ is a spanning set which is a proper subset of $T$, contradicting the minimality of $T$.

Theorem. Let $S$ be a finite spanning set of $V$. Then there is a $B\subseteq S$ which is a basis of $V$.

Proof. Consider the following algorithm: if $S$ is linearly dependent, there is an $x$ such that $x$ is a linear combination of $S\setminus \{x\}$. In this case, set $S:=S\setminus \{x\}$ and repeat this step; else, stop.

At the end of the execution of the algorithm, $S$ is still a spanning set (because we only deleted redundant vectors). Also $S$ is then a minimal spanning set, because otherwise we would have deleted more vectors. Thus, by the lemma, $S$ is a basis.

My question: Is it really necessary to use the lemma? Doesn't the following argument suffice: Also $S$ is linearly independent, since otherwise, the algorithm wouldn't have ended.


It seems you're right. If the algorithm ended, the remaining set must be linearly independent. And it must end because there are only finitely many vectors in the spanning set.

  • $\begingroup$ Thank you for your answer! $\endgroup$ – user7280899 Apr 27 at 20:42
  • $\begingroup$ @user7280899 No problem. $\endgroup$ – Matt Samuel Apr 27 at 20:47

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.