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.
Can one always make hybrid bases from two bases?
1 Answers
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.