Size of Linearly Independent Subset is at Most Size of Finite Generator/Proof 3
Theorem
Let $R$ be a division ring.
Let $V$ be an $R$-vector space.
Let $F \subseteq V$ be a finite generator of $V$ over $R$.
Let $L \subseteq V$ be linearly independent over $R$.
Then:
- $\size L \le \size F$
Proof
Let $\alpha_1, \alpha_2, \ldots, \alpha_n$ be a generator of $V$.
Let $\xi_1, \xi_2, \ldots, \xi_r$ be a linearly independent set of elements of $V$.
Hence the sequence $\sequence {\xi_1, \alpha_1, \alpha_2, \ldots, \alpha_n}$ is a linearly dependent sequence of elements of $V$.
One of these elements, which cannot be $\xi_1$, is a linear combination of the preceding elements.
Let this elements be $\alpha_i$.
So we can omit $\alpha_i$ from that sequence, and the remaining set is still a generator of $V$.
Therefore $\xi_2$ is a linear combination of these.
Thus $\sequence {\xi_2, \xi_1, \alpha_1, \alpha_2, \ldots, \alpha_{i - 1}, \alpha_{i + 1}, \ldots, \alpha_n}$ is a linearly dependent sequence of elements of $V$.
Again, one of them is a linear combination of the preceding elements.
This cannot be $\xi_2$, as $\xi_2$ has no preceding elements.
Neither can it be $\xi_1$, as $\xi_1$ and $\xi_2$ are linearly independent.
Thus we can omit whichever $\alpha_j$ it is, and we have a new set which is a generator of $V$.
This consists of $\xi_1$, $\xi_2$ and whichever $n - 2$ of the remaining elements of $\set {\alpha_1, \alpha_2, \ldots, \alpha_n}$.
After $p$ such steps, we have a set which is a generator of $V$ which consists of:
- $\xi_1, \xi_2, \ldots, \xi_p$ and $n - p$ of the elements of $\set {\alpha_1, \alpha_2, \ldots, \alpha_n}$.
Aiming for a contradiction, suppose suppose $n < r$.
Then when $p = n$, the remaining set which is a generator of $V$ consists of:
- $\xi_1, \xi_2, \ldots, \xi_n$
and there is at least one more element $\xi_{n + 1}$.
This is a linear combination of $\set {\xi_1, \xi_2, \ldots, \xi_n}$.
But this contradicts the supposition that $\set {\xi_1, \xi_2, \ldots, \xi_n, \xi_{n + 1} }$ is a linearly independent set.
Hence, by Proof by Contradiction, $n \ge r$.
The result follows.
$\blacksquare$
Sources
- 1969: C.R.J. Clapham: Introduction to Abstract Algebra ... (previous) ... (next): Chapter $7$: Vector Spaces: $\S 33$. Definition of a Basis: Theorem $66$