0
$\begingroup$

Show that if the set of linearly independent vectors ${X}$ does not span $\mathbb R^n$ then there exists a vector $v \in \mathbb R^n$ s.t. $\{v\} \cup X$ is linearly independent.

My shot at a proof for this by contraposition, let me know when I mess up:

let $X \cup \{v\}$ be linearly dependent $\forall v \in \mathbb R^n$, then

$$\exists \alpha_1 , \dots, \alpha_k\text{ s.t. }v=\alpha_1x_1 +\dots + \alpha_kx_k \forall v \in \mathbb R^n$$

thus by definition of span, $X$ spans $\mathbb R^n$

this is a contradiction of the original proposal, thus $\exists v \in R^n$ s.t. $v \cup X$ is linearly independent

$\endgroup$
11
  • $\begingroup$ Did you really mean $v\cup\mathbb{R}^n$? $\endgroup$ Aug 15, 2018 at 14:02
  • $\begingroup$ nope! fixed it to read $v \cup X$ $\endgroup$ Aug 15, 2018 at 14:02
  • $\begingroup$ Or perhaps $\{v\}\cup X$. $\endgroup$ Aug 15, 2018 at 14:04
  • $\begingroup$ you're correct Thomas, I've changed it. sorry guys, its early out here $\endgroup$ Aug 15, 2018 at 14:06
  • $\begingroup$ If X itself is not linearly independent this statement is false. $\endgroup$
    – Hamed
    Aug 15, 2018 at 14:06

3 Answers 3

2
$\begingroup$

It is mostly correct, but incomplete.

You don't state what your $v$ is in the proof. You need to pick $v$ to be an element of $\mathbb R^n$ which is not in the span of $X$. (Thus, you are using one condition.)

You should also state why $\exists \alpha_1,\dots,\alpha_k.$

If $X\cup\{v\}$ is linearly dependent, then $\exists \beta_0,\dots,\beta_k$ such that $$0=\beta_0 v + \beta_1 x_1+\dots+\beta_k x_k$$ with the $\beta_i$ not all zero.

But if $\beta_0=0$ then $X$ would be linearly dependent. So $\beta_0\neq 0$ and from there you can conclude that $\alpha_i=\frac{-\beta_i}{\beta_0}$ gives you:

$$v=\alpha_1 x_1+\cdots+\alpha_kx_k$$

showing $v\in \operatorname{Span}(X),$ which is a contradiction.


Indeed, this could be stated as a general lemma:

Lemma: If $V$ is a vector space and $X\subset V$, then, for any $v\in V\setminus X$, $X\cup\{v\}$ is linearly independent if and only if $X$ is linearly independent and $v\notin\operatorname{Span}(X).$

This lemma is exactly why you can find $\alpha_1,\dots,\alpha_k.$ Since $X$ is linearly independent, we have, by this lemma, if $X\cup \{v\}$ is linearly dependent, then $v\in\operatorname{Span}(X).$

Aside: This lemma assumes the definition that $\operatorname{Span}(\emptyset)=\{0\}.$


The question has two conditions:

  1. $X$ is linearly independent
  2. $X$ does not span $\mathbb R^n$

Without $(2),$ you cannot find $v.$

Without $(1),$ you cannot prove $X\cup\{v\}$ is linearly independent.

Your proof does not mention where you are using either condition.

$\endgroup$
8
  • $\begingroup$ does the statement, "$\exists \alpha_1 , ... , \alpha_k$ s.t. $\alpha_1x_1 +...+ \alpha_kx_k$" not flow directly from the definition of linear dependence? or is that explanation simply not sufficient for the proof? $\endgroup$ Aug 15, 2018 at 14:18
  • $\begingroup$ Thomas Andrews, there is not mentioned that X is linearly independent $\endgroup$
    – MathBS
    Aug 15, 2018 at 14:18
  • $\begingroup$ @BiswarupSaha Re-read the question, it has been edited. $\endgroup$ Aug 15, 2018 at 14:18
  • 1
    $\begingroup$ @CorranHorn There are two possible definitions of linear dependence, but in either one, you still need to show this, though in some sense it is trivial. For example, why do you have to choose $v$ outside the span of $X$? Why is it important that $X$ is linearly independent? This is the step where you need both conditions. $\endgroup$ Aug 15, 2018 at 14:25
  • 1
    $\begingroup$ Yes. I noticed. My intention was to post the comment under the OP. VERY SORRY about this. I have never had any complaints about YOUR approach to the site. Certain other users OTOH... $\endgroup$ Aug 15, 2018 at 15:26
1
$\begingroup$

Your attempt is basically good, but there's no need to go that route.

Assume $X=\{v_1,\dots,v_r\}$ is linearly independent and let $v\in\mathbb{R}^n$ such that $v$ does not belong to the span of $X$.

Let $\alpha v+\alpha_1v_1+\dots+\alpha_rv_r=0$.

Suppose $\alpha\ne0$: then you get a contradiction (how?).

Therefore $\alpha=0$ and from here it is easy to conclude.

$\endgroup$
0
$\begingroup$

The set $X$ does not generate $\Bbb{R}^n\implies\exists v\in\Bbb{R}^n\backslash X$ such that $v\notin \text{Span}(X)$.
I will show that $X\cup\{v\}$ is linearly independent.
Let us assume on contrary that, $X\cup\{v\}$ is linearly dependent. Then $\exists u_1, u_2, ..., u_k\in X\cup\{v\}$ scalers $a_1, a_2, ..., a_k\text{(not all zero)}\in\Bbb{R}$ such that $a_1 u_1+ a_2u_2+...+a_k u_k=0$
If $u_i\ne v\forall i\in \{1,2,..,k\}$, then it would imply $X$ is linearly dependent (because in that case $\{u_1, u_2, ...,u_k\}\subseteq X$).
So at least one of $u_i$'s must be $v$ (say $u_j)$.
We get $a_j v=a_1 u_1+...+a_{j-1} u_{j-1}+a_{j+1} u_{j+1}+...+a_k u_k$.
Not that $a_j\ne 0$(if not, suppose $a_j=0\implies a_1 u_1+...+a_{j-1} u_{j-1}+a_{j+1} u_{j+1}+...+a_k u_k=0\implies X$ is linearly dependent, contradiction).
So, $a_j^{-1}$ exists in $\Bbb{R}$, then $v=(a_j^{-1} a_1) u_1+...+(a_j^{-1} a_{j-1}) u_{j-1}+(a_j^{-1} a_{j+1})u_{j+1}+...+(a_j^{-1} a_k) u_k\implies v\in\text{Span}(X)$, contradiction.
So, we must have $X\cup\{v\}$ is linearly independent.

$\endgroup$

You must log in to answer this question.

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