# Proving a lemma about the union of set, linear independence, spans

OK, here's another lemma I'm being asked to prove and I am trying to see if I am in the right ballpark.

Let $L$ = {$y, y_1, y_2, y_3,..., y_m$} be a linearly independent subset of $V$, a vector space over field $K$.

Let $S$ = {$x_1, x_2,...,x_r$} be a subset of $V$ such that

{$y_1, y_2,...,y_m, x_1, x_2, x_3,...,x_r$} = ($L$ - {$y$}) $\cup\ S$ spans $V$.

Show $\exists$ an element $x_i\in\ S$ s.t. $L \cup\$($S$ - {$x_i$}) = {$y, y_1, y_2,..., y_m, x_1, x_2, x_3, ...,x_{i-1}, x_i, x_{i+1}, x_n$} spans $V$.

I approached it like this:

Given that ($L -${$y$}) $\cup\$ $S$ spans $V$ , that means that $y$ is linearly dependent, and thus a linear combination of $L \cup\ S$, so it can be expressed:

$y = \lambda_1y_1 + \lambda_2y_2 + ... \lambda_m y_m + \mu_1x_1 + \mu_2x_2+ ... \mu_rx_r$

by construction L is a linearly independent set, $\exists$ scalars $c$ such that $cy + c_1y_1 + c_2y_2 + ... c_my_m = 0$

But since we have L as linearly independent, that means the coefficients have to be zero. That's true for both L as a linearly independent set with scalar coefficient $c$ and $\lambda_i$.

That in turn reduces $y = \lambda_1y_1 + \lambda_2y_2 + ... \lambda_m y_m + \mu_1x_1 + \mu_2x_2+ ... \mu_rx_r$ to $y = \mu_1x_1 + \mu_2x_2+ ... \mu_rx_r$

But y isn't linearly independent. That means at least one of the coefficients $\mu_i \neq 0$ therefore there is some element $x_i \neq 0$

The span of V is the set of all vectors in V. And we're trying to show that the union of L and S with that nonzero $x_i$ subtracted is the span of V. But that's where I get a little stuck; I know I've almost got the last step.

(also, any critique o how to write this proof "properly" is much appreciated).

• In the right ballpark... lol :) – Patrick Da Silva Jun 20 '13 at 4:36
• "by construction L is a linearly independent set, $\exists$ scalars c such that " That's the opposite. By linear independence, the only possibilities for $c, c_1, \dots, c_m$ is $c = c_1 = \dots = c_m = 0$. I know that's what you wrote, but you're kind of saying stuff for nothing there. – Patrick Da Silva Jun 20 '13 at 4:46

You don't know that $\{ y, x_1, \dots, x_r \}$ is a linearly dependent subset! You are misunderstanding the definitions. The problem is that when you write $$y = \lambda_1 y_1 + \dots + \lambda_m y_m + \mu_1 x_1 + \dots + \mu_r x_r,$$ you cannot assume that all coefficients $\lambda$ will be zero. Think of $V = \mathbb R^2$ with basis $\{e_1,e_2\}$, $L = \{ e_1, e_2 \}$ and $S = \{e_1 + e_2\}$ and see what happens with your equations.
The right proof would go like this : since $\{ y_1,\dots,y_m , x_1, \dots, x_r\}$ spans $V$, we have $$y = \lambda_1 y_1 + \dots + \lambda_m y_m + \mu_1 x_1 + \dots + \mu_r x_r,$$ and we cannot have all $\mu_i$'s equal to zero, because this would give a linear dependence on the set $\{y,y_1,\dots, y_m\}$. Therefore one of the $\mu$'s is not zero. Say $\mu_i \neq 0$. Then $$x_i = \frac {-1}{\mu_i}\left( \lambda_1 y_1 + \dots + \lambda_m y_m + \mu_1 x_1 + \dots + 0 x_i + \dots + \mu_r x_r - y \right),$$ which means even though the set $\{y,y_1, \dots, y_m, x_1, \dots, x_r \}$ spans $V$, the element $x_i$ is not necessary to span $V$, so we can remove it from this set and still have a generating set for $V$.
• That does help. Just so I understand tho, the hint my prof gave was that since (L-{y}) $\cup$ S spans V, y is a linear combination of $y_1, ...,y_m, x_1, ...,x_r$. And that we should use the linear independence of L to conclude there is at least one $x_i$ that is nonzero. Anyhow, I assumed y was linearly dependent because it could be written as a linear combination. And that a linearly independent set would have coefficients that go to zero. Which part was a wrong understanding? – Jesse Jun 20 '13 at 4:55