# Number of generators greater than the number of vectors

Show that if we pick in a vector space a set of generators and a set of linearly independent vectors that the number of generators is greater than or equal to the number of linearly independent vectors.

My question is whether or not the proof I came up with for this is (a) correct, (b) too convoluted:

Proof:

Take a vector space $$V$$.

Let $$B = \left\{e_1,e_2,...,e_n\right\} \subset V$$ where the elements of $$B$$ are generators of $$V$$ and $$G = \left\{v_1,v_2,...,v_k\right\} \subset V$$ where the elements of $$G$$ are linearly independent vectors.

By the definition of systems of generators, any vector in a vector space can be expressed as a linear combination of generators. So any element in $$G$$ can be expressed as a linear combination of elements in $$B$$.

Since the elements of $$G$$ are linearly independent of one another, it follows that each $$v_i \in G$$ is given by a linear combination of a unique subset of elements of $$B$$; that is no single element of $$B$$ is used in any more than one linear combination of elements giving a vector in $$G$$.

Assume that $$\#B < \#G$$. This contradicts the above since there will be at least one element in $$B$$ which is used in more than one linear combination that gives an element of $$G$$, contradicting the uniqueness of these combinations.

$$\therefore \#B \geq \#G$$ by contradiction. $$\square$$

• I'll say your proof is correct. – Fareed Abi Farraj Oct 12 '19 at 20:54
• This is not a proof, this is a hand-wavy argument to convince yourself and a friend. It can be made a proof using induction, though. – Will M. Oct 12 '19 at 20:54
• What must I show mathematically when using induction to prove this? Something to do with $a_1e_1 + a_2e_2 + ...$(where $a_i$ is some constant)? – sandbag66 Oct 12 '19 at 20:59
• Use induction in $n$ and show that $\#G \leq n.$ $n = 1$ is obvious. On a side note, I find it amusing how I said this is not a proof at all and other people say it was a correct proof. Generally speaking, I am quite formal, so it is expected I wouldn't take an argument like this as a proof. At the end, it boils down to who is marking you. If it were someone like me, I'd give you 1 mark for trying. – Will M. Oct 12 '19 at 21:00
• Is it possible to prove by contradiction? – sandbag66 Oct 12 '19 at 21:14

The proof is not correct. The statement that no element of $$B$$ can be used in more than one linear combination giving a vector of $$G$$ is not true. Suppose $$B$$ and $$G$$ are two different bases of $$V$$. If we accept your statement, we must conclude each element of $$G$$ is a scalar multiple of some element of $$B$$, which is false.
• @s If $B$ and $G$ are both bases, they have the same number of elements. If you can use each element of $B$ only once, they you can't use more than one. So each element of $G$ is a scalar multiple of an element of $B$. (I said the bases are the same; that was a mistake, which I'll correct.) – saulspatz Oct 12 '19 at 21:31
• Ignore that last comment; what I meant to ask was: if the statement that "no element of $B$ can be used in more than one linear combination giving a vector of $G$" is false, then what is the true condition? I don't know. – sandbag66 Oct 12 '19 at 22:45