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... – AndreasT Mar 7 '13 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 '13 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 '13 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$).
• @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 '13 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 '13 at 15:28