# Linear Independence proof.

Let $S=\{u_1,u_2,......,u_n \}$ be a finite set of vectors, the objective is to show that $S$ is linearly dependent if and only if $u_1=0$ or $u_{k+1} \in span(\{u_1,u_2,......,u_k\})$.

First assuming $u_1=0$ or $u_{k+1} \in span(\{u_1,u_2,......,u_k\})$ and then implying $S$ is linearly dependent is trivial, now considering the converse.

Let $S$ is linearly dependent, that means a vector in $S$ say $u_k$ could be written as a linear combination of others or if we have $a_1u_1+a_2u_2+......+a_nu_n=0$ not all $a_i's$ are zero, say $a_k\ne0$.

So, if $a_1u_1+a_2u_2+...+a_ku_k+...+a_nu_n=0$ implies: $u_k=\frac{(-a_1)}{a_k}u_1+\frac{(-a_2)}{a_k}u_2+...+\frac{(-a_{k-1})}{a_k}u_{k-1}....+\frac{(-a_n)}{a_k}u_n$

Now the issue is how to prove $u_1=0$ or $u_{k+1} \in span(\{u_1,u_2,......,u_k\})$ from here. Why $u_1$ only ? Any vector could be zero and we wont necessarily have the last vector as the linear combination of the remaining ones..

Can anyone help ?

• I think the theorem can be stated more generally as : Let .... iff $\exists u_i$ in $\{u_1,u_2,......,u_n \}$ such that $u_i = \sum_{j \not = i} \lambda_j u_j$, because in this form it does not cover the case where, for example, $u_3 = u_1 + u_6$ – onurcanbektas Sep 28 '17 at 17:58
• What's the meaning of span({u_1,...u_{k}})? – Guillemus Callelus Sep 28 '17 at 18:26

First, if $u_1=0$, then you are done (the coefficient of $u_1$ is $1\neq 0$). So, assume $u_1\neq 0$. You can write $$0=a_1u_1+\cdots +a_nu_n$$ with not all $a_i=0$. Now, we may choose $k\geq 1$ maximal such that $a_{k+1}\neq 0$ (note that if $a_1\neq 0$, the fact that $u_1\neq 0$ implies some other $a_i\neq 0$). Therefore, we have $$0=a_1u_1+\cdots a_ku_k+a_{k+1}u_{k+1}$$ and, in turn $$u_{k+1}=-a_{k+1}^{-1}(a_1u_1+\cdots a_ku_k).$$

• Why the word 'maximal' is used here for $k$ ? If we remove that word, the statement still would make sense ? – User9523 Sep 29 '17 at 7:51
• No, it wouldn't. You would have something like $$u_j=-a_j^{-1}(a_1u_1+\cdots+a_{j-1}u_{j-1}+a_{j+1}u_{j+1}+\cdots+a_{k+1}u_{k+1}).$$ You cannot conclude from this that $u_j\in span(\{u_1,\ldots,u_{j-1})$, which is what you are trying to prove. – David Hill Sep 29 '17 at 14:29

The correct statement should be

$\{u_1,u_2,\dots,u_n\}$ is linearly dependent if and only if $u_1=0$ or there exists $k<n$ with $u_{k+1}\in\operatorname{span}\{u_1,u_2,\dots,u_k\}$.

The direction $\Leftarrow$ is easy: if $u_1=0$, then the set is clearly linearly dependent; otherwise we have $u_{k+1}=a_1u_1+\dots+a_ku_k$ and $$a_1u_1+\dots+a_ku_k+(-1)u_{k+1}+0u_{k+2}+\dots+0u_n$$ (the terms with the $0$ coefficients would be missing if $k=n-1$, of course). Since one of the coefficients in the linear combination is nonzero, as $-1\ne0$, we are done.

The key for $\Rightarrow$ is the following useful result, which you can prove separately:

if $\{u_1,u_2,\dots,u_k\}$ is linearly independent and $u_{k+1}\notin\operatorname{span}\{u_1,u_2,\dots,u_k\}$, then also $\{u_1,u_2,\dots,u_k,u_{k+1}\}$ is linearly independent.

Thus we can prove by easy induction that

If $u_1\ne0$ and, for all $k<n$, $u_{k+1}\notin\operatorname{span}\{u_1,u_2,\dots,u_k\}$, then $\{u_1,u_2,\dots,u_n\}$ is linearly independent.

• How about this approach: Let us consider the negation of the statement $u_1=0$ or $u_{k+1} \in span(\{u_1,u_2,......,u_k \})$ and then somehow extract some contradiction out of it ? – User9523 Sep 29 '17 at 7:20
• @User9523 That's essentially the same: proving the contrapositive. – egreg Sep 29 '17 at 7:26