0
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Anurag A
    Jun 17, 2019 at 18:47
  • 1
    $\begingroup$ Aren't you missing something? Are the $g$'s linearly independent? $\endgroup$
    – GReyes
    Jun 17, 2019 at 18:48
  • $\begingroup$ I am sorry, indeed I have missed that detail. $\endgroup$ Jun 17, 2019 at 18:53
  • 3
    $\begingroup$ 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$ ? $\endgroup$ Jun 17, 2019 at 19:21
  • $\begingroup$ the question should have been $l\leq k$. Otherwise one could choose $g_i = f_i$ for $i = 1,...,k$. $\endgroup$ Jun 18, 2019 at 18:42

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .