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 ?

  • $\begingroup$ 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$ $\endgroup$ – onurcanbektas Sep 28 '17 at 17:58
  • $\begingroup$ What's the meaning of span({u_1,...u_{k}})? $\endgroup$ – 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).$$

  • $\begingroup$ Why the word 'maximal' is used here for $k$ ? If we remove that word, the statement still would make sense ? $\endgroup$ – User9523 Sep 29 '17 at 7:51
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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 ? $\endgroup$ – User9523 Sep 29 '17 at 7:20
  • $\begingroup$ @User9523 That's essentially the same: proving the contrapositive. $\endgroup$ – egreg Sep 29 '17 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.