# Little lemma about number of linearly independent vectors

Let $$f_1, f_2, ... , f_k$$ be linearly dependent vectors in a vector space. Let $$g_1,g_2,...,g_l$$ each be linear combination of the vectors $$f_1, f_2, ... , f_k$$. If $$g_1,g_2,...,g_l$$ are linearly independent, then I need to prove that $$l.

I have tried using pigeon hole principle and doing stuff with coefficients to prove contrapositive, but no success. Any hint would be appreciated.

• Something is missing here otherwise your question is incorrect. For example, take $f_1=(1,0)$ and $f_2=(0,1)$, then we can take $g=(a,b)$ and we will have infinitely many vectors $g_i$. So $l=\infty$ and $k=2$. Jun 17, 2019 at 18:47
• Aren't you missing something? Are the $g$'s linearly independent? Jun 17, 2019 at 18:48
• I am sorry, indeed I have missed that detail. Jun 17, 2019 at 18:53
• If $(f_1,...,f_n)$ are linearly independant, and $f_i=g_i$, then $l=k$... Maybe you try to prove that $l\le k$ ? Jun 17, 2019 at 19:21
• the question should have been $l\leq k$. Otherwise one could choose $g_i = f_i$ for $i = 1,...,k$. Jun 18, 2019 at 18:42

Let's work towards the contrapositive, for which it suffices to show that any $$k$$ vectors $$g_i$$ which are linear combinations of the $$f_i$$ will be linearly dependent.

Write $$g_i = \sum_{j=1}^k a_{ij} f_i$$ with $$a_{ij}$$ elements of the field.

We can write this concisely in matrix notation as

$$A F = G$$ where $$A$$ is the $$k \times k$$ matrix with $$ij$$th coefficient $$a_{ij}$$ and $$F,G$$ are column vectors with $$i$$th entries $$f_i, g_i$$ respectively.

MAIN HINT Now to finish the proof, divide into two cases depending on whether $$A$$ is invertible or not. You can construct a linear dependency for the $$g_i$$ (i.e. a row vector $$C$$ such that $$CG =0$$) from either a linear dependency for the $$f_i$$ or for the columns of $$A$$, depending on the case.

I was going to write a proof but I found this thread which contains many elegant proofs. So I deleted my written up part and leave it to here:

n+1 vectors in $\mathbb{R}^n$ cannot be linearly independent

It is readily adaptable to your question. Use your $$g$$ as their $$f$$ and your $$f$$ as their $$e$$.

It's a simple evident fact however the different proofs are themselves interesting. People use induction, basis, algebra etc. It is a nature of linear algebra: many things are equivalent.

After thinking a while about this question, this is what came to my mind. There is another well-known theorem that if $$g_1, ..., g_l$$ are linearly independent and are each linear combination of $$f_1, ..., f_k$$, then it must be that $$l \leq k$$.

Now in my question, we have that $$f_1, ..., f_k$$ are linearly dependent. This means that there exists vector $$f_i$$ for some $$i \in {1, ... , k}$$ such that $$f_i$$ is a linear combination of the rest of the vectors. Hence, we can express $$g_1, ..., g_l$$ as a linear combination of $$f_1,..., f_{i-1}, f_{i+1}, ..., f_k$$. Now apply the above-stated theorem to get that $$l \leq k-1$$. Hence, we conclude that $$l < k$$.

The theorem stated in the beginning can be found in Gelfand’s book on linear algebra.