Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following claim: Let $V$ be a vector space and let $A,B\subseteq V$ be two independent sets with $|A|<|B|<\infty $. Then there exists $b\in B$ such that $A\cup \{b\}$ is independent.

Can anyone prove this claim without using matrices?

share|cite|improve this question
Something like this might help. – Dylan Moreland Jun 13 '12 at 14:48
The basic result here is the (Steinitz) Exchange Lemma. A web search should turn up much, including that it generalizes from linear dependence to abstract dependence relations (e.g. algebraic dependence), cf. matroid theory. – Bill Dubuque Jun 13 '12 at 16:39

Since $\,|A|<|B|\,\,$ and both are lin. independent set, we get that $$\dim \operatorname{Span}(A)<\dim\operatorname{Span}(B)\,\,(**)$$

Now, we know that for any vector $$\,v\in V\,\,,\,v\in\operatorname{Span}(A)\Longleftrightarrow A\cup\{v\}\,\text{is linearly dependent}$$

So if $$\forall b\in B\,,\,A\cup\{b\}\,\text{is linearly dependent, then} \forall b\in B\,,\,b\in\operatorname{Span}(A)$$ which contradicts (**) above

share|cite|improve this answer
The claim in the question is used to prove the fact that the dimension of a space is well defined.... Using it to prove the claim gives a circular argument. – Shay Moran Jun 13 '12 at 17:55
Perhaps for you, @Shay. I didn't studied and learnt about dimension by means of this question or something like this, though perhaps The Replacement Theorem could be applied to both. – DonAntonio Jun 13 '12 at 18:30

Assume not:

Then if $|A| = n$, $|B| \geq n+1$, choose $n+1$ (linearly independent) elements $b_1, b_2, ..., b_{n+1}$ elements of $B$. If all $n+1$ elements are dependent with $A$, then the $n$ elements spanning $A$ span a $(n+1)$-dimensional space. Contradiction.

share|cite|improve this answer
How do you prove that n elements can not span n+1 independent element? This is the essence of the question... Also note that the fact we need to prove in this question is used to define the concept of dimension... – Shay Moran Jun 13 '12 at 17:58

I guess you can reduce to the case in which $|A| = |B|-1$, and then to the case $|A|=1$ and $|B|=2$. You can just add a vector $b$ to $A$ so that $\operatorname{span}\{A,b\}$ is a base for $B$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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