1

In the book that I am using, Linear Algebra Done Right, the proof for the Steinitz exchange lemma (which can be found here) left me unconvinced.

The proof refers to the linear independence lemma. This is where my problem lies, the proof says that 'one of the vectors in this list is in the span of the previous ones'. I believe this should be 'at least one', as the LDL reads 'there exists'.

Related to this, why must that vector be one of the w's (the vectors that span V)? As I see it, it could be one of the u's too (the vectors that are linearly independent)! As an example, $((2,0,0),(0,2,0),(0,0,2),(1,1,1))$ certainly spans $\mathbb{R}^3$ and $((1,0,0),(0,1,0),(0,0,1))$ is certainly linearly independent in $\mathbb{R}^3$.

We add the $(1,0,0)$ to the first set and choose not to remove $(1,0,0)$, but a 'w', $(2,0,0)$ (I understand why LDL is correct so we can always do this). Now we have: $((1,0,0),(0,2,0),(0,0,2),(1,1,1))$. We then add $(0,1,0)$, but actually, even though $(1,0,0)$ and $(0,1,0)$ are linearly independent, $(0,1,0)$ is also in the span of the previous ones! So we could actually remove that one, so as I see it, what the proof says is incorrect.

Can someone point out my misunderstanding?

EDIT: So, I still find the formulation of the proof a bit sketchy. Krish' post inspired me to prove the lemma below formally. Hopefully it clears up things for some, as it did for me.

Lemma: If $(u_1,\dots,u_n,w_1,\dots,w_m)$ is a linearly dependent list of vectors, with $(u_1,\dots,u_n)$ linearly independent, then for some $i \in \left\{1,\dots,n\right\}$, $w_m$ is in the span of that initial list that remains after removing $w_i$.

Proof: Let $(u_1,\dots,u_n,w_1,\dots,w_j)$ be a list, where $w_j$ is chosen as high as possible such that the list is linearly independent. Then $(u_1,\dots,u_n,w_1,\dots,w_j,w_{j+1})$ is linearly dependent.

From linear dependence follows that $a_1u_1+a_2u_2+\dots+a_nu_n+b_1w_1+\dots+b_{j+1}w_{j+1} = \mathbf{0}$, for some $a_1,\dots,a_n,b_1,\dots,b_{j+1}$ not all zero. If $w_{j+1} = \mathbf{0}$, then the desired result follows. If not, then $b_{j+1} \neq 0$, as otherwise the equality would only be satisfied if $a_1,\dots,a_n,b_1,\dots,b_j$ would equal zero (because of linear independence).

Linear independence ensures that $u_1,\dots,u_n,w_1,\dots,w_j \neq \mathbf{0}$, and hence at least one of $a_1,\dots,a_n,b_1,\dots,b_j$ of must be nonzero. Now we can get $ w_{j+1}= - \frac{a_1}{b_{j+1}} u_1 - \frac{a_2}{b_{j+1}} u_2 - \dots - \frac{a_n}{b_{j+1}} u_n - \dots - \frac{b_1}{b_{j+1}} w_1 - \dots - \frac{b_j}{b_{j+1}} w_j $. Thus $w_{j+1}$ can be written as a linear combination of $u_1,\dots,u_n,w_1,\dots,w_j$, hence $w_{j+1} \in \mathrm{span}(u_1,\dots,u_n,w_1,\dots,w_j) \subseteq \mathrm{span}(u_1,\dots,u_n,w_1,\dots,w_j,w_{j+2},\dots,w_m).$ Q.E.D.

Community
  • 1
Bart Louwers
  • 213
  • $(0,1,0)$ is in the span of $((1,0,0),(0,2,0),(0,0,2),(1,1,1))$, but it isn't in the span of $((1,0,0))$. At this stage, $(1,0,0)$ is the only adjoined vector that originally belonged to the linearly independent list; what the proof correctly states is that any of the u's you add cannot be in the span of the previous u's you have already added. In your example, there is a w to remove; $(0,2,0)$ is in the span of $((1,0,0),(0,1,0))$. – Michael M Dec 21 '14 at 01:41
  • The proof first adds an $u_i$, and then looks at the whole set. It cannot be in the span of the u's already added, but it can be in the span of the u's already added together with the w's, as I demonstrated. – Bart Louwers Dec 21 '14 at 15:46
  • True, but that doesn't negate the proof. The idea is to take out one of the w's in the span of the previous u's and w's at each step, and at each step such a w has to exist. – Michael M Dec 21 '14 at 16:22

1 Answers1

2

Let $\{v_1, v_2, \cdots , v_n \}$ be a set of linearly dependent vectors of a vector space $V$ with $v_i \neq 0, \forall i = 1, 2, \cdots , n$. Then by Linear Dependence Lemma there exists a vector $v_i$ which can be written as a linear combination of rest of the $v_j$'s. But we can also choose a $v_i$ with the property that it can be written as a linear combination of $v_1, v_2, \cdots , v_{i-1}$ as follows: Start with $v_1.$ Surely it is linearly independent. Now consider $v_1, v_2.$ If the set $\{v_1, v_2 \}$ is linearly dependent, then we can write $v_2$ as a constant multiple of $v_1$. If the set $\{v_1, v_2 \}$ is linearly independent, then consider the set $\{v_1, v_2, v_3 \}$. If this set is linearly dependent then we can write $v_3$ as a linear combination of $v_1$ and $v_2$ (why?). If the set $\{v_1, v_2, v_3 \}$ is linearly independent then consider the set $\{v_1, v_2, v_3, v_4 \}$ and continue. Since the given set $\{v_1, v_2, \cdots , v_n \}$ is linearly dependent, at some stage you can find one $v_i$ with the above mentioned property.

Krish
  • 7,102
  • I understood why $v_3$ could be written as a linear combination of $v_1$ and $v_2$ if $(v_1,v_2,v_3)$ is linearly dependent, but your inductive argument left me unconvinced, because I did not see why that is true for any given step where we end up with a linearly dependent list! So I wrote a formal proof, so thanks for your inspiration. – Bart Louwers Dec 21 '14 at 17:35
  • @ultimatebowser: Yeah!! You got it right. The induction step is the one that you wrote in your post (in the Edit part). I was too lazy to write it completely. In my argument, you will ultimately end up with a set which is linearly dependent, because you start with a linearly dependent set. It can be that first $n-1$ elements are linearly independent. Then use the same argument as you used above. – Krish Dec 21 '14 at 17:45