# If $n=\dim(V)$ and $n$ vectors are linearly independent, then they form a basis

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.

• 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. Jun 1, 2015 at 14:05

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

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

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.

• Thank you, but I don't really understand how n-1 relates to m.
– Jess
Jun 1, 2015 at 10:25
• 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$. Jun 1, 2015 at 11:18

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.

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$.

• This argument skips over the most important problem: why are you able to invert the matrix $[a_ij]$? Jun 2, 2015 at 9:25
• @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. :-) Jun 3, 2015 at 7:40

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.