Searching for the most elementary proof of a theorem in linear algebra Let $V$ be a vector space. Let $u_1, ..., u_n$ be linearly independent vectors, and let $v_1, ..., v_m$ be generators of $V$. Then, we have $n \leq m$.
On my book there is a proof of this result, but it is quite long and cumbersome. Could you suggest one proof that you know which is quick and elementary?
 A: Assume $n>m$ and write $u_i$ as linear combination of the set $\{v_1,\dots,v_m\}$:
$$
u_i=\sum_{j=1}^m \beta_{ij}v_j\qquad(i=1,\dots,n).
$$
A relation $\alpha_1u_1+\dots+\alpha_nu_n=0$ gives
$$
\sum_{i=1}^n\sum_{j=1}^m\alpha_i\beta_{ij}v_j=0
$$
that can be rewritten as
$$
\sum_{j=1}^m\biggl(\sum_{i=1}^n \alpha_i\beta_{ij}\biggl)v_j=0.
$$
The homogeneous linear system
\begin{cases}
\alpha_1\beta_{11}+\alpha_2\beta_{21}+\dots+\alpha_n\beta_{n1}=0\\
\alpha_1\beta_{12}+\alpha_2\beta_{22}+\dots+\alpha_n\beta_{n2}=0\\
\quad\vdots\\
\alpha_1\beta_{1m}+\alpha_2\beta_{2m}+\dots+\alpha_n\beta_{nm}=0
\end{cases}
in the unknowns $\alpha_1,\alpha_2,\dots,\alpha_n$ has less equations than unknowns, so it has infinitely many solutions. Hence $\{u_1,\dots,u_n\}$ is not linearly independent.

Note. The exchange theorem that you probably are referring to as having a long and cumbersome proof is much more informative than this proof.
A: *

*Any linearly independent family of vectors is contained in a basis

*Any generating family contains a basis

*Any two bases have the same cardinality.


The last item is the most technical one and is obtained by exchanging basis elements one by one (which is especially straightforward in the finite-dimensional case). The most interesting step is the first, however, because it involves the axiom of choice (well, not so much in the case of finite dimensions)
