Any two bases of a finite dimensional vector space must have the same number of elements.

Prove that any two bases of a finite dimensional vector space must have the same number of elements.

By considering the following two bases

$$S_1 = \{ \alpha_1, \alpha_2 , \ldots, \alpha_n \},$$

$$S_2 = \{ \beta_1, \beta_2, \ldots, \beta_m \},$$

how do I show that $m = n$?

Hints to get started. Thanks very much.

Solution 1:

Quote from Wikipedia quoted from Linear Algebra Done Right of a bit more general result:

Theorem: If A = $(a_1,\dots,a_n) \subseteq V$ is a linearly independent tuple in a vector space $V$, and $B_0 = (b_1,...,b_r)$ is a tuple that spans $V$, then $n\le r$.

Proof: Since $B_0$ spans $V$, the tuple $(a_1,b_1,\dots,b_r)$ also spans. Since $a_1\ne 0$ (because A is linearly independent), there is at least one $t\in\{1,\ldots,r\}$ such that $b_t$ can be written as a linear combination of $B_1 = (a_1,b_1,\dots,b_{t-1}, b_{t+1}, ... b_r)$. Thus, $B_1$ is a spanning tuple, and its length is the same as $B_0$'s.

Repeat this process. Because $A$ is linearly independent, we can always remove an element from the list $B_i$ which is not one of the $a_j$'s that we prepended to the list in a prior step (because $A$ is linearly independent, and so there must be some nonzero coefficient in front of one of the $b_i$'s). Thus, after $n$ iterations, the result will be a tuple $B_n = (a_1, \ldots, a_n, b_{m_1}, \ldots, b_{m_k})$ (possibly with $k=0$) of length $r$. In particular, $A\subseteq B_n$, so $|A|\le |B_n|$, i.e., $n\leq r$.

Solution 2:

Assume that $$ (\alpha_1,\cdots, \alpha_n)\supseteq (\beta_1,\cdots, \beta_m) \Rightarrow n \geq m $$

where $\{ \alpha_i\} $, $\{\beta_i\}$ are linearly independent.

Proof : Assume that $ (\alpha_1) \supseteq (\beta_1,\cdots, \beta_m),\ m>1 $ So $ \beta_1=c_1\alpha_1,\ \beta_2=c_2\alpha_1$ so that $\{ \beta_i\}_{i=1}^2$ is dependent. Contradiction.

We will use induction : $n=k$ is fine. Then let $$ (\alpha_1,\cdots, \alpha_{k+1})\supseteq (\beta_1,\cdots, \beta_m),\ m>k+1 $$

Clearly we have $c_{ij}$ : $$ \beta_j:= \sum_i c_{ji}\alpha_i$$ Note that for some $j$, $c_{j1}\neq 0$. If not $$ (\alpha_2,\cdots, \alpha_{k+1})\supseteq (\beta_1,\cdots, \beta_m) $$ So we have $k\geq m$.

Let $c_{11}\neq 0$. Then $$ (\beta_2- \frac{c_{21}}{c_{11}} \beta_1,\cdots, \beta_m-\frac{c_{m1}}{c_{11}} \beta_1 )\subset (\alpha_2,\cdots , \alpha_{k+1})$$

Note that $\{ \beta_2- \frac{c_{21}}{c_{11}} \beta_1,\cdots, \beta_m-\frac{c_{m1}}{c_{11}} \beta_1 \}$ is linearly independent. So $ k\geq m-1$. Thus we have a contradiction.