# Linearly Independent Vectors and Basis

Q. Prove that if $x_1,x_2,...,x_n$ form basis for vector space $X$, and $y_1,y_2,...,y_m$ be linearly independent vectors in $X$, with $m\le n$ show that it is possible to construct new basis for $V$ with $y_1,y_2,...,y_m$ and $n-m$ vectors from $x_1,x_2,...,x_n$?

I know, the basis vectors $x_1,x_2,...,x_n$ can be reduced to row echelon form. the vectors $y_1,y_2,...,y_m$ can be reduced into row echelon form with $n-m$ rows reduced to all $0s$. I have no idea whether this is correct approach or if it is correct.

Edited The new basis should be for $V$. Thank you.

• I think you mean $m\leq n$, otherwise $x_1,x_2,\ldots,x_n$ would be a counterexample... Mar 7, 2013 at 15:18
• that is possible but if am given $ys$ such that $m<n$, I think there is not problem. Any, let's take$m\le n$
– user59756
Mar 7, 2013 at 15:23
• This is true - the $m<n$ is an assumption, but not a necessary one. You can either replace it by $m\leq n$, or drop it entirely and treat it as a conclusion (see the Steinitz exchange lemma).
– mdp
Mar 7, 2013 at 15:24

You should try to do things in the opposite order to that suggested by Learner, i.e. you should show that there is some $x_i$ you can replace by $y_1$ and still have a basis. Then repeat for $y_2$, and so on (being careful that you always remove an $x$ rather than a $y$).

I would strongly recommend trying to do this yourself first, but if you get very confused you can try looking up the Steinitz exchange lemma, which is a slightly more general result than the one you want.

• thank you. for the answer.
– user59756
Mar 7, 2013 at 15:32
• I would say the Steinitz exchange lemma is exactly the result asked for here. Oct 22, 2013 at 7:43
• @MarcvanLeeuwen Pretty much, although in the statement of the lemma that I'm used to, the $m\leq n$ is a conclusion rather than an assumption.
– mdp
Oct 22, 2013 at 10:40

since already $y_1, \cdots y_m$ vectors are linearly independent, just keep adding the vectors from $x_i$ which are not linearly dependent with $y_i$ vectors and previously added vector.

• my question basically is, what guarantees that there are $n-m$ vectors from original basis are linearly independent from the all $y$s
– user59756
Mar 7, 2013 at 15:28