# Prove that if a vector space has dimension n then any n + 1 of its vectors are linearly dependent. (Linear Algebra )

I cannot seem to figure out how to prove the following:

"Prove that if a vector space has dimension $$n$$ then any $$n + 1$$ of its vectors are linearly dependent."

I reckon applying proof by contradiction might be a useful approach, but cannot seem to figure it out. Maybe weak induction as well? How would one go about this?

Below Edit 1 - Made to accomodate question requesting further specification:


"Linearly independent": A set of vectors $$\{a_1, a_2,a_3...,a_n\}$$ is seen as being linearly independent if $$x_1a_1 + x_2a_2 + x_3a_3 + x_na_n = 0 \space (null vector)$$ only is satisfied for $$x_1 = x_2 = x_3 = x_n = 0$$, then the set $$\{a_1, a_2,a_3...,a_n\}$$ is linearly independent. ($${x_1,x_2,x_3,...,x_n}$$ are arbitrary scalars)

"Definition of dimension": Let $$V$$ be a vector space. The number of vectors in a basis for $$V$$ is called the dimension of $$V$$, and is written $$\dim V$$.

• What is your definition of "linearly independent" (there are many equivalent definitions, so it is important that we know which one(s) you are allowed to use in your proof). – kccu Apr 1 '19 at 19:42
• This answer to this question probably depends on the definition of dimension you have. – Bernard Apr 1 '19 at 19:42
• Perhaps contrapositive is best. If you have $n+1$ linearly independent vectors in a vector space, either they span or they do not. What do you conclude about the dimension? – Ted Shifrin Apr 1 '19 at 20:15
• Hi @kccu, I appreciate your interest. I have hereby specified the term linearly independent as I was not aware of the fact that the term had multiple definitions. Thank you. – ms99 Apr 1 '19 at 20:15
• There is a nice proof at math.harvard.edu/archive/23b_spring_04/hw3sc.pdf on page 3, proof 3 that proves this. – user648059 Apr 1 '19 at 22:09

## 3 Answers

For sake of contradiction, suppose there is a set of vectors $$\{u_1, \ldots, u_{n+1}\}$$ in an $$n$$-dimensional vector space $$V$$ such that $$\{u_1, \ldots, u_{n+1}\}$$ are linearly independent. Let $$B = \{v_1, \ldots, v_n\}$$ be a basis for $$V$$. Then $$B$$ spans $$V$$, and we can write

$$u_1 = a_1v_1 + \cdots + a_nv_n$$

Since $$\{u_1, \ldots, u_{n+1}\}$$ is linearly independent, it follows that no $$u_i$$ can be zero. This implies that there is at least one $$j$$ such that $$a_j \neq 0$$. Without loss of generality, assume that $$j = 1$$. Then we may write

\begin{aligned} v_1 & = \frac{1}{a_1}u_1 - \frac{a_2}{a_1}v_2 - \cdots - \frac{a_n}{a_1}v_n & (1) \end{aligned}

Now let $$B_1 = \{u_1, v_2, \ldots, v_n\}$$. Since $$B$$ spans $$V$$, we can write

$$v = \lambda_1v_1 + \cdots + \lambda_nv_n$$

for any $$v\in V$$. By $$(1)$$, we have

\begin{align} v & = \lambda_1(\frac{1}{a_1}u_1 - \frac{a_2}{a_1}v_2 - \cdots - \frac{a_n}{a_1}v_n) + \lambda_2v_2 + \cdots + \lambda_nv_n \\ & = \frac{\lambda_1}{a_1}u_1 + \frac{-\lambda_1 a_2}{a_1}v_2 + \lambda_2v_2 + \cdots + \frac{-\lambda_1 a_n}{a_1}v_n + \lambda_nv_n \\ & = \frac{\lambda_1}{a_1}u_1 + (\frac{-\lambda_1 a_2}{a_1} + \lambda_2)v_2 + \cdots + (\frac{-\lambda_1 a_n}{a_1} + \lambda_n)v_n \\ & = \lambda_1^{'}u_1 + \lambda_2^{'}v_2 + \cdots + \lambda_n^{'}v_n \\ \end{align}

Thus, we can write any $$v \in V$$ in terms of the elements of $$B_1$$, which means $$B_1$$ spans $$V$$.

Suppose we have obtained $$B_{i - 1} = \{u_1,\ldots, u_{i-1},v_i,\ldots, v_n\}$$ and have shown that it spans $$V$$. Then we may write

$$u_i = a_1u_1 + \cdots + a_{i-1}u_{i-1} + a_iv_i + \cdots + a_nv_n$$

for some $$a_1, \ldots, a_n \in \mathbb{R}$$. Since $$u_i$$ is a non-zero vector, there must be a $$k$$ such that $$a_k \neq 0$$. Let $$j$$ be the largest index for which $$a_j \neq 0$$. This $$j$$ must satisfy $$j \geq i$$, for if $$j < i$$, then $$a_i = a_{i+1} = \ldots = a_n = 0$$, which implies that

$$u_i = a_1u_1 + \cdots + a_{i-1}u_{i-1}$$

which contradicts that $$\{u_1, \ldots, u_{n+1}\}$$ is linearly independent. Without loss of generality, assume $$j = i$$. Then we can switch $$u_i$$ with $$v_i$$ in $$B_{i-1}$$ to obtain $$B_i = \{u_1,\ldots, u_{i-1}, u_i,v_{i+1},\ldots, v_n\}$$, which can be shown to span $$V$$ by a substitution similar to the one using $$(1)$$ above.

Continue to do this until the $$n$$th step, where $$B_n = \{u_1, u_2, \ldots, u_n\}$$. Previously, we showed that if $$B_{i-1}$$ spans $$V$$, then our operation of switching $$u_i$$ with $$v_i$$ to get $$B_i$$ also makes $$B_i$$ span $$V$$. Therefore, $$B_n$$ must span $$V$$ (by induction starting with $$B_1$$). Since $$u_{n+1}$$ is in $$V$$, and since $$B_n$$ spans $$V$$, we can write

$$u_{n+1} = a_1u_1 + \cdots + a_nu_n$$

for some $$a_1, \ldots, a_n \in \mathbb{R}$$. But this contradicts that $$\{u_1, \ldots, u_{n+1}\}$$ is linearly independent. Therefore, it must not be the case that $$\{u_1, \ldots, u_{n+1}\}$$ is linearly independent, which is to say that $$\{u_1, \ldots, u_{n+1}\}$$ must be linearly dependent. $$\tag*{\blacksquare}$$

If there are $$n+1$$ linearly independent vectors, then $$\operatorname{dim} V\ge n+1\gt n \Rightarrow \Leftarrow$$.

(This is the contrapositive, as @Ted Shifrin suggested. )

Let $$n$$ be the dimension of $$V$$. Let $$u_{i}\in V$$ for $$i=1$$ to $$n{+}1$$ be a set of linearily independent set. Hence, $$u_{i}$$ for $$i{=}1$$ to $$n$$ are also linearly independent, hence $$u_{i}$$ for $$i=1$$ to $$n$$ is a basis set for $$V$$ (you need to prove that let $$V'= \text{span}\{u_{1},u_{2}\cdots u_{n}\}$$, then $$V'\subseteq V$$ and $$\text{dim}(V')=\text{dim}(V)=n$$, then $$V'=V$$, see this ) . Since $$u_{n+1}\in V$$, thus it has a unique representation using the basis vectors; thus

$$u_{n+1} = \sum_{i=1}^{n}\alpha_{i}u_{i}$$

Hence, $$u_{i},\ i\in 1\cdots n{+}1$$ are linearly dependent.