# Prove subset of $S$ is a basis

Let $V$ be a vector space having dimension $n$, and let $S$ be a subset of $V$ that generates $V$.

Prove that there is a subset of $S$ that is a basis for $V$.

So if I let $\beta={u_1, u_2,....,u_n}$ be a basis for $V$, then each vector in $V$ can be written as a linear combination of the vectors in $\beta$. Since $S$ generates $V$ and $\beta$ $\subseteq$ V, then $S$ generates $\beta$.

I'm not sure where to go from here. I know I can somehow use the fact that the vectors in $\beta$ are linearly independent, but I still don't fully see how.

Any tips are appreciated.

Thanks

• You have a fundamental misunderstanding of the problem. It is true that if a set S spans the space then it contains a basis. You starting with a basis $\beta$ and the declare it must be a subset of S. It is not true that every basis is a subset of S! – user247327 Apr 1 '18 at 23:10

If $s_1,\ldots,s_k\in S$ are linearly independent with $0\le k<n$, look for $s_{k+1}\in S$ so that $s_1,\ldots,s_k,s_{k+1}$ are linearly independent. Proceed by induction on $k$.

• So I would show that $S$ contains all linearly independent vectors? And then, it has to contain $\beta$? – Alti Oct 14 '13 at 15:35
• No, $S$ will not have to contain $\beta$. The proof will not use $\beta$ at all. You just need the dimension: First, to prove that the induction can continue for $k<n$, second, to show that the induction stops at $k=n$. So now you have independent vectors $s_1,\ldots,s_n\in S$, and these cannot be extended further, and from this you prove that these vectors form a basis. (I have of course left out many details.) – Harald Hanche-Olsen Oct 14 '13 at 16:51

You can proceed with an inductive argument:

Take $\;0\neq s_1\in S\;$ . If $\;$ Span$\{s_1\}=V\;$ then we're done, otherwise there must be $\;s_2\in S\setminus \{s_1\}\;$ (why?).

If $\;$Span$\{s_1,s_2\}=V\;$ we're done, otherwise there's $\;s_3\in S\setminus\{s_1,s_2\}\;$ ...etc.

The above process is finite since $\;\dim V=n\;$ . Now polish, finise and serve hot.

Note that $S$ must contain $n$ linearly independent vectors, say $u_1, \ldots, u_n \in S$. If not, then $\text{dim}(\text{span}(S)) < n$ and $S$ cannot generate $V$. Then $\beta = \{u_1, \ldots, u_n\}$ is a basis for $V$ since $\beta$ is certainly linearly independent and $\text{dim}(\text{span}(\beta)) = n$, i.e. $\text{span}(\beta) = V$.