# Exchange lemma for basis question

In the book I am referring (Jim Hefferon) Exchange Lemma for the basis is given as:

Assume that $B =\big< \overrightarrow{\beta_1}, \overrightarrow{\beta_2},...\overrightarrow{\beta_n}\big>$ is a basis for a vector space, and that for the vector $\overrightarrow{v}$ the relationship $\overrightarrow {v}$ = $c_1 \overrightarrow{\beta_1}+c_2\overrightarrow{\beta_2}+...+c_n\overrightarrow{\beta_n}$ has $c_i \neq 0$. Then exchanging $\overrightarrow{\beta_i}$ for $\overrightarrow{v}$ yields another basis for the space.

Intuitively speaking, we are replacing one of the elements of the basis (which is linearly independent by definition) with an element that is linear combination of other elements, so now the basis does not remain linearly independent and so is no more a basis, but it is not happening as per my argument, so what am I missing?

-
how do you it's not linear independent after replacement? – chaohuang Sep 4 '12 at 5:09
Briefly, $v$ is a linear combination of all of the $\overrightarrow{\beta_{i}}$, including the one we are discarding, and we need that discarded basis vector to get $v$ (since each $c_{i}\neq 0$). So it is not a linear combination of the other remaining basis vectors. – Kirk Boyer Sep 4 '12 at 7:21

In order to be a basis a set must be linearly independent and spanning. Replacing $\vec{\beta_i}$ with $\vec v$ gives you a linearly independent set, as if $$a_1\vec{\beta_1}+\cdots+a_{i-1}\vec{\beta_{i-1}}+a_i\vec{v}+a_{i+1}\vec{\beta_{i+1}}+\cdots+a_n\vec{\beta_n}=0$$ with some $a_j\neq 0$ then either $a_i=0$, and so the set $B\setminus \{\vec{\beta_i}\}$ is linearly dependent, or $$\vec{v}=\frac{a_1\vec{\beta_1}+\cdots+a_{i-1}\vec{\beta_{i-1}}+a_{i+1}\vec{\beta_{i+1}}+\cdots+a_n\vec{\beta_n}}{a_i}$$ so $\vec{v}$ can be expressed in two different ways as a linear combination of elements of $B$. Both of these contradict $B$ being linearly independent. Since $$\vec{\beta_i}=\frac{\vec v-c_1\vec{\beta_1}-\cdots-c_{i-1}\vec{\beta_{i-1}}-c_{i+1}\vec{\beta_{i+1}}-\cdots-a_n\vec{\beta_n}}{c_i}$$ it follows that $$\mathrm{Span}\{\vec{\beta_1},\ldots,\vec{\beta_{i-1}},\vec v,\vec{\beta_{i+1}},\ldots,\vec{\beta_n}\}=\mathrm{Span} B$$ hence $\{\vec{\beta_1},\ldots,\vec{\beta_{i-1}},\vec v,\vec{\beta_{i+1}},\ldots,\vec{\beta_n}\}$ is a basis.

-

Your statement that $v$ is a linear combination of the other basis elements (meaning $\beta_j$ with $j \ne i$) would be correct if $c_i = 0$. However, the assumption is that $c_i \ne 0$.

(Perhaps this should be a comment, but I don't yet have enough reputation to post comments.)

-

Hint: You can use the "relationship" to express $v_i$ as a linear combination of $v$ and the remaining $v_j$, or more informally to solve for $v_i$. At the end, you will have to divide by $c_i$, which is one reason that one must insist that $c_i\ne 0$.

So now if you have expressed a vector $u$ as a linear combination of $v_1,v_2,\dots, v_n$, you can express $u$ as a linear combination of $v$ and the $v_j$ with $j\ne i$. Just replace $v_i$ by the expression obtained in the first paragraph, and simplify.

We also need to show that $v$ and the $v_j$ with $j \ne i$ form a linearly independent set. If they are not, then some non-trivial linear combination of $v$ and the $v_j$ with $j\ne i$ is $0$. The coefficient of $v$ must be non-zero, else the $v_j$ would form a linearly dependent set. Replace $v$ by $c_1v_1+\cdots+c_nv_n$ and simplify. We get a non-trivial linear combination of $v_1,v_2,\dots, v_i,\dots, v_n$ is $0$, contradicting the fact that the set $\{v_1,\dots,v_n\}$ is a basis.

Remark: You would be right about the result not being a basis if we did not throw away $v_i$. But we do throw it away.

-