# Linear Independence: How to maintain it through linear combinations

I'm working on problems from the third edition of "Linear Algebra Done Right" by Sheldon Axler. In Section 2.A there is the following problem (problem #6):

Suppose $v_1$, $v_2$, $v_3$, $v_4$ is linearly independent in $V$. Prove that the list $v_1-v_2,v_2-v_3,v_3-v_4,v_4$ is also linearly independent.

This begs the question: What is the general solution to this problem? In other words, given a list of m linearly independent vectors $v_1,...,v_m$, define $w_i\in$ span ($v_1,...,v_m$). What are the necessary and sufficient conditions so that $w_1,...,w_m$ is also linearly independent?

I feel uncomfortable with this problem because I can't see it clearly. It seems like its a hidden combinatorial exercise in this book. Linear Independence seems harder to verify the greater the value of $m$. I'm not even sure that my intuition is right and so I would appreciate any feedback.

• Write up the coefficients (coordinates) of each $w_j$ w.r.t. $v_i$ and put these in a matrix. Sufficient and necessary condition is that its determinant is nonzero – Berci Jun 20 '18 at 22:25
• One approach would be to let $w_i = c_{1,i}v_1+c_{2,i}v_2+c_{3,i}v_3,\dots,c_{m,i}v_m$ and consider the matrix $\begin{bmatrix}c_{1,1}&c_{1,2}&\dots&c_{1,m}\\c_{2,1}&c_{2,2}&\dots\\\vdots\\&&&c_{m,m}\end{bmatrix}$ and its determinant. – JMoravitz Jun 20 '18 at 22:26
• If $$c_1v_1+c_2v_2+c_3v_3+c_4v_4=0$$ implies $c_1=c_2=c_3=c_4=0$, then $$b_1(v_1-v_2)+b_2(v_2-v_3)+b_3(v_3-v_4) + b_4v_4 = b_1v_1 + (b_2-b_1)v_2 + (b_3-b_2)v_3 + (b_4-b_3)v_4 = 0$$ implies that $b_1=b_2-b_1=b_3-b_2=b_4-b_3=0$, so that $b_1=b_2=b_3=b_4=0$. – Math1000 Jun 20 '18 at 22:28
• For the record I don't think we should use determinants if they're following Axler's book. Isn't the whole point to do as much as possible without determinants. (He did after all write "down with determinants" )axler.net/DwD.html – N8tron Jun 21 '18 at 3:03

The list $v_1,\dots,v_n$ is a basis of $U$, the subspace they span. So we can work in $U$ and consider $$w_j=\sum_{i=1}^n \alpha_{ij}v_i \qquad(j=1,2,\dots,m)$$ Then the coordinate vector of $w_1$ with respect to the chosen basis is $$\begin{bmatrix} \alpha_{11} \\ \alpha_{21} \\ \vdots \\ \alpha_{n1} \end{bmatrix}$$ and, more generally, the coordinate vector of $w_j$ is $$\begin{bmatrix} \alpha_{1j} \\ \alpha_{2j} \\ \vdots \\ \alpha_{nj} \end{bmatrix}$$

A set of vectors is linearly independent if and only if the set of their coordinate vectors is. Thus the necessary and sufficient condition is that the matrix $[\alpha_{ij}]$ has rank $m$.

In your case the matrix is $$\begin{bmatrix} 1 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \end{bmatrix}$$ that indeed has rank $4$.

• This is great! Thank you for putting it in those terms, it helped me to see yet another application of matrices. I just want to clarify that if the matrix [$a_ij$] has rank $n$. then this is the same as saying that dim span ($w_1,...,w_m$) = m which would imply that $w_1,...,w_m$ are linearly independent. – Sebastian Erquiaga Jun 21 '18 at 3:21
• @SebastianErquiaga I worked in the assumption that we had $n$ vectors $w_1,\dots,w_n$. I fixed for any number of them. The matrix will have $n$ rows and $m$ columns. – egreg Jun 21 '18 at 6:44

By definition of Linear independence, 4 vectors $(v_1-v_2),(v_2-v_3),(v_3-v_4), v_4$ are linearly independent iff $a(v_1-v_2) + b(v_2-v_3) + c(v_3-v_4) + dv_4$ is nonzero for any choice of scalars $a,b,c,d$ where at least one is nonzero. However, as we are given $v_1,v_2,v_3,v_4$ are linearly independent, we already know that $a'v_1+b'v_2+c'v_3+d'v_4$ is nonzero for any choice of $a',b',c',d'$ such that at least one of $a',b',c',d'$ is nonzero. Thus we observe the following:

Fact 1: Let $a,b,c,d$ be scalars not all zero. Then if one can show that $a(v_1-v_2) + b(v_2-v_3) + c(v_3-v_4) + dv_4$ is $a'v_1+b'v_2 + c'v_3 + d'v_4$ for some scalars $a',b',c',d'$ not all zero, then that will imply linear independence of the 4 vectors $(v_1-v_2),(v_2-v_3),(v_3-v_4), v_4$

Make sure you see can this!

But

$$a(v_1-v_2) + b(v_2-v_3) + c(v_3-v_4) + dv_4 =av_1 + (b-a)v_2 + (c-b)v_3 + (d-c)v_4.$$

So set $a'=a$, $b'=(b-a)$, $c'=(c-b)$, and $d'=(d-c)$. If $a$ is nonzero then $a'$ will be nonzero. Otherwise if $a$ is zero and $b$ is nonzero then $b'$ is nonzero. Otherwise if $b$ is zero and $c$ nonzero then $c'$ is nonzero. Otherwise $d$ must be nonzero so $s'$ must be nonzero. Thus this and Fact 1 imply linear independence of the 4 vectors $(v_1-v_2),(v_2-v_3),(v_3-v_4), v_4$.

As far as a general answer to your question, the $w_i$s form a matrix; indeed write $w_i = \sum_j a_{ji}v_j$ and let $A$ be the matrix where the $ji$-th entry (the entry in the $j$-th column $i$-th row) is $a_{ji}$. Then if the rows of $A$ are linearly independent then $w_1,\ldots, w_m$ are linearly independent. And if $m=n$ i.e., $A$ is square then $w_1,\ldots, w_n$ are linearly independent iff determinant of $A$ is nonzero. There is an algorithm to check linear independence that runs in quadratic time I believe.

A linear independent system $v_1$, $v_2$, $v_3$...$v_n$ is linear independent if the equation $a_1v_1 + a_2v_2 + a_3v_3 + ... a_nv_n = 0$ is true only when $a_1 = a_2 = a_3 =...=a_n = 0$, in other words, you can not demonstrate one vector by other vectors.

To make it clearer, if an arbitrary $v_i$ in the given set can be written as $v_i = bv_j + cv_k$, which mean it can be demonstrated by two other vectors, the system won't be linear independent anymore.

So if another set $v'_1$, $v'_2$, $v'_3$...$v'_n$ defined by $v_1$, $v_2$, $v_3$...$v_n$, you just need to consider the equation $a'_1v'_1 + a'_2v'_2 + a'_3v'_3 + ... a'_nv'_n = 0$ which I'm sure that it can somehow be rewritten as $a''_1v_1 + a''_2v_2 + a''_3v_3 + ... a''_nv_n = 0$

Because $v_1$, $v_2$, $v_3$...$v_n$ is linear independent, $a''_1 = a''_2 = a''_3 =...=a''_n = 0$, so you just need to find the relation between $a''_1, a''_2, a''_3,....,a''_n$ and $a'_1,a'_2,a'_3,...,a'_n$ to prove that $a'_1 = a'_2 = a'_3 =...=a'_n = 0$, which meant $v'_1$, $v'_2$, $v'_3$...$v'_n$ is linear independent.