linear independence of $\{x_j-x_i\}_{j=1 ,\\j \ne i}^{k+1}$?

Question

Show that if the set $\{x_2-x_1,...,x_{k+1}-x_1\} \subset \mathbb{R}^n$ is linearly independent then the following set is also linearly independent:

$$\{x_1-x_i,...,x_{i-1}-x_i,x_{i+1}-x_i,...,x_{k+1}-x_i\}$$

Answer 1

Hint:

For fixed $i$, set up $$ \sum_{j=1\\j\neq i}^{k+1}\mu_j(x_j-x_i)=0. $$ Then by adding and subtracting $x_1$ inside the parentheses, we get \begin{align} 0&=\sum_{j=1\\j\neq i}^{k+1}\mu_j((x_j-x_1)-(x_i-x_1)) \\ &=\sum_{j=2\\j\neq i}^{k+1}\mu_j(x_j-x_1)-(x_i-x_1)\sum_{j=1\\j\neq i}^{k+1}\mu_j. \end{align}

Answer 2

I think it’s more simple than that, at first you should now that if you have a linear independent set, then a same size combination of this set it’s also l.i, so you just have to use the linear combination above and that’s it. The proof of this statement it’s essentially by contradiction.

Let’s have $\{x_1,\dots,x_n\}$ an l.i. set, want to proof that this happens if and only if $\{x_1,\dots,x_i+kx_j,\dots,x_n\}$ it’s a l.i. set for each $i,j$. Let’s make left to right, if $\{x_1,\dots,x_i+kx_j,\dots,x_n\}$ isn’t l.i. then we would have that for some index (not necessarily $i$ or $j$) it’s a linear combination of the rest, then:

1. If $x_l$, for $l\in\{1,\dots,n\}-\{i,j\}$ it’s a linear combination of the other elements of the set then the contradiction it’s obvious because $x_l\in\{x_1,\dots,x_n\}$.
2. Other wise the argument it’s pretty much the same, if $x_i+kx_j$ it’s a linear combination of the other elements in $\{x_1,\dots,x_i+kx_j,\dots,x_n\}$ then $x_i\in \{x_1,\dots,x_n\}$ it’s a linear combinaton of elements in that set.

So it’s clear that you can make finite linear combinations of a l.i. set and you will get another l.i. set.

Answer 3

The format of the vectors in question, suggests that we may be able to represent the vectors $$\{x_1-x_i,...,x_{i-1}-x_i,x_{i+1}-x_i,...,x_{k+1}-x_i\}$$ as a linear combination of $$\{x_2-x_1,...,x_{k+1}-x_1\} \subset \mathbb{R}^n.$$ To test this hypothesis, let us define $$v_j\triangleq x_{j+1}-x_1\quad,\quad j=1,2,\cdots,k.$$Then we can write the vectors $\{x_1-x_i,...,x_{i-1}-x_i,x_{i+1}-x_i,...,x_{k+1}-x_i\}$ in terms of $\{v_j\}$ as $$ {x_1-x_i=-v_{i-1}\\ x_2-x_i=(x_2-x_1)-(x_i-x_1)=v_1-v_{i-1}\\ \vdots\\ x_{i-1}-x_i=v_{i-2}-v_{i-1}\\ x_{i+1}-x_i=v_i-v_{i-1}\\ \vdots\\ x_{k+1}-x_i=v_k-v_{i-1} }. $$ The term $x_1-x_i$ enforces $i\ne 1$. Let us further assume $i\ne 2$ (we'll refer to this case later). Then the problem reads:

Assuming $\{v_1,v_2,\cdots v_k\}$ are linear independent, do the vectors $\{v_1-v_{i-1},v_2-v_{i-1},\cdots,v_{i-2}-v_{i-1},-v_{i-1},v_i-v_{i-1},\cdots v_k-v_{i-1}\}$ maintain that character?

To answer this question, lets us define two matrices $$ { A=\begin{bmatrix} v_1\\v_2\\\vdots\\v_k \end{bmatrix} \\ B=\begin{bmatrix} v_1-v_{i-1}\\v_2-v_{i-1}\\\vdots\\v_{i-2}-v_{i-1}\\-v_{i-1}\\v_i-v_{i-1}\\\vdots \\v_k-v_{i-1} \end{bmatrix} }. $$ A transformation matrix $M$, relates $A$ and $B$ through $$ B=MA $$ where $$ M=\begin{bmatrix} 1&0&0&0&0&0&\cdots&0&-1&0&\cdots&0&0&0&0&0&0\\ 0&1&0&0&0&0&\cdots&0&-1&0&\cdots&0&0&0&0&0&0\\ 0&0&1&0&0&0&\cdots&0&-1&0&\cdots&0&0&0&0&0&0\\ 0&0&0&1&0&0&\cdots&0&-1&0&\cdots&0&0&0&0&0&0\\ 0&0&0&0&1&0&\cdots&0&-1&0&\cdots&0&0&0&0&0&0\\ \vdots\\ 0&0&0&0&0&\cdots&0&1&-1&0&\cdots&0&0&0&0&0&0\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&0&0&0&0&0\\ 0&0&0&0&0&\cdots&0&0&-1&1&\cdots&0&0&0&0&0&0\\ \vdots\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&1&0&0&0&0\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&0&1&0&0&0\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&0&0&1&0&0\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&0&0&0&1&0\\ 0&0&0&0&0&\cdots&0&0&-1&0&\cdots&0&0&0&0&0&1 \end{bmatrix} $$ where the row containing only a $-1$, is the $(i-1)$th row and the column containing only $-1$s and no $0$s, is the $(i-1)$th column. Hence, $M$ is full-rank, since the first $i-2$ rows and last $k-i$ rows are linearly independent and the $(i-1)$th row is too linearly independent from the others, since all of its entries except the $(i-1)$th are zero. Therefore, the linear independence of $\{v_1,v_2,\cdots v_k\}$ carries over to $\{v_1-v_{i-1},v_2-v_{i-1},\cdots,v_{i-2}-v_{i-1},-v_{i-1},v_i-v_{i-1},\cdots v_k-v_{i-1}\}$ and the problem is solved for $i\ne 2$. The case $i=2$ also follows easily with a different transformation matrix $M$ $\blacksquare$