# Help with the proof of the characterization of linearly dependent sets

In Lay - Linear Algebra, 3rd ed. ch 1.7, Theorem 7 states that

An indexed set $S = \{ \mathbf{v}_1, \dots , \mathbf{v}_p \}$ of two or more vectors is linearly dependent if and only if at least one of the vectors in $S$ is a linear combination of the others. In fact, if $S$ is linearly dependent and $\mathbf{v}_1 \neq \mathbf{0}$ , then some $\mathbf{v}_j$ (with $j > 1$) is a linear combination of the preceding vectors, $\mathbf{v}_1,\dots , \mathbf{v}_{j-1}$ .

The proof later on in the chapter proves the theorem from two "directions", starting with $\mathbf{v}_j$ in $S$ as a linear combination of the other vectors, and showing that if this is the case then $S$ must be linearly dependent. Then Lay proves the theorem from the other direction, namely supposing $S$ is linearly dependent first, and then showing that some $\mathbf{v}_j$ must be a linear combination of the other vectors.

The whole second part is shown here for context, but my problem is already in the second line (the rest is fine):

[...] suppose $S$ is linearly dependent. If $\mathbf{v}_1$ is zero, then it is a (trivial) linear combination of the other vectors in $S$. Otherwise, $\mathbf{v}_1 \neq \mathbf{0}$, and there exists weights $c_1 , \dots , c_p$ , not all zero, such that $$c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_p \mathbf{v}_p = \mathbf{0}$$ Let $j$ be the largest subscript for which $c_j \neq 0$. If $j=1$ , then $c_1 \mathbf{v}_1 = \mathbf{0}$, which is impossible because $\mathbf{v}_1 \neq \mathbf{0}$. So $j>1$, and \begin{align} c_1 \mathbf{v}_1 + \cdots + c_j \mathbf{v}_j + 0 \mathbf{v}_{j+1} + \cdots + 0\mathbf{v}_p = \mathbf{0} \\ c_j \mathbf{v}_j = -c_1 \mathbf{v}_1 - \cdots -c_{j-1} \mathbf{v}_{j-1} \\ \mathbf{v}_j = ( - \frac{c_1}{c_j} \mathbf{v}_1 ) + \cdots + ( -\frac{c_{j-1}}{c_j} ) \mathbf{v}_{j-1} \end{align}

Now, my concern here is quite trivial really (pun sort of intended). In the second line of the proof above, if $\mathbf{v}_1$ is zero, why must it be a trivial linear combination of the other vectors in $S$? Since $S$ is here defined to be linearly dependent, can't we find weights $c_1, \dots , c_p$ not all zero so that $$c_1 \mathbf{v}_1 = c_2 \mathbf{v}_2 + \cdots c_p \mathbf{v}_p$$, where $\mathbf{v}_1 = \mathbf{0}$? Or is it that $\mathbf{v}_1$ is the defining factor that determines the linear dependence of $S$? There is something here I just can't see. Maybe it's too late.

Sorry for the long post! I wasn't sure how much context would be appropriate. If somebody knows how to clean up the multiline code in the proof then I'd appreciate that.

• When you have a set of $n$ vectors and if one of the them is the zero vector they are going to be linearly dependent: Set the coefficients of the other vectors to be zero and any non-zero constant for the zero vector. – user38268 Aug 30 '11 at 21:32
• @D B Lim: Thank you! That makes perfect sense! – Jodles Aug 30 '11 at 21:47

The point is not that $\mathbf v_1$ must be a trivial linear combination of the other vectors, as you rephrased it, but that it is. That's enough to show that at least one of the vectors is a linear combination of the others.

Also, we did find weights $c_1,\dotsc,c_p$, not all zero, so that $c_1 \mathbf{v}_1 = c_2 \mathbf{v}_2 + \cdots c_p \mathbf{v}_p$, namely $c_1=1$, $c_2=\dotso=c_p=0$.

• Sorry, I didn't mean to rephrase it. Do you mean that we're simply saying that v_1 is a trivial linear combination in this case; and that it could just as fine be a non-trivial combination as well (but for the sake of the proof we're assuming the former)? – Jodles Aug 30 '11 at 18:35
• @Jodles: Yes, except we're not assuming the former, we know it, whereas we don't know whether there are also other combinations. – joriki Aug 30 '11 at 18:42
• Thank you! I think I got it! Now the point with the second part, where v_1 is not zero, is that then not all numbers c_2 -> c_p can be zero (for it to be linearly dependent), which in turn leads to the fact that v_j is a linear combination of the preceding vectors... Have I kind of got it? I have at least got what I initially asked for, so I'm marking your post as the answer:) – Jodles Aug 30 '11 at 21:45

The following exercises will strengthen your understanding of the concepts you asked above.

$\textbf{Exercise 1:}$ Suppose we have a set of $n$ vectors that spans some "space" V, viz. every vector in $V$ can be written as a linear combination of these vectors. I am using "space" because I don't know if you have done vector spaces or not. Prove that a set of vectors that spans $V$ can always be reduced to a basis for $V$.

Definition: A set of $n$ vectors is said to form a basis $B$ of a "space" $V$ if they are linearly independent and any vector in $V$ can be expressed as a linear combination of these basis vectors.

$\textbf{Exercise 2:}$ Suppose there are $n$ vectors in a basis $B$ of a "space" $V$. Prove that any set of $n+1$ vectors in $V$ will be linearly dependent.

I can give you more exercises but I am not sure of the material you have covered in class. By "space" I mean of course a vector space, you can read about it in Lay's textbook I am sure.

$\textbf{Edit:}$ This is just a personal opinion, but I think that studying linear algebra from the point of view of Lay is just painful. They give the impression that linear algebra is all about matrices. You should look up Sheldon Axler's Linear Algebra Done Right. Minimal use of matrices, but I must say that the proofs are more abstract as they look at linear algebra from the point of view of linear maps.

Example, in Lay they prove that the dimension of the column space of a matrix must equal the dimension of the row space. In Lay you have to go through this horrible process of row reduction, reduced row echelon form, etc.

But then you notice that if $T$ is a linear transformation between vector spaces $V$, $W$ and $K$ its null space, then $V = K \oplus K^{\perp}$. Apply rank nullity and the fact that $K^{\perp} =$ Im $T^T$ and you're done. The point I am saying is that linear algebra with operators and not matrices just seems way more smooth and elegant. Lay does not do a good job at putting that across.

• Thanks D B Lim! +1! Vector spaces are the next chapter in the book, so I'll have a go at these once I've had a look in that chapter. – Jodles Aug 31 '11 at 7:18
• @Jodles Please see my extended answer above that I have edited. – user38268 Aug 31 '11 at 7:30
• @D B Lim: Thank you D B Lim! You're right, Lay has given me the impression that linear algebra is mostly about matrices... I'll pick the book up at my library right away! Thank you for the helpful suggestion! – Jodles Aug 31 '11 at 8:05

Carefully looks at the theorem 7, it proves two statements: 1. linearly dependent ⇔ linear combination. 2. linearly dependent & $V_1\neq0 \Rightarrow V_j$ is a linear combination of preceding.

Notice that,

1. linearly dependent is consisted by two mutually exclusive parts(linearly dependent & $V_1\neq 0$, linearly dependent & $V_1=0$),
2. and $V_j$ is a linear combination of preceding ⇒ linear combination.

So the theorem is equal to prove three statements:

1. linear combination $\Rightarrow$ linearly dependent.
2. linearly dependent & $V_1=0 \Rightarrow$ linear combination.(trival linear combination: $V_1 = 0V_2 + ... +0V_p$, notice that $S - V_1$ can be linearly independent, so this trivial solution is the only one that satisfy all $S$ that is linearly dependent & $V_1=0$)
3. linearly dependent & $V_1\neq 0\Rightarrow V_j$ is a linear combination of preceding ⇒ linear combination.