Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

3 Answers

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|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
add comment

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.