Theorem – Every basis for a vector space has the same cardinality as every other basis.

Theorem

Let $V$ be a finite dimensional vector space and let $B_1$ and $B_2$ be any two different bases for $V$ . For all pairs of bases $B_1$ and $B_2$ , we have $|B_1| = |B_2|$ .

Proof

We will use proof by contradiction to show that, given two different bases for a finite dimensional vector space $V$ , say $X = \{x_1, ..., x_i\}$ and $Y = \{y_1, ..., y_k\}$ , $i \ne k$ leads to a contradiction.

To do so, consider the set $X$ . Since it is a basis, it is linearly independent, and a linear combination of the vectors in $X$ can generate any vector in $V$ . It follows that said linear combination can generate the vector $y_k$ , so that the set

$S = \{y_k, x_1, ..., x_i\}$

is linearly dependent. Since $S$ is linearly dependent, some $x_j\in{S}$ can be written as a linear combination of the vectors preceeding it for some $j = 1, ..., i$ . Considering the set $S' = S\setminus {x_j}$ , it follows from the previous reasoning that, since we can make the vector $x_j$ via a linear combination of the elements of $S'$ , that $S'$ can still make any vector in $V$ . For a similar reason, the set $S'$ is also linearly depenedent.

Note that we have appended the last vector of $Y$ and removed one element from $X$ . $S'$ is linearly dependent. If we continue this approach, at each step we have removed the same amount of elements as we have added. Thus, at the 6th step we will have removed 6 elements ( $x$ ‘s) from $X$ and added 6 elements of $Y$ to the set $X$ .

Now, we have two cases. Since we are assuming that $i\ne k$ , we have that either $i < k$ , or $i > k$ . If $i < k$ , then on the $i$ th iteration, we will have a set that consists of $i$ many $y$ ‘s and no $x$ ‘s. Since we know that at each stage, our algorithm leaves us with a set that can generate any vector in $V$ and is linearly dependent, our contradiction will be that one of these conditions is broken.

To see that this must be the case for $i < k$ , recall that for any vector $V$ , the coefficients of the linear combination that generates it are unique (proof given here). Now consider a vector $y_0 \in Y$ such that $y_0$ is not in the final set of $S'$ after $i$ iterations. Then, the vector $2y_0$ cannot be generated by the set of vectors left after the $i$ th iteration, and it follows that this set is not a basis. But this contradicts the fact that $i<k$ .

Now let $i > k$ . The same logic as above applies, so that it cannot be the case that the set is still a basis, since it only contains a strict subset of $X$ . Therefore, it must be the case that $i = k$ . $\square$