2
$\begingroup$

I've been reading the wikibook on Linear Algebra and in the section 'Linear Independence and Subset Relations' it defines the following lemma:

Lemma 1.14: Any subset of a linearly independent set is also linearly independent. Any superset of a linearly dependent set is also linearly dependent.

The following is my proof of the statement "Any subset of a linearly independent set is also linearly independent": $$S= \{v_1, \dots, v_n\}\space |\space a_1\cdot v_1 +\space ... +\space a_n\cdot v_n =0$$ Let $$S_i=S-\{v_i\}$$ $S_i$ is linearly dependant if $$\sum_{j=1,\space j\neq i}^n (b_j\cdot v_j)$$

That is:

$$\sum_{j=1}^n (b_j\cdot v_j) - 0\cdot v_i$$ Let $a_i = b_i$ and using the constraint in the definition of $S$ we conclude $S_i$ is linearly independent.

I'm uncertain about the validity/notation regarding my assignment of $a_i = b_i$ in the proof. Is there a more correct approach to this proof? I often find myself needing to make a set of 'placeholder' (for a lack of a better word) variables map to an equivalent set of variables and am concerned I'm doing it wrongly. The book's proof is simply 'This is clear'.

Second Attempt

Let S be a linearly independent set of unique vectors $v_1,…,v_n$ such that $n\in Z$ and $n\geq1$. Without a loss of generality let a set $U$ be a linearly dependent subset of $S$ such that $U= \{v_1,…,v_i \}$ for some $i<n$. Because $U$ is a linearly dependent set, the element $v_1$ of $U$ can be written as a linear combination of the other elements of $U$ where coefficient $b_1\neq0$ and there must be coefficients which satisfy the equation other than the trivial case of $b_2=\dots =b_i=0$.

$$ v_1=(-b_2/b_1 )v_2+\dots +(-b_i/b_1 )v_i $$

Given the independence of $S$, $v_1$ cannot be written as a non-trivial linear combination of vectors $v_1,\dots ,v_n$ such that coefficient $a_1\neq 0$ and not all coefficients $a_2,…,a_n$ are zero. That is:

$$v_1\neq(-a_2/a_1 )v_2+\dots +(-a_n/a_1 )v_n$$

Expanding out this equation we have:

$$v_1\neq(-a_2/a_1 )v_2+\dots +(-a_i/a_1 )v_i+(-a_n/a_1 )v_n$$

Using the dependence of $U$, which states $v_1$ be written as a linear combination of the other elements of $U$ (i.e $\{v_2,…,v_i\}$), where the vector coefficients are not all zero, we get:

$$v_1\neq(v_1)+(-a_n/a_1 )v_n$$

Now given that not all the coefficients of $v_2,\dots,v_i$, were zero we can have $a_n=0$ and still satisfy both conditions of the equation, namely that $a_1\neq 0$ and not all the coefficients are $0$. This yields $$v_1\neq v_1$$ This cannot be true so therefore the assumption that $U$ is dependant must be wrong.

$\endgroup$
1
  • 1
    $\begingroup$ At the beginning, a better formulation is, without loss of generality, assume $b_1\ne 0$, so that $v_1$ is a linear combination of $v_2, ..., v_i$. Then after you write the formula out, you can say that it is equivalent as $v_1=(-b_2/b_1 )v_2+\dots +(-b_i/b_1 )v_i+0\cdot v_{i+1}+\cdots + 0\cdot v_n$. This gives a contradiction because $S$ is a linearly independent set. $\endgroup$ Commented Sep 2, 2015 at 11:33

3 Answers 3

Reset to default
2
$\begingroup$

Your first attempt is completely wrong, I'm afraid. The second attempt contains a good idea that can be fixed to provide a proof.

Suppose $\{v_1,v_2,\dots,v_n\}$ is a linearly independent set and that (without loss of generality) $\{v_1,\dots,v_i\}$ is a linearly dependent subset. Then $i\ge1$, because the empty set is linearly independent. Thus, again without loss of generality, we can write $$ v_1=b_2v_2+\dots+b_iv_i $$ that can be also written $$ v_1=b_2v_2+\dots+b_iv_i+0v_{i+1}+\dots+0v_{n} $$ which is a contradiction.

However, it's better to use a different definition/characterization of linearly dependent sets: saying that $\{v_1,\dots,v_i\}$ is linearly dependent means that there exist scalars $a_1,\dots,a_i$ not all zero such that $$ a_1v_1+\dots+a_iv_i=0 $$ Now we can rewrite this as $$ a_1v_1+\dots+a_iv_i+a_{i+1}v_{i+1}+\dots+a_nv_n=0 $$ where $a_{i+1}=\dots=a_n=0$. The scalars $a_1,\dots,a_i,a_{i+1},\dots,a_n$ are not all zero, so the set $\{v_1,\dots,v_n\}$ is linearly dependent.

$\endgroup$
1
$\begingroup$

There are several mistakes in your proof. First of all, it is not clear what you want to say in your first line. You can assume $$S= \{v_1, \dots, v_n\}\space$$ and assume it is linearly independent. But that does not tell you the equation you wrote.

I suppose you want to show it by contradiction. Since the question says "any subset", your assumption has to include a general subset. WLOG, we can assume the subset $$\{v_{1}, \dots, v_{i}\}\subset S$$ is linearly dependent, for some $i<n$. So we have $$b_1v_1+\cdots b_iv_i=0$$

for some constants $b_1, \dots, b_i$ which are not all zeros.

Now see if you can proceed from here.

$\endgroup$
5
  • $\begingroup$ So: $v_1 = (-b_2/b_1)v_2 + \dots + (-b_n/b_1)v_n$ however given the dependence of $S$, $v_1$ can not be a linear combination of $\{v_1,\dots ,v_n\}$ hence the assumption that $\{v_1,\dots,v_i\} \subset S$ is dependant must be false? $\endgroup$ Commented Sep 2, 2015 at 9:42
  • $\begingroup$ This argument skipped some steps. It ignored the difference between $i$ and $n$. You have to expand the equation to get $n$. Also you are assuming $b_1$ is the nonzero constant. You can of course assume that, but need to add a sentence: "Without loss of generality (WLOG), assume $b_1\ne 0$". And you have a typo in your first line. You meant "the independence of $S$", right? $\endgroup$ Commented Sep 2, 2015 at 9:48
  • $\begingroup$ Ah yes I did mean to say independence. I'll have another go writing the proof and place it in my question. $\endgroup$ Commented Sep 2, 2015 at 9:51
  • $\begingroup$ just added my new attempt. I feel that my language is a bit verbose but I'm not sure how to be more articulate without losing detail. $\endgroup$ Commented Sep 2, 2015 at 10:41
  • $\begingroup$ I added comment after your post. This can be also extended to use @drhab's definition. That was my intention at first. However your approach is also correct. You are using the fact that the set is linearly dependent if "one of them can be written as linear combination of the others". $\endgroup$ Commented Sep 2, 2015 at 11:56
1
$\begingroup$

I start with an alternative definition.

If $V$ is a vector space and $S\subset V$ then $S$ is a linearly independent set if the statement $$a_1v_1+\cdots+a_nv_n=0\implies a_1=\cdots=a_n=0$$ is true whenever the $v_i$ are distinct elements of $S$. This for every nonnegative integer $n$.

Then it follows immediately that a subset $T$ of a linearly dependent $S$ will also be linearly indepent, since distinct elements of $T$ are also distinct elements of $S$.

The definition on wikibook is wrong. It says:

A subset of a vector space is linearly independent if none of its elements is a linear combination of the others.

That is not correct. If $S=\{0\}$ then there are no "others" so $0$ cannot be written as a linear combination of the others. Nevertheless $\{0\}$ is not linearly independent.

edit:

"wrong" is a bit too strong here. The "empty sum" is usually defined as $0$ in this context. See the comment of @egreg on this question.

Nevertheless I advice you strongly to drop the wikibook statement as "definition" and accept it as theorem that can be proved on base of the definition in my answer.

$\endgroup$
3
  • $\begingroup$ Thanks for pointing out the part about $S=\{0\}$. I follow the logic about how if the elements of $S$ are independent then subset of these must be. It's very intuitive but I was trying to also write a formal proof of it. Based of @KittyL's answer I may have been able to correct the proof I wrote in my question. $\endgroup$ Commented Sep 2, 2015 at 9:46
  • $\begingroup$ In my definitions, $0$ is a linear combination of any set of vectors (including the empty set), so in the set $\{0\}$ there is a vector which is a linear combination of the others (that is, of no vector at all). But I agree that the Wikibook definition is bad anyway: the fact that in a linearly dependent set one of the vectors is a linear combination of the remaining ones is better a theorem than a definition. $\endgroup$ Commented Sep 2, 2015 at 10:48
  • $\begingroup$ @egreg Thank you. I edited and asked attention for your comment. $\endgroup$ Commented Sep 2, 2015 at 11:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.