# Proving that $m \leq n$, using finite spanning sets and linear independence.

Let $V$ be a vector space in $F$, and suppose that $V$ has a finite spanning set $S=\{v_1,\ldots,v_n\}$. Show that if $T=\{u_1,\ldots,u_m\}$ is a linearly independent subset of V, then $m\leq n$. (We are not assuming $T$ is a subset of $S$)

I have tried going about this using contradiction, but I'm unclear as to whether that is enough or how to start from there. Thanks in advance

-
Just use the definition of dimension. Recall: when you want to find the (finite) dimension of a vector space, the "problem" is that spanning sets might be too big and linearly independent sets might be too small: more precisely, when you have a spanning set $S$ with $n$ elements, then $n\geq \dim V$. And, given any subset $T$ of $m$ linearly independent vectors, you have $m\leq \dim V$. The dimension is the number of vectors you collect when you do "your best" in any of these two cases: you can find a minimal set of generators, or a maximal independent system. –  Brenin Sep 13 '12 at 18:13
I think the title of this question can be improved... –  ivan Sep 13 '12 at 18:57
add comment

## 2 Answers

Hint: Since $S$ is a spanning set, you can write $u_i=\sum\limits_{j=1}^n\lambda_{ij}v_j$ for some $\lambda_{ij}\in F$. If $m>n$, can you find a linear dependence among these elements?

Hint 2: We have $u_1=\sum\limits_{j=1}^n\lambda_{1j}v_j$ and $u_2=\sum\limits_{j=1}^n\lambda_{2j}v_j$. If $\lambda_{21}\neq 0$, then $$u_1-\frac{\lambda_{11}}{\lambda_{21}}u_2=0v_1+x_2v2+\cdots + x_nv_n$$ while otherwise $u_2=0v_1+x_2v_2+\cdots + x_nv_n$ for some $x_2,\ldots,x_n\in F$. Either way, we've found a linear combination of the first $2$ elements of $T$ which eliminates $v_1$. Proceeding in this manner, what do we get using the first $n+1$ elements of $T$?

-
So if you let $u_m=\lambda_1 v_1 + ... + \lambda_n v_n$ then I'm unclear, but I'll continue with my line of thought. Assume $\lambda_n \neq 0$ then we can say $v_n=\frac{u_m-\lambda_1 v_1 - ... }{\lambda_n}$? I'm confused, sorry. –  tk2 Sep 13 '12 at 17:56
@tkrm I edited to include another hint. –  Alex Becker Sep 13 '12 at 18:21
Thanks, I got it now! –  tk2 Sep 13 '12 at 23:20
add comment

You can select a basis from $S$ and you can extend $T$ a basis. These basises have the same length.

-
add comment