# Linear Algebra - Linear Independence Proof - Any hints?

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?

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

• just re-read over this, can you explain why this is a contradiction? – PhysicsMathsLove May 22 '17 at 12:02
• 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$. – fonfonx May 22 '17 at 12:47