0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you mean $m\leq n$, otherwise $x_1,x_2,\ldots,x_n$ would be a counterexample... $\endgroup$ – AndreasT Mar 7 '13 at 15:18
  • $\begingroup$ 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$ $\endgroup$ – user59756 Mar 7 '13 at 15:23
  • $\begingroup$ 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). $\endgroup$ – mdp Mar 7 '13 at 15:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you. for the answer. $\endgroup$ – user59756 Mar 7 '13 at 15:32
  • $\begingroup$ I would say the Steinitz exchange lemma is exactly the result asked for here. $\endgroup$ – Marc van Leeuwen Oct 22 '13 at 7:43
  • $\begingroup$ @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. $\endgroup$ – mdp Oct 22 '13 at 10:40
1
$\begingroup$

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.

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

Your Answer

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