5
$\begingroup$

If $V$ is a vector space and $v_1, v_2, . . . , v_n \in V$ span $V$, and $u_1, u_2, . . . , u_m ∈ V$ are linearly independent, then $m\le n$.

Use this to prove that if $V$ has dimension $n$ and $u_1, u_2, . . . , u_n \in V$ are linearly independent then $u_1, u_2,\le, u_n$ form a basis of $V$.

Do I prove that $V$ has a basis with n elements? Not really sure how to approach this proof.

$\endgroup$
1
  • 1
    $\begingroup$ Please, try to make the title of your question more informative. E.g., Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here. $\endgroup$ Jun 1, 2015 at 14:05

5 Answers 5

7
$\begingroup$

You need to show that $u_1,\dotsb,u_n$ span $V$. The easiest way to do this is to suppose that there is a vector $v\in V$ which is not in the span of $u_1,\dotsb,u_n$. Then $u_1,\dotsb,u_n,v$ is a linearly independent set. Then apply your result on the size of linearly independent sets. This will lead to a contradiction and therefore no such $v$ can exists

$\endgroup$
2
  • $\begingroup$ "Then apply your result on the size of linearly independent sets" need to elaborate more n this. $\endgroup$ Oct 5, 2021 at 17:40
  • $\begingroup$ I assume you are saying that a linearly independent set can't be larger than the dimension $V$. you must prove this! $\endgroup$ Oct 5, 2021 at 17:40
2
$\begingroup$

You have to argue by contradiction. Moreover you need that

Let $V$ be a vector space, and suppose $v_1, \dots, v_n$ are linearly dependent vectors spanning $V$. Then there exists $i$ such that $V$ is spanned by $ v_1, \dots, v_{i-1}, v_{i+1}, \dots v_n $ ($v_i$ disappears).

Now, since $V$ has dimension $n$ there exists a basis of $V$: $w_1, \dots, w_n$ . In particular $w_1, \dots, w_n$ are linearly independet.

Suppose by contradiction that $u_1, \dots, u_n$ is not a basis. By hypothesis they span $V$, so we are saying that they are linearly dependent. Then you have that $ u_1, \dots, u_{i-1}, u_{i+1}, \dots u_n $ span $V$ for some $i$, and they are $n-1$ vectors.

Now, applying the proposition you stated, $$\left\{ \begin{matrix} \mbox{$ u_1, \dots, u_{i-1}, u_{i+1}, \dots u_n $ span $V$} \\ \mbox{ $w_1, \dots, w_n$ are linearly independent }\end{matrix} \right. \Longrightarrow n-1 \le n$$ A contradiction.

$\endgroup$
2
  • $\begingroup$ Thank you, but I don't really understand how n-1 relates to m. $\endgroup$
    – Jess
    Jun 1, 2015 at 10:25
  • $\begingroup$ You must see this in this way: if some family of vectors $A$ is linearly independent, and some other family of vectors $B$ spans the whole space, then $A$ has more elements than $B$. I hope that this helps to avoid confusion with $n,m, n-1$. $\endgroup$
    – Crostul
    Jun 1, 2015 at 11:18
2
$\begingroup$

Hint. Assume that $u_1,\ldots,u_n$ DO NOT form a basis of $V$. Then, as they are linearly independent, they DO NOT span $V$. Hence, there exists a vector, say $u_{n+1}$ NOT spanned by the $u_1,\ldots,u_n$. This implies that $u_1,\ldots,u_n,u_{n+1}$ are linearly independent.

This apparently leads to a contradiction...

$\endgroup$
1
$\begingroup$

Just for completeness, although it is certainly the simplest way to prove this result, you don't have to use proof by contradiction.

Instead, since you know that you have an $n$ dimensional vector space there must exist a set of $n$ basis vectors. Call them $\mathbf{b_1}, \dots, \mathbf{b_n}$. Since they are a basis, for each of your vectors $\mathbf{u_i}$ there exist coefficients $a_{ij}$ such that $$ \mathbf{u_1} = a_{11} \mathbf{b_1} + a_{12} \mathbf{b_2} + \dots + a_{1n} \mathbf{b_n} \\ \vdots \\ \mathbf{u_i} = a_{i1} \mathbf{b_1} + a_{i2} \mathbf{b_2} + \dots + a_{in} \mathbf{b_n} \\ \vdots \\ \mathbf{u_n} = a_{n1} \mathbf{b_1} + a_{n2} \mathbf{b_2} + \dots + a_{nn} \mathbf{b_n} $$ You then have $n$ linearly independent equations, which means that you can rearrange these to form new equations $$ \mathbf{b_i} = c_{i1} \mathbf{u_1} + c_{i2} \mathbf{u_2} + \dots + c_{in} \mathbf{u_n} $$ (where $c_{ij}$ are coefficients defined in terms of the $a_{ij}$'s). This means that you have found $n$ linearly independent vectors such that each of the basis vectors $\mathbf{b_i}$ can be written as a linear combination of them. It is a simple consequence of the definition of a basis that this is sufficient to show that $\mathbf{u_1}, \dots, \mathbf{u_n}$ span $V$, and are therefore a basis for $V$.

Aside: if this looks like matrix multiplication, that's because it is! This manoeuvre only works when the matrix is invertible, and the coefficients $c_{ij}$ are exactly the entries in the inverse matrix. If you are interested, try to work through the proof as I've written it, but where the $\mathbf{u_i}$ are not linearly independent, and see where it fails. It can also be instructive to pick a familiar vector space and work through this by hand: I recommend proving that $\left\{ \left(\matrix{1\\0}\right), \left(\matrix{1\\1}\right) \right\}$ is a basis for $\mathbb{R}^2$.

$\endgroup$
2
  • $\begingroup$ This argument skips over the most important problem: why are you able to invert the matrix $[a_ij]$? $\endgroup$
    – egreg
    Jun 2, 2015 at 9:25
  • $\begingroup$ @egreg The idea was to show a "positive" proof; it reduces a problem about vector spaces to a linear algebra question, which is something the questioner might be more familiar with. The invertibility of the matrix is important to the proof, but I glossed over it because it doesn't actually help illustrate the construction: it only matters that it is possible to rearrange the equations, not how or why. Pedagogical opinions may vary, though. :-) $\endgroup$
    – Kara Potts
    Jun 3, 2015 at 7:40
1
$\begingroup$

The “exchange lemma” by Steinitz says something more about your two sets $\{v_1,\dots,v_n\}$ and $\{u_1,\dots,u_m\}$ besides $m\le n$. Precisely, it says that you can replace $m$ elements in the first set with the elements in the second set, so that you still have a spanning set.

In case $m=n$, you replace all the vectors in the given spanning set, so the given linearly independent set is a basis.


The information $m\le n$ is not sufficient to conclude without using specific properties of vector spaces. For instance, you can prove that a linearly independent set in a finitely generated free abelian group must have at most as many elements as the rank of the group (that is, the number of elements in a basis), but it's not true that a linearly independent set with as many elements as the rank is a spanning set.

You can use the auxiliary result, for vector spaces, that every linearly independent set can be extended to a basis; since any two bases have the same number of elements, you're done.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .