7
$\begingroup$

Does the Linear Dependence Lemma imply that there are always at least TWO possible vectors of which one can be removed from a linearly dependent list without changing the span?

The Linear Dependence Lemma as presented in Axler, Linear Algebra Done Right (3rd Edition): Linear Dependence Lemma (Axler, Linear Algebra Done Right 3rd Edition)

It seems to me that there exist at least 2 such $j$, because if $v_{j}$ is in the span of the other vectors in the list then it can be written as a linear combination of those others, (i.e., $v_{j}=a_{1}v_{1}+a_{2}v_{2} +...+ a_{m}v_{m}$). And if so, then by rearranging terms between RHS and LHS you could always specify at least one other $v$ in terms of $v_{j}$ (and assuming $v_{j} \neq 0$ then at least one $a$ is also $\neq 0$). In which case you could remove that $v$ from the list without changing the span. So there should always be at least 2 candidates for removal from a linearly dependent list without changing the span, right?

Perhaps this is obvious, but I want to make sure I'm not missing something.

Any and all feedback is welcome. Thanks!

$\endgroup$
0

3 Answers 3

7
$\begingroup$

No there isn't necessary multiple of this j because of (a)

For example in the List (1,0) (0,1) (1,1) you can leave out any of these and the span isn't changing but (a) says that the span of the first j-1 vectors contain the j-th vector. That is only true for the third vector in this case

$\endgroup$
5
  • $\begingroup$ I don't actually understand the argument you're making. The question's asking whether there's more than one choice of which you can out, you say that you can leave any one of them out in your example, but you're saying “no” to the title question using that example as demonstration. $\endgroup$
    – wizzwizz4
    Oct 7, 2023 at 16:00
  • 3
    $\begingroup$ The question is asking if there is more than choice for j. That is different from the question if there is more than one choice of which you can out, because the j-th vector has to be in the span of the first j-1 vectors. $\endgroup$
    – Etoplay
    Oct 7, 2023 at 16:20
  • 1
    $\begingroup$ Okay, I see what you mean: the distinction you're making is worth making. It might be worth clarifying your answer. $\endgroup$
    – wizzwizz4
    Oct 7, 2023 at 16:27
  • $\begingroup$ Thanks. This does clarify the fact that as posed the original question conflates two issues: the use of $j$ and the possibility of multiple candidates for removal without changing the span. (I’ve elaborated in my comment on the post from @QiaochuYuan above). $\endgroup$
    – NAD
    Oct 7, 2023 at 17:47
  • $\begingroup$ This answer interprets the question as: are there always more than one js (j1, j2, ...) that satisfiy both (a) and (b). However, I would interpret the question, as posed atm, as: assuming (a) is met, is the j-th term the only candidate that can be removed from v1,...,vm. This is because the question starts with "if vj is in the span of the other vectors in the list then it can be written as a linear combination of those others". I'd say this (as considered in the answer ab.) is also an interesting interpretation, but it may better to rewrite the question if this is the intended interpretation. $\endgroup$ Oct 7, 2023 at 20:32
6
$\begingroup$

This is almost right. It's correct if you're also guaranteed that $v_1, \dots v_m$ are all nonzero. A more symmetric way to say it is that a nontrivial linear dependence between nonzero vectors always involves at least two vectors, and you can remove any vector that appears in such a dependence.

However, it could happen that, for example, $v_1 = 0$ and $v_2, \dots v_m$ are linearly independent. In that case $v_1$ is the only vector that can be removed.

$\endgroup$
9
  • 4
    $\begingroup$ QiaochuYuan - I initially read it the same way as your answer, but if you check part a) closely, as in the answer by @Etoplay, you'll see that they take the vectors in order, one by one, and $j$ identifies the location of the first dependence. So, while you and the OP are saying true (and useful) things, the lemma does define a unique $j$, even if one of the vectors is $0$. $\endgroup$
    – JonathanZ
    Oct 7, 2023 at 14:03
  • 1
    $\begingroup$ Ah, you're right, I misread condition a). $\endgroup$ Oct 7, 2023 at 14:55
  • 2
    $\begingroup$ Thank you all! So it seems there are two issues here: 1) because of the way the Lemma is constructed list-order matters and so there is not necessarily more than one $j$ (where $j$ is referring specifically to the list order in the lemma), BUT more generally 2) in a case of nontrivial linear dependence within a list of non-zero vectors there are always at least 2 vectors either of which can be removed without changing the span of the list. Is this accurate? And if so, without reference to $j$, would the answer to the question as posed in the title be “yes”? $\endgroup$
    – NAD
    Oct 7, 2023 at 17:43
  • 1
    $\begingroup$ …with Qiaochu’s original caveat regarding zero vectors. $\endgroup$
    – NAD
    Oct 7, 2023 at 17:52
  • 2
    $\begingroup$ @NAD: yes, that's right. $\endgroup$ Oct 7, 2023 at 18:06
0
$\begingroup$

If these vectors are linearly dependent, then there exists $ a_1, \ldots, a_m \in \mathbb { F } $ and $ j \in \left\{ 1,... m \right\} $ where $ a_j \neq 0 $ such that $ \sum _ { i = 1 } ^ m a_i v_i = 0 $

Since this $a_j \neq 0$, then $1/a_j$ exists and then we can write

$$ v_j = -\frac{a_1}{a_j}v_1 - ... - \frac{a_{j - 1}}{a_j}v_{j - 1} $$

(Just as Axler tells you in the proof)

In other words it can be written as a linear combination of those others: $$v_{j}=b_{1}v_{1}+b_{2}v_{2} +... + b_{j - 1} v_{j - 1} + \qquad + b_{j + 1} v_{j + 1} + ... + b_{m}v_{m}$$

Then from our initial equation, we would have $$a_1 v_1 + ... + a_{j - 1} v_{j - 1} + a_j ( b_{1}v_{1}+b_{2}v_{2} +...+ b_{m}v_{m} ) + a_{j + 1} v_{j + 1} + ... + a_m v_m = 0$$

Which is equivalent to $$(a_1 + a_j b_1) v_1 + ... + (a_{j - 1} + a_j b_{j - 1}) v_{j - 1} + \qquad + (a_{j + 1} + a_j b_{j + 1}) v_{j + 1} + ... + (a_m + a_j b_m) v_m = 0$$

So in simpler terms we have $$c_1 v_1 + ... + c_{j - 1} v_{j - 1} + \qquad + c_{j + 1} v_{j + 1} + ... + c_m v_m = 0$$

There are two options at this point, either all the $c_k$'s are zero, and we don't know anything else, or at least one of the $c_k$'s are non-zero, therefore we know that $v_1, ..., v_{j - 1}, \qquad, v_{j + 1}, ..., v_m$ are linearly dependent, and we can perform the same procedure again.

Note that in the latter case in the above paragraph yes, we can find a second vector that can be removed.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .