2
$\begingroup$

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

$\endgroup$
7
  • 3
    $\begingroup$ 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). $\endgroup$ – kccu Apr 1 '19 at 19:42
  • 8
    $\begingroup$ This answer to this question probably depends on the definition of dimension you have. $\endgroup$ – Bernard Apr 1 '19 at 19:42
  • $\begingroup$ 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? $\endgroup$ – Ted Shifrin Apr 1 '19 at 20:15
  • $\begingroup$ 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. $\endgroup$ – ms99 Apr 1 '19 at 20:15
  • 1
    $\begingroup$ There is a nice proof at math.harvard.edu/archive/23b_spring_04/hw3sc.pdf on page 3, proof 3 that proves this. $\endgroup$ – user648059 Apr 1 '19 at 22:09
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.