# Should it have taken me three pages to prove this?

I'm in an introductory linear algebra class and I wanted to prove that all bases for a given space are of equal cardinality. As a step towards that, I proved the following:

Let $A$ be a finite set of vectors in a vector space $V$. Then there is no linearly independant set $B \subseteq Span(A)$ with $|B| > |A|$.

Using only the following assumptions, the proof took me three pages (at roughly 300 words per page):

1. That an operation that I defined during the proof is associative and distributive.
2. That $\mathbb{K}^n$ is a vector space with a basis of cardinality $n$.
3. A subset of a linearly independent vector set is linearly independent.
4. The relation "A generates B" over subsets of a vector space is transitive.

And possibly one or two other trivial assumptions that I didn't notice. I relied on no other definitions or theorems. The point is, should it have taken me three pages? Or did I miss a much shorter and simpler proof technique? Sorry if this is a bit of a soft question, I see my LinAlg professor once a week and he's a busy guy.

-
I'm trying to wrap around my head what exactly you're trying to prove in that remarked claim: is it that a set of vectors cannot generate a linearly independent (this is what I understand by "free" within this context) set of vectors which has a greater cardinality than its own? – DonAntonio Feb 17 '13 at 14:05
Yes. Sorry, is "free" not a standard synonym for "linearly independant"? It is in France, I must have gotten mixed up. If $A$ is a set of vectors, then $A$ cannot generate a linearly independant set $B$ such that $|B| > |A|$. – Jack M Feb 17 '13 at 14:26
Yes in fact. "Free generating set" for a vector space is the same as "linearly independent generating set" of the space. It just looked funny on writing, as the "free" thing usually gets used within this context later, and even then not that much imo. – DonAntonio Feb 17 '13 at 14:37
Do you know the Steinitz Exchange Lemma? That is the key here. – Math Gems Feb 17 '13 at 16:00

Ok, with the comment added by the OP I think I understand better now. We have the rather easy

Claim: If $\,A\,$ is a set of linearly independent (=l.i.) vectors in some linear space $\,V\,$, then for $\,v\in V\,$ we have that

$$v\in\operatorname{Span}\{A\}\Longleftrightarrow A\cup\{v\}\,\,\text{is not l.i.}$$

With the above claim your proposition follows at once, since any generated vector by $\,A\,$ lies in the span of $\,A\,$ and it is thus linearly dependent on elements of $\,A\,$ . In particular, the number of linearly independent elements in the span of $\,A\,$ cannot be greater than the cardinality of $\,A\,$....

-
That isn't what I'm claiming - I'll tighten up the wording in the OP. – Jack M Feb 17 '13 at 14:42
I don't understand: I'm just giving you some ideas to prove what you wanted in a shorter way than what you say you did. What did you mean "that" wasn't what you were claiming? – DonAntonio Feb 17 '13 at 14:45
Sorry, I misunderstood your answer. But how does my proposition follow from this? Note that when I say that A generates a linearly independent set B, I don't mean that the elements of B are linearly independent from A. I mean they're linearly independent from one another. – Jack M Feb 17 '13 at 15:05
Suppose $\,|A|=m\,$ and there exists a lin. ind. set $\,B\subset\operatorname{Span}{A}\,$ . Let $\,b\in B-A\,$ , then it certainly is true that $\,b\in\operatorname{Span}{A}\Longleftrightarrow A\cup\{b\}\,$ linearly dependent , and from this it follows that the amount of line. ind. vectors doesn't increase, and since this is true for any $\,b\,$ we're done. – DonAntonio Feb 17 '13 at 19:07
Doesn't this assume that A is a subset of B? If for example B and A are disjoint, then B - A is empty. – Jack M Feb 17 '13 at 23:24