Little lemma about number of linearly independent vectors

Question

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

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$. — Anurag A, Jun 17 '19 at 18:47
Aren't you missing something? Are the $g$'s linearly independent? — GReyes, Jun 17 '19 at 18:48
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$ ? — Mishikumo2019, Jun 17 '19 at 19:21
the question should have been $l\leq k$. Otherwise one could choose $g_i = f_i$ for $i = 1,...,k$. — Book Book Book, Jun 18 '19 at 18:42

score 1 · Answer 1 · answered Jun 17 '19 at 20:39

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.

score 1 · Answer 2 · answered Jun 17 '19 at 20:56

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.

Renat Sergazinov · Answer 3 · 2019-09-05T00:11:17.780

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.

Little lemma about number of linearly independent vectors

3 Answers3