# Proving linear independence of a set of sums of linearly independent vectors

Need help proving this, I struggle with proofs overall so feel free to nitpick:

Let $$\{v_1, ... , v_n\} \in V$$. Show that if $$\{v_1, ... , v_n\}$$ is linearly independent, then $$\{v_1, v_1 + v_2, v_1 + v_2 + v_3, ... , v_1 + ... + v_n\}$$ is linearly indepedent.

Proof:

Assume $$\{v_1, ... , v_n\} \in V$$ is linearly indepedent.

Linear independence implies for $$c_1v_1+...+c_nv_n=0$$ for all $$v\in V$$ and $$c_i \in R$$ $$c_1 = c_2 = ... = c_n = 0$$

Conceptually I understand why $$\{v_1, v_1 + v_2, v_1 + v_2 + v_3, ... , v_1 + ... + v_n\}$$ is linearly indepedent. I am just unsure how to continue the proof other than to say each sum is in the initial sets linear combination which we know is linearly independent so adding the sums onto each other would just create another linear combination where the only solution to the homogenous system is 0 for all scalar $$c_i$$.

• Proof by contradiction is the way to go here. After your contradiction assumption, take pairwise differences. – Don Thousand Oct 4 '18 at 22:52
• The map from the first set of vectors to the second set is upper-triangular, with an easy to calculate determinant. If you don’t want to do it this way, just write out an arbitrary linear combination $a_1 v_1 + a_2 (v_1 + v_2) + \cdots$, rearrange to a combination in only the $v_i$, and apply the independence assumption. – Joppy Oct 4 '18 at 23:19

Suppose that $$\{v_1,v_2,\dots,v_n\}$$ is linearly independent. To show linear independence of $$\{v_1,v_1+v_2,v_1+v_2+v_3,\dots,v_1+v_2+\dots+v_n\}$$ take a linear combination and set it equal to zero, then prove that the coefficients are necessarily zero. Observe that if, \begin{align} a_1(v_1) + a_2(v_1+v_2) + \dots + a_n(v_1+v_2+\dots+v_n) &= 0\\ \Rightarrow \left(\sum_{i=1}^n a_i\right) v_1 + \left(\sum_{i=2}^n a_i\right) v_2 + \dots + a_nv_n &= 0 \end{align} Which by linear independence of $$\{v_1,v_2,\dots,v_n\}$$ implies that $$\left(\sum_{i=1}^n a_i\right), \left(\sum_{i=2}^n a_i\right),\dots, a_n$$ are all equal zero, from which it's easy to see that $$a_1,a_2,\dots,a_n$$ are all zero as well so we are done.

A first observation is that if $$\{v_1, \dots, v_n\}$$ are linearly independent, then $$v_n \not \in \langle v_1, \dots, v_{n-1}\rangle$$. If it were so, there would be a linear combination $$a_1v_1 + \dots + a_{n-1}v_{n-1} = v_n$$ with not all $$a_i$$ being zero (because if not $$v_n = 0$$), and so substracting $$v_n$$ we see that the original set was not l.i. thus reaching a contradiction.

Having said that, you can prove it by induction on $$n$$. The case $$n = 2$$ should be fairly straightforward, so I'll prove the inductive step. Let $$\{v_i\}_{i = 1}^{n+1}$$ be a set of l.i. vectors. In particular, $$v_1, \dots, v_n$$ are l.i. and so by inductive hypothesis, so is $$\{v_1, \dots, v_1 + \dots + v_n \}$$. Now, if

$$a_1v_1 + \dots + a_n\sum_{i = 1}^nv_i + a_{n+1}\sum_{i = 1}^{n+1}v_i = 0 \tag{1}$$

then,

$$a_1v_1 + \dots + a_n\sum_{i = 1}^nv_i + a_{n+1}\sum_{i = 1}^{n}v_i = -a_{n+1}v_{n+1}$$

and in particular by 'unpacking' the sums, $$a_{n+1}v_{n+1} \in \langle v_1 , \dots, v_n\rangle$$. If $$a_{n+1} \neq 0$$, that would imply $$v_{n+1} \in \langle v_1 , \dots , v_n \rangle$$ which we have already noted cannot happen. Thus, $$a_{n+1} = 0$$ and then $$(1)$$ becomes

$$a_1v_1 + \dots + a_n\sum_{i = 1}^nv_i= 0$$

which imply $$a_i = 0$$ for all $$i$$, because once again by inductive hypothesis, $$\{v_1, \dots, v_1 + \dots + v_n \}$$ is linearly independent.

It is not restrictive to work in the span of $$\mathcal{B}=\{v_1,v_2,\dots,v_n\}$$. The coordinates of the new vectors with respect to the basis $$\mathcal{B}$$ form the matrix $$\begin{bmatrix} 1 & 1 & 1 & \dots & 1 & 1 & 1 \\ 0 & 1 & 1 & \dots & 1 & 1 & 1 \\ 0 & 0 & 1 & \dots & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \dots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & 0 & 1 & 1 \\ 0 & 0 & 0 & \dots & 0 & 0 & 1 \end{bmatrix}$$ and this matrix is invertible, being upper unitriangular.