Let $X,Y$ be two linearly independent sets of vectors of a finite dimensional vector space $V$ over $\mathbb{R}$ such that $|X| = |Y|$. Prove that for every $x \in X$ there is a $y \in Y$ such that the set $\left( X \setminus \{x\}\right) \cup \{y\}$ is linearly independent.

Any hints?

  • 3
    $\begingroup$ What actually is the question? (Whatever it is I'm sure the answer will be the Steinitz Exchange Lemma.) $\endgroup$ – Lord Shark the Unknown May 20 '17 at 16:01
  • $\begingroup$ @LordSharktheUnknown The question is there. I'll put it in bold for clarity. $\endgroup$ – PhysicsMathsLove May 20 '17 at 16:03
  • $\begingroup$ There's definitely a verb missing. Prove that there exists a $y$ such that the given set..... has super-powers? $\endgroup$ – G Tony Jacobs May 20 '17 at 16:03
  • 1
    $\begingroup$ "such that the set" is linearly independent? $\endgroup$ – Itay4 May 20 '17 at 16:03
  • $\begingroup$ @PhysicsMathsLove It's now all bold, but the last sentence is still verbless! $\endgroup$ – Lord Shark the Unknown May 20 '17 at 16:04

You can see it with a proof by contradiction.

Let $x \in X$, and $y \in Y$ s.t $\{X \backslash \{x\}\} \cup \{y\}$ is linearly dependent. Then there exist a non trivial linear combination of the elements of $\{X \backslash \{x\}\} \cup \{y\}$ which is zero. The coefficient in front of $y$ cannot be zero since $X$ is a linearly independent family. Then you can express $y$ as a non trivial linear combination of elements of $X \backslash \{x\}$.

If all elements of $Y$ verify this property, then you have proven that the vector space spanned by $Y$ is included in the one spanned by $X\backslash \{x\}$. However $\dim \mathrm{span}\{X\backslash \{x\}\} = \dim \mathrm{span} \{Y\} - 1$ which is a contradiction.

  • $\begingroup$ just re-read over this, can you explain why this is a contradiction? $\endgroup$ – PhysicsMathsLove May 22 '17 at 12:02
  • $\begingroup$ since $Y$ is a linearly independent set of vectors the vector subspace it spans has dimension $|Y|$. And we have proven that this subspace is included in the subspace spanned by $X \backslash \{x\}$ whose dimension is $|X| -1$ = $|Y| -1$. This is a contradiction because if $A$ and $B$, are vector spaces such that $A \subset B $, then $\dim A \leq \dim B$. $\endgroup$ – fonfonx May 22 '17 at 12:47

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.