Basis Exchange and Dimension

Definition Let $V$ be a vector space over $\mathbb{F}$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, and let all lists be finite. The lemma rests on a replacement step. If $w_1, \dots, w_n$ span $V$ and $v = a_1 w_1 + \cdots + a_n w_n$ with $a_k \ne 0$, then replacing $w_k$ by $v$ gives a list that still spans $V$, because

The exchange lemma says that if $v_1, \dots, v_m$ are linearly independent in $V$ and $w_1, \dots, w_n$ span $V$, then $m \le n$. Moreover, after the $w_j$ are renumbered, the list $v_1, \dots, v_m, w_{m+1}, \dots, w_n$ spans $V$.

To prove it, insert $v_1, v_2, \dots$ one at a time. Suppose $v_1, \dots, v_k$ have replaced $k$ of the $w_j$ and the current list still spans $V$. Write $v_{k+1}$ as a combination of the current list. Some coefficient on a remaining $w_j$ must be nonzero, since otherwise $v_{k+1}$ would be a combination of $v_1, \dots, v_k$, which contradicts independence. Replacing that $w_j$ by $v_{k+1}$ keeps the list spanning. If $m$ were larger than $n$, then after $n$ steps no $w_j$ would remain, and the same reasoning would make $v_{n+1}$ a combination of $v_1, \dots, v_n$, which is impossible. So $m \le n$.

Definition Let $V$ be a vector space over $\mathbb{F}$ that is spanned by some finite list. Then every linearly independent list in $V$ has at most as many vectors as that spanning list, and any two bases of $V$ have the same number of vectors. For the proof, let $b_1, \dots, b_p$ and $c_1, \dots, c_q$ be bases of $V$. The first list is independent and the second spans, so $p \le q$ by the exchange lemma. Exchanging the roles gives $q \le p$, so $p = q$. The scalar field stays fixed throughout, and bases of the same set over $\mathbb{R}$ and over $\mathbb{C}$ may have different lengths.

Definition A vector space $V$ over $\mathbb{F}$ is finite-dimensional if some finite list spans it. Such a space has a basis, by the extraction result below, and its dimension $\dim V$, written $\dim_{\mathbb{F}} V$ when the field needs saying, is the number of vectors in any basis. The zero space $\{0\}$ has the empty list as a basis and dimension $0$. If $\dim V = n$, then

• every list of more than $n$ vectors in $V$ is linearly dependent,
• no list of fewer than $n$ vectors spans $V$,
• a list of exactly $n$ vectors that is independent also spans, so it is a basis,
• a list of exactly $n$ vectors that spans is also independent, so it is a basis.

The first two facts are the exchange lemma applied with a basis of $V$. For the third, if an independent list of $n$ vectors did not span $V$, appending a vector $u$ outside its span would give an independent list of $n + 1$ vectors, as shown under extension below, which the first fact rules out. For the fourth, a dependent spanning list of $n$ vectors could lose one vector and still span, which the second fact rules out.

Definition Every finite list that spans a vector space $V$ over $\mathbb{F}$ contains a basis of $V$. To find one, as long as the list is linearly dependent, remove a vector that is a linear combination of the others. A dependent list always has such a vector, since a relation $c_1 w_1 + \cdots + c_n w_n = 0$ with $c_k \ne 0$ can be solved for $w_k$. Removing it does not change the span, and the length drops each time, so the process stops, and it can stop only at a list that is independent and still spans $V$. In particular, every finite-dimensional space has a basis.

Definition In a finite-dimensional vector space $V$ over $\mathbb{F}$, every linearly independent list can be extended to a basis of $V$. The key fact is that if $v_1, \dots, v_p$ is independent and $u \notin \operatorname{span}(v_1, \dots, v_p)$, then $v_1, \dots, v_p, u$ is independent. Indeed, in a relation $a_1 v_1 + \cdots + a_p v_p + cu = 0$, a nonzero $c$ would put $u$ in the span, so $c = 0$, and then independence gives $a_1 = \cdots = a_p = 0$. To extend, take a spanning list $w_1, \dots, w_n$ of $V$ and go through it in order, appending $w_j$ whenever it is not in the span of the current list. Each step keeps the list independent, and at the end every $w_j$ lies in its span, so the list spans $V$.

Definition Let $V$ be a finite-dimensional vector space over $\mathbb{F}$ and let $U$ be a subspace of $V$. Then $U$ is finite-dimensional and $\dim U \le \dim V$. Moreover, $\dim U = \dim V$ only when $U = V$. For the proof, start with the empty list and, as long as the current list does not span $U$, append a vector of $U$ outside its span. Each list is independent, so by the exchange lemma, with a basis of $V$ as the spanning list, at most $\dim V$ vectors can be appended. The process therefore stops at a basis of $U$ with at most $\dim V$ vectors. If $\dim U = \dim V = n$, that basis is an independent list of $n$ vectors in $V$, so it spans $V$, and $U = V$.