Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose you have a finite dimensional vector space $V$ with two different bases $\{b_1,\dots,b_n\}$ and $\{c_1,\dots,c_n\}$. Is it possible to swap out any number of vectors between the two bases such that both resulting sets are still bases? More precisely, for any $0\lt m\lt n$ is there some permutation $\pi$ such that $$\{b_1,\dots, b_m, c_{\pi(m+1)},\dots,c_{\pi(n)}\}$$ and $$\{c_{\pi(1)},\dots,c_{\pi(m)},b_{m+1},\dots, b_n\}$$ are bases of $V$? If so, why? Thanks.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

We prove it for the case $m = n-1$, and the general case follows from induction.

Set $W:=\mathrm{span}_{1\leq i \leq n-1}\{b_i\}$. Suppose we wish to exchange $b_n$ with some element $c_i$ in such a way that these two sets remain bases. Consider the set $S \subset \{1,2,\ldots,n\}$ of indices $i$ such that $c_i \notin W$. $S \neq \emptyset$, because if it did, then we would have an $n$-dimensional vector space ($\mathrm{span}\{c_i\}$) sitting inside of $W$, an $n-1$-dimensional vector space. So $S$ contains at least one index.

We need to prove that there is at least one index $j \in S$ such that $b_n \notin \mathrm{span}_{i\neq j}\{c_i\}$. We proceed by contradiction. Suppose that this is not the case, ie that $b_n \in \mathrm{span}_{i \neq j}\{c_i\}$ for each $j \in S$. Then $b_n$ is in the intersection of these subspaces, which is $\mathrm{span}_{i \notin S}\{c_i\}$. Now, $c_i \in W$ for $i \notin S$ by the definition of $S$. So we have $\mathrm{span}_{i \notin S}\{c_i\} \subseteq W$. Since $b_n \in \mathrm{span}_{i \notin S}\{c_i\}$, this implies $b_n \in W$. But this is a contradiction, because $b_n$ is linearly independent from $W$. Our contradiction completes the proof.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.