Linear Independence: How to maintain it through linear combinations

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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.