Show that if we exchange elements in 2 different basis will still give us a basis. I came across a proof of the following theorem:
Let V be a free module over a division ring D. Suppose X and Y are two finite basis of V, then |X| = |Y|.
that uses the fact that if we exchange elements in 2 different basis, we will still get a basis. Say $X = \{x_1, x_2, ..., x_n\}$ and $Y = \{y_1, ..., y_k\}$, then $\{x_1, x_2, ..., x_{n-1}, y_k\}$ is still a basis. 
However, I am having trouble proving that, I can't show that if $0 = a_1 x_1 + ... a_n y_k$, then all the coefficients are 0. Can someone teach me how to solve this? Thanks
 A: You have to be more precise.
First of all, it is convenient to assume that $k \le n$.
Then, $y_{k}$ will be a non-zero linear combination of the $x_{i}$. This means that when you write out $y_{k}$ as a linear combination of the $x_{i}$, at least one of the coefficients is non-zero. Permuting the $x_{i}$, one may assume that it is precisely the coefficient of $x_{n}$ that is non-zero.
Now you can proceed safely. That is, you have
$$
y_{k} = a_{1} x_{1} + \dots + a_{n} x_{n},
$$
with $a_{n} \ne 0$. So
$$
x_{n} = a_{n}^{-1} (y _{k} - a_{1} x_{1} - \dots - a_{n-1} x_{n-1}).
$$
This shows that $x_{1}, \dots, x_{n-1}, y_{k}$ is a system of generators, as
$$
\langle x_{1}, \dots, x_{n-1}, y_{k} \rangle \supseteq \langle x_{1}, \dots, x_{n-1}, x_{n} \rangle = V.
$$
If
$$
b_{1} x_{1} + \dots + b_{n-1} x_{n-1} + c y_{k} = 0,
$$
then
$$
(b_{1} + c a_{1}) x_{1} + \dots + (b_{n-1} + c a_{n-1}) x_{n-1} + c a_{n} x_{n} = 0.
$$
This implies $c = 0$, as $a_{n} \ne 0$, and thus all $b_{i}$ are zero. It follows that $x_{1}, \dots, x_{n-1}, y_{k}$ are also linearly independent.
A: The exchange lemma does not work quite as you suggest - assuming we are not dealing with empty sets, so every set has an element in it, proceed as follows. Suppose $\{x_1 \dots x_n\}$ and $\{y_1 \dots y_m\}$ are two bases. They are both minimal spanning sets, and they are both maximal linearly independent sets. Suppose $m\le n$.
Consider $\{y_1, x_1 \dots x_n\}$ this is a spanning set, because the $x_i$ are a spanning set. It is not minimal, because the $x_i$ are a minimal spanning set. We cast out the first element of the set which is linearly dependent on the previous elements. This cannot be $y_1$, because that is part of a linearly independent set, so it must be one of the $x_i$. 
If $x_r$ and $x_s$ were both dependent on previous elements with $r\gt s$, these dependencies include $y_1$ (because the $x_i$ are linearly independent). But then we can use the fact that $D$ is a division ring to eliminate $y_1$. Since $x_r$ appears only in one of the dependencies, it cannot be eliminated, and we therefore have a non trivial dependence amongst the $x_i$. This is a contradiction, because they form a basis.
You can't replace any element you choose - you have to pick (the) one which is linearly dependent on the rest.
You systematically replace the $x$s with $y$s. And if you had any $x$s left over that would be a contradiction because the $y$s form a spanning set.
A: Let $X=\{x_1, x_2\}$, $Y=\{y_1, y_2\}$ with $y_1=x_2$, $y_2=x_1$. Now $\{x_1, y_2\} = \{x_1\}$ is not a basis in general. Hence, your statement is wrong.
