# A basic question in linear Algebra

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?

-
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

## 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

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

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

-