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$
3
  • $\begingroup$ I think you mean $m\leq n$, otherwise $x_1,x_2,\ldots,x_n$ would be a counterexample... $\endgroup$
    – AndreasT
    Mar 7, 2013 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, 2013 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, 2013 at 15:24

2 Answers 2

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$
3
  • $\begingroup$ thank you. for the answer. $\endgroup$
    – user59756
    Mar 7, 2013 at 15:32
  • $\begingroup$ I would say the Steinitz exchange lemma is exactly the result asked for here. $\endgroup$ Oct 22, 2013 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, 2013 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$
1
  • $\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, 2013 at 15:28

You must log in to answer this question.