why I think wrong? Question:
Let $u_1, u_2, ...,u_k$ be vectors in $R^n$, and P a square matrix of order n. Show that if $Pu_1, Pu_2, ...,Pu_k$ are linearly independent, then $u_1, u_2, ..., u_k$ are independent. 
What I did was that I tried to induct
$c_1Pu_1+c_2Pu_2+...+c_kPu_k=0$ where $c_1=c_2=...=c_k=0$
to 
$c_1u_1+c_2u_2+...+c_ku_k=0$ where $c_1=c_2=...=c_k=0$
and I got stuck. 
However, my teacher gave the answer in the opposite direction. 
He inducted from 
Let $c_1u_1+c_2u_2+...+c_ku_k=0$
Then pre-multiply matrix P to both sides of the equation.
$P(c_1u_1+c_2u_2+...+c_ku_k)=P0$
then 
$c_1Pu_1+c_2Pu_2+...+c_kPu_k=0$
because $Pu_1, Pu_2, ...,Pu_k$ are linearly independent, so $c_1=c_2=...=c_k=0$
It worked! It was an amazing proof. But I was kind of wondering why two opposite thinking would result in so different results. I know I thought in the wrong direction. But I still didn't get the point so that I will not do wrong similarly. Can anyone provide some analysis? 
 A: It's a very common mistake starting a proof of linear independence by saying
$$c_1v_1+c_2v_2+\dots+c_kv_k=0\quad\text{where}\quad
c_1=c_2=\dots=c_k=0.$$
This is obvious and so it is never useful in this kind of proofs. What you want to prove is very different, namely that

the only case where $c_1v_1+c_2v_2+\dots+c_kv_k=0$ is when $c_1=c_2=\dots=c_k=0$

So, when you're given a statement such as

Prove that the vectors $v_1,v_2,\dots,v_k$ are linearly independent if (C)

where (C) stands for any particular condition in your problem, you should do according to the following pattern:

Suppose $c_1v_1+c_2v_2+\dots+c_kv_k=0$. Then …reasoning…, so we conclude that $c_1=c_2=\dots=c_k=0$. Therefore we have proved the vectors are linearly independent.


In your particular case you can say


*

*Suppose $c_1u_1+c_2u_2+\dots+c_ku_k=0$

*Then $P(c_1u_1+c_2u_2+\dots+c_ku_k)=P0$

*Therefore $c_1Pu_1+c_2Pu_2+\dots+c_kPu_k=0$

*Since $Pu_1,Pu_2,\dots,P_uk$ are, by hypothesis, linearly independent, we conclude that $c_1=c_2=\dots=c_k=0$

A: Basically you did not respect the correct order for proof.
What do you want to prove ?
That $u_1,u_2, \ldots ,u_n$ are independent.
So your proof MUST go like this :
(1) Suppose $c_1u_1+c_2u_2+ \ldots +c_ku_k=0$.
(2) Blah Blah Blah
(3) Therefore $c_1=c_2=c_3=\ldots =c_k=0$.
It seems you were confused and put item 1 in place 3.
A: You don't know elementary logic. Your problem: $(u_i)_i$ are given.
(H): if $\sum_ic_iPu_i=0$, then $(c_i)_i=(0)_i$.
(C): if $\sum_id_iu_i=0$, then $(d_i)_i=(0)_i$. Show that (H) implies (C).
Solution: 1. you rush on (C) and not to (H), otherwise you are dead !


*

*Now your hypothesis is: (H) and  $\sum_id_iu_i=0$ (hypothesis of (C)).

*$P(\sum_id_iu_i)=0=\sum_id_iP(u_i)$ and you apply (H) for $c_i=d_i$.
Notes: 1. Here we take $(c_i)=(d_i)$ but it is not true in general. Take always two different notations for these coefficients. 2. That is above is the standard method and if you don't understand that, you are dead again!
