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).

  • $\begingroup$ In the right ballpark... lol :) $\endgroup$ – Patrick Da Silva Jun 20 '13 at 4:36
  • $\begingroup$ "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. $\endgroup$ – 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$.

Hope that helps,

  • $\begingroup$ 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? $\endgroup$ – Jesse Jun 20 '13 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.