Prove that the set $S \cup \{v\}$ is linearly independent.

Let $S$ be a linearly independent set of vectors in $\mathbb R^n$. Suppose that $v$ is a vector in $\mathbb R^n$ that is not in the span of $S$. Prove that the set $S \cup \{v\}$ is linearly independent.

Would a proof like the one below work?

Let $S = \{u_1, u_2, \ldots , u_k\}$. Given is if $a_1u_1 + a_2u_2 + a_3u_3 +\ldots +a_ku_k = 0$, then $a_i = 0$.

Consider $a_1u_1 + a_2u_2 + ...+a_ku_k - bv = 0$. Let $x_i$ be the elements of $u_1$, $u_i$ be the elements of $u_2$ and $z_i$ be the elements in $u_k$.

Then componentwise we have:

$a_1x_1 + a_2y_1 + \ldots + a_kz_1 - bv_1 = 0$

$a_1x_2 + a_2y_2 + \ldots + a_kz_2 + bv_2 = 0$

$\ldots$

$\ldots$

$a_1x_k + a_2y_k + \ldots + a_kz_k - bv_k = 0$

We can take a random row from the system above :

$a_1x_i + a_2y_i + \ldots + a_kz_i - bv_i = 0$ where $bv_i = a_1x_i + a_2y_i + \ldots + a_kz_i$ so that

$(a_1x_i + a_2y_i + \ldots + a_kz_i) + (a_1x_i + a_2y_i + \ldots + a_kz_i) = a_i(x_i + x_i) + a_2(y_i – y_i) + \ldots + a_k(z_i + z_i) = 0$.

Since no vector in $S$ is zero, none of $x_i + x_i, y_i + y_i, \ldots, z_i + z_i$ is $0$ meaning $a_i = 0.$

edit:

I think one of the problems of this proof is that if, say, $(0, 4, 3, \ldots, 8)$ and $(0, 7, 2, \ldots, 4) \in S$, then one of $x_i + x_i, y_i + y_i, \ldots, z_i + z_i$ is $0$, so the proof fails.

• The sentence "Let $x_i$ be the elements of $u_1$, $u_i$ be the elements of $u_2$ and $z_i$ be the elements in $u_k$" is very confusing. Can you clarify? – user37238 Jan 12 '16 at 15:39
• (1) I don’t get how you arrive at the conclusion that $(a_1 x_i + \dotsb + a_k z_i) +(a_1 x_i + \dotsb + a_k z_i) = 0$. (2) When working with an unknown amount of vectors, it is unwise to use letters $x$, $y$, $z$ for the entries; by your notation, how are the entries of $u_3$ called? Instead, use something like $x^{(j)}_1, \dotsc, x^{(j)}_k$ for the entries of $u_j$. (3) This problem actually becomes more complicated by looking at entries of the vectors. (4) In its current form there are some sign errors. I don’t know if they effect your calculation, which I don’t understand. – Jendrik Stelzner Jan 12 '16 at 15:39
• $u_1 = (x_1, x_2, x_3, \ldots x_k)$ – reddit Jan 12 '16 at 15:40

As others have said, there is confusion in your notation, and much of it is unnecessary. You don't need to consider individual components of the vectors. While it is helpful to look over and correct the errors in your own proof, I will provide you with a proof sketch for help later.

Let's get things straight. $S$ is linearly independent, and $v$ is not in $Span (S)$. We are to show that $S\cup \{v\}$ is linearly independent. You should ask yourself what each of these previous statements means in terms of vectors: for instance, any nontrivial linear combination of vectors of $S$ is nonzero. If we assume for contradiction that $S\cup \{v\}$ is linearly dependent, then there is some linear combination of vectors in $S$ that equals a multiple of $v$. If this multiple is $0$, this is a contradiction since $S$ is linearly independent. If this multiple is nonzero, then $v$ can be written as some linear combination of vectors in $S$ which means that $v$ is in the span of $S$, also a contradiction. Thus $S\cup \{v\}$ is independent.

While this may look dense, it could be improved upon with the addition of symbolic representation of the vectors discussed. This is the idea, so try to sift through it.

• This is actually super clear. – reddit Jan 12 '16 at 16:59

This question is tackled surprisingly quickly by using the contrapositive.

Given the premise $S\subset\mathbb{R}^n$ is linearly independent, you are trying to prove $p\implies q$, where:

• $p$ is "$v\notin \text{span}S$"
• $q$ is "$S\cup \{v\}$ is linearly independent".

The contrapositive works by proving $\text{not}\;q\implies \text{not}\;p$. Now:

• $\text{not}\;q$ is the statement "$S\cup \{v\}$ is linearly dependent".
• $\text{not}\;p$ is the statement "$v\in \text{span}S$".

Given that $S$ was previously linearly independent, any linear dependence relation on $S\cup \{v\}$ must involve a $v$ term, which means that we can easily make $v$ the subject of such an equality, which directly expresses $v$ as a member of $\text{span}S$. We are thus done.