Given two bases of $\mathbb{R}^n$, is it possible to switch a vector between the two to get a new basis? Let $V_1, V_2$ be different bases of $\mathbb{R}^n$ and let $v\in V_1\setminus V_2$. Show that there must be a $u\in V_2\setminus V_1$ such that $(V_1\setminus\{v\})\cup\{u\}$ is a basis of $\mathbb{R}^n$.
The way I'm interpreting this is that we are trying to swap a vector from one basis with a vector from another basis to form a basis that still spans $\mathbb{R}^n$.
If $V_1$ is a basis for $\mathbb{R}^n$ and $u \in V_2$ is non zero then $ u = c_1 v_1 + \cdots + c_n v_n$ where at least one $c_i$ is non zero for some $1 \le i \le n$. Thus we get $\frac{1}{c_i} u = \frac{c_1}{c_i} v_1 + \cdots + \frac{c_i}{c_i} v_i + \cdots + \frac{c_n}{c_i} v_n$ and rearranged we get $ v_i = \frac{1}{c_i} u - \frac{c_1}{c_i} v_1 - \cdots - \frac{c_n}{c_i} v_n$.
Then we can use this new vector as a replacement. I'm not sure if this is the way to go. Any pointers would be really helpful. Thanks
Edit: can someone verify this?
We can use the following theorem:
Let $V\subseteq\mathbb{R}^n$. Any two of the following implies the third:

*

*The set $V$ contains exactly $n$ elements.

*The set $V$ is linearly independent.

*The set $V$ spans $\mathbb{R}^n$.

We also have another theorem: A basis of $\mathbb{R}^n$ has $n$ elements.
Since we are working with bases, we have already satisfied 1. from the above theorem. Now since $u\not\in V_1$, we can say that $u$ is linearly independent with all of the vectors in $V_1$, thus taking out $v$ and replacing it with $u$ gives us a set $V$ that is linearly independent, so 2. is satisfied. This means that we have a set $V$ that contains $n$ that spans $\mathbb{R}^n$ and is linearly independent. Thus, the resulting set $V$ is a basis.
Edit 2:
I think I can solve this by contradiction. If we assume that $u$ does not exist, then the vectors in $V_2\setminus V_1$ will be linearly dependent with those in $V_1$. So $V_2\cap V_1$ and $V_2\setminus V_1$ are linearly dependent, so $V_2$ is not linearly independent, which contradicts the fact that it is a basis. So a $u$ must exist and adding it $V_1$ after removing $v$ will result in a set of $n$ linearly independent vectors, which from above theorem and the definition of basis, means that it is a basis.
 A: We have two distinct bases $v_1,\dots v_n$ and $u_1,\dots, u_n$. We want to show that there is some $u_i$ such that $v_1,\dots, v_{n-1}, u_i$ is a basis (we can assume the vector we are removing is $v_n$ as otherwise we can just reorder). You mention using the fact that if a linearly independent set has $n$ elements then it must be a basis as it must span. There might be a way to do this, but it would require proving that $v_1, \dots v_{n-1}, u_i$ is linearly independent, and it's not obvious that this is true. I propose using the "opposite" fact, that if you have a spanning set which has $n$ elements then it must be a basis. Now, $v_1,\dots, v_n$ is a basis so for any $i$ we have $a_1,\dots,a_n\in\mathbb R$ such that $a_1v_1 + \dots + a_n v_n = u_i$. Suppose that $a_n$ is non-zero. Then we would have that $v_n = u_i - a_1/a_n v_1 -\dots - a_{n-1}/a_n v_n $. This means that $v_1,\dots,v_{n-1}, u_i$ spans and so it is a basis.
Now, all we have to do is prove that there is some $u_i$ where $a_n$ is not zero. Suppose that this weren't the case. Then $u_i$ is in the span of $v_1, \dots, v_{n-1}$ for each $i$, and so the span of $u_1,\dots, u_n$ is contained in the span of $v_1, \dots, v_{n-1}$. But this is a problem, as that would mean that $v_n$ is not in the span of $u_1,\dots, u_n$ which is a contradiction as $u_1,\dots,u_n$ is a basis. Therefore, there must be a $u_i$ which has $a_n$ non-zero and so we are done.
