Linear Dependence Lemma

This is out of my textbook, Axler's "Linear Algebra Done Right" which I am self-studying from. (I organized my thoughts in which I would like some sort of response with Roman Numerals).

Linear Dependence Lemma: If $(v_{1},\ldots,v_{m})$ is linearly dependent in $V$ and $v_{1} \neq 0$, then there exists $j \in \{2,\ldots,m\}$ such that the following hold:

(a) $v_{j} \in span(v_{1},\ldots,v_{j-1})$;

(I. Why does this need to be justified? Is it because $v_{j}$ is an "extra" vector, which would make this arbitrary set of linear combinations dependent?).

(b) If the $j^{th}$ term is removed from $(v_{1},\ldots,v_{m})$, the span of the remaining list equal $span(v_{1},\ldots,v_{m})$.

(II. My assumption is that this basically means that if we remove this extra vector, then we still have the same list of linear combinations).

(I also found the following proof a bit confusing and need some clarification).

PROOF: Suppose $(v_{1},\ldots,v_{m})$ is linearly dependent in $V$ and $v_{1} \neq 0$. Then there exists $a_{1},\ldots,a_{m} \in \mathbb{F}$, not all $0$ such that $$a_{1}v_{1}+\cdots+a_{m}v_{m} = 0$$.

(So far so good, from what I know, this is just stating the opposite of Linear Independence, where the only choice of $a_{1},\ldots,a_{m} \in \mathbb{F}$ that satisfies $a_{1}v_{1}+\cdots+a_{m}v_{m} = 0$ is $a_1 =\cdots= a_{m} = 0$)

CONT: Not all of $a_{2},a_{3},\ldots,a_{m}$ can be $0$ (because $v_1 \neq 0)$. Let $j$ be the largest element of $\{2,\ldots.,m\}$ such that $a_{j} \neq 0$. Then $$v_{j} = -\frac{a_1}{a_j}v_1 - \cdots - \frac{a_{j-1}}{a_j}v_{j-1} ,$$

proving (a).

(III. I will fill in the extra steps here because I feel that I may have the right idea).

$Span(v_{1},\ldots,v_{m}) = 0$ for $j \in \{2,\ldots,m\} = a_{1}v_{1} + \cdots + a_{j}v_{j} = 0$.

Here I just solved for $v_j$, and got the result $v_{j} = -\frac{a_1}{a_j}v_1 - \cdots - \frac{a_{j-1}}{a_j}v_{j-1} ,$ which corresponds to the above. $a_{j} \neq 0$ because we have $a_j^{-1}$ for each term, and $v_1 \neq 0$ because if we have $a_{1}v_{1}+\cdots+a_{j}v_{j} = 0$ then all the scalars $a_{2},\ldots,a_{m} \in \mathbb{F}$ could be equal to $0$, if that was the case. I think I have an idea, but how exactly does this prove that $v_j$ is contained in the span of $(v_{1},\ldots,v_{j-1})$? Is it because $-\frac{a_1}{a_j}v_1 - \cdots - \frac{a_{j-1}}{a_j}v_{j-1}$, is just a linear combination of vectors that is equal to $v_j$?

CONT: to prove (b), suppose that $u \in span(v_{1},\ldots,v_{m})$. Then there exists $c_{1},\ldots,c_m \in \mathbb{F}$ such that $$u = c_1v_1 + \cdots + c_mv_m$$.

In the equation above, we replace $v_j$ with the right side of 2.5, which shows that $u$ is in the span of the list obtained by removing the $j^{th}$ term from $(v_1,\ldots,v_m)$. Thus (b) holds. $\Box$

(IV. So how exactly does this work? I find this part the most confusing).

Sorry that this is such a long list, but I really want to fully understand everything I am learning, and I am pretty new to proving stuff, so I want to make sure that I improve that skill as well.

• for part 3 involving the linear dependence proof. Since $\frac{-a_i}{a_j}$ are all nonzero scalars in $F$ where $1\leq i \leq j-1$ then $v_j$ is a linear combination of those nonzero terms – user60887 Sep 13 '13 at 23:08
• Alright cool, that's what I was thinking. Thanks for that added clarification. – St Vincent Sep 13 '13 at 23:38
• Did you make a mistake here : "Linear Dependence Lemma: If (v1,...,vm) is linearly independent in V and v1≠0, then there exists j∈{2,...,m} such that the following hold" ? – shooting-squirrel Sep 14 '13 at 0:39
• I believe I did. Thanks for catching that. – St Vincent Sep 14 '13 at 0:43
• For a question about the (unnecessary) condition $v_1\neq0$, see What's special about the first vector? – Marc van Leeuwen Sep 15 '13 at 7:21

I. Why does (a) need to be justified

Because every claim made needs to be. The essence of (a) is that if there is a linear dependence, then there is a specific index $j$ such that the blame of linear dependence can be given to $v_j$, for its failing to be independent of its predecessors. A different way to prove this is to consider the list of sequences $()$, $(v_1)$, $(v_1,v_2)$, $\ldots$, $(v_1,v_2,\ldots,v_m)$; since the first one is linearly independent and the last one is linearly dependent (by assumption) there must be a first one in the list the is linearly dependent; if this is $(v_1,\ldots,v_j)$ then one can show $v_j\in span(v_1,\ldots,v_{-1})$. The argument is similar to the proof given in the text (a linear dependence relation among $(v_1,\ldots,v_j)$ must involve $v_j$ with nonzero coefficient). An advantage of this approach is that it does not depend essentially on any choice (the linear dependency taken is unique up to a scalar multiple) and it puts the blame on the very first $v_j$ that causes linear dependence.

II. My assumption is that (b) basically means that if we remove this extra vector, then we still have the same list of linear combinations.

More precisely, the removal of $v_j$ does not affect the set of vectors that can be written as linear combinations, even though the linear combinations themselves look different (since $v_j$ is no longer allowed to appear).

III. I will fill in... $span(v_{1},\ldots,v_{m}) = 0$ for $j \in \{2,\ldots,m\} = a_{1}v_{1} + \cdots + a_{j}v_{j} = 0$. Here I just solved for $v_j$, and got the result $v_j = -\frac{a_1}{a_j}v_1 - \cdots - \frac{a_{j-1}}{a_j}v_{j-1} ,$ which corresponds to the above. $a_{j} \neq 0$ because we have $a_j^{-1}$ for each term,

You've got that a bit backwards. You could only solve for $v_j$ under the assumption $a_j\neq0$; you cannot conclude that from the fact that you just solved for $v_j$.

and $v_1 \neq 0$ because if we have $a_{1}v_{1}+\cdots+a_{j}v_{j} = 0$ then all the scalars $a_{2},\ldots,a_{m} \in \mathbb{F}$ could be equal to $0$, if that was the case.

This is doubly beside the point. $v_1\neq0$ is given, you don't need to prove that. On the other hand there is nothing absurd in the scalars $a_{2},\ldots,a_{m} \in \mathbb{F}$ all being equal to $0$, except that the text had just proved it is not the case using the fact that $v_1\neq0$. But the author could have avoided the whole mess about $v_1$ by observing that $span()=\{0\}$.

I think I have an idea, but how exactly does this prove that $v_j$ is contained in the span of $(v_{1},\ldots,v_{j-1})$? Is it because $-\frac{a_1}{a_j}v_1 - \cdots - \frac{a_{j-1}}{a_j}v_{j-1}$, is just a linear combination of vectors that is equal to $v_j$?

Precisely.

In the equation above, we replace $v_j$ with the right side of 2.5, which shows that $u$ is in the span of the list obtained by removing the $j^{th}$ term from $(v_1,\ldots,v_m)$. Thus (b) holds. $\Box$

IV. So how exactly does this work?

If you write down a linear combination of $v_1,\ldots,v_m$ it contains a single occurrence of $v_j$. If you replace that occurrence (within parentheses, as it gets multiplied by a scalar) by the right hand side of 2.5, then there is no longer any occurrence of $v_j$. You don't directly get a linear combination of the remaining $v_i$, but once you work out the multiplication and collect like terms, you do get such a linear combination. For instance if $v_3=-5v_1+\frac32v_2$ then \begin{align} av_1+bv_2+cv_3+dv_4 &= av_1+bv_2+c(-5v_1+\frac32v_2)+dv_4 \\&= av_1+bv_2-5cv_1+\frac32cv_2+dv_4 \\&= (a-5c)v_1+(b+\frac32c)v_2+dv_4. \end{align}

• Awesome answer! – St Vincent Sep 15 '13 at 17:22
• Why is it that noting $span\{\} = {0}$ is important to justify that $v_1$ can also be zero? Does this include the case where our set of vectors is the null space? I'm not sure I understand that part fully. – St Vincent Sep 15 '13 at 18:27
• I'm just saying that the whole exception that is made in the statement of the lemma for $j=1$ is unnecessary: if the conclusion had included $j=1$ then one could drop the condition $v_1\neq0$ of the lemma; then the lemma and the proof would have been simplified. Indeed it could happen that we need to take $j=1$ in the conclusion precisely because $v_1$ happens to be $0$; this is OK since $0\in span()$. This question discusses that aspect in detail. – Marc van Leeuwen Sep 15 '13 at 19:54
• Okay, I think I get it now. Thanks. – St Vincent Sep 16 '13 at 5:36
• If $j = 1$, how would $v_j \in span(v_1,\ldots,v_{j-1})$ get rewritten? – St Vincent Sep 19 '13 at 18:10