Vector space/Basis/Exchange theorem/Fact/Proof

Proof

We do induction over ${}k$, the number of the vectors in the family. For ${}k=0$, there is nothing to show. Suppose now that the statement is already proven for ${}k$, and let ${}k+1$ linearly independent vectors

$u_{1},\ldots ,u_{k},u_{k+1}$

be given. By the induction hypothesis, applied to the vectors (which are also linearly independent)

$u_{1},\ldots ,u_{k},$

there exists a subset ${}J=\{i_{1},i_{2},\ldots ,i_{k}\}\subseteq \{1,\ldots ,n\}$ such that the family

$u_{1},\ldots ,u_{k},b_{i},i\in I\setminus J,$

is a basis of ${}V$. We want to apply the basis exchange lemma to this basis. As it is a basis, we can write

${}u_{k+1}=\sum _{j=1}^{k}c_{j}u_{j}+\sum _{i\in I\setminus J}d_{i}b_{i}\,.$

Suppose that all coefficients ${}d_{i}=0$. Then we get a contradiction to the linear independence of ${}u_{j}$, ${}j=1,\ldots ,k+1$. Hence, there exists some ${}i\in I\setminus J$ with ${}d_{i}\neq 0$. We put ${}i_{k+1}:=i$. Then ${}J'=\{i_{1},i_{2},\ldots ,i_{k},i_{k+1}\}$ is a subset of ${}\{1,\ldots ,n\}$ with ${}k+1$ elements. By the basis exchange lemma, we can replace the basis vector ${}b_{i_{k+1}}$ by ${}u_{k+1}$, and we obtain the new basis

$u_{1},\ldots ,u_{k},u_{k+1},b_{i},i\in I\setminus J'.$

  The final statement follows, since we have a subset with ${}k$ elements inside a set with ${}n$ elements.

To fact