1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I'll say your proof is correct. $\endgroup$ – Fareed Abi Farraj Oct 12 '19 at 20:54
  • $\begingroup$ 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. $\endgroup$ – Will M. Oct 12 '19 at 20:54
  • $\begingroup$ 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)? $\endgroup$ – sandbag66 Oct 12 '19 at 20:59
  • $\begingroup$ 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. $\endgroup$ – Will M. Oct 12 '19 at 21:00
  • $\begingroup$ Is it possible to prove by contradiction? $\endgroup$ – sandbag66 Oct 12 '19 at 21:14
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand why we must conclude that they are equal. You could have multiple elements in B that are used in the same combination giving an element in G without contradiction the assumption, right? $\endgroup$ – sandbag66 Oct 12 '19 at 21:23
  • $\begingroup$ @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.) $\endgroup$ – saulspatz Oct 12 '19 at 21:31
  • $\begingroup$ Ok, but for the vectors in G to be linearly independent, mustn't the generators used to generate them be linearly independent of each other too? $\endgroup$ – sandbag66 Oct 12 '19 at 21:37
  • $\begingroup$ @sandbag66 I don't understand what you mean, nor what is has to do with the question. $\endgroup$ – saulspatz Oct 12 '19 at 22:31
  • $\begingroup$ 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. $\endgroup$ – sandbag66 Oct 12 '19 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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