# Linear independence problems

If $v_{1},v_{2},...v_{n}$ are linearly independent then are the following too? $v_{1}+v_{2},v_{2}+v_{3},...v_{n-1}+v_{n},v_{n}+v_{1}$

I tried summing them to give 0 but had no success.

-

They can't always be linearly independent, since they're clearly not for $n=2$.

For even $n$, you can sum them with alternating signs to represent the zero vector.

To represent the zero vector for odd $n$, you'd also have to sum them with alternating signs, since each $v_i$ occurs only in two adjacent vectors and the two contributions must cancel; but for odd $n$ the signs clash when you wrap around, so in this case the vectors are linearly independent.

-
"The signs clash" only says that some particular linear combination does not vanish, not that no nontrivial combination vanishes, i.e., that the vectors are linearly independent. – Travis Feb 22 at 13:57
@Travis: No. I argue that a nontrivial combination that vanishes would have to have alternating signs (and constant modulus) in order to make the contributions for each individual $v_i$ cancel. Since there can't be alternating signs with wraparound in the odd case, it follows that no nontrivial combination vanishes. – joriki Feb 22 at 14:02
Oh, I see, that's what you mean by "you'd have to sum them...", the wording wasn't clear to me at first. Anyway, +1 for the efficient answer. – Travis Feb 22 at 14:04
@Travis: Thanks. I slightly reformulated it; I hope that makes it a bit clearer? – joriki Feb 22 at 14:05
Yes, I find it totally readable this way---cheers! – Travis Feb 22 at 14:11

The dependence relation $\sum_{i=1}^{n-1} \alpha_i (v_i + v_{i+1}) + \alpha_n (v_n + v_1) = 0$, combined with the linear independence of the $v_i$, yields the linear system $\alpha_i + \alpha_{i+1} = 0$ ($i = 1,\ldots,n-1$) and $\alpha_1 + \alpha_n = 0$. You can check that the corresponding matrix $$\begin{pmatrix} 1& 1&&&& \\ & 1&1&&& \\ & &&\ddots&& \\ & &&&1&1 \\ 1& &&&&1 \\ \end{pmatrix}$$ has full rank iff $n$ is odd. (For instance you can use $n-1$ elementary row operations to modify the bottom row to get your matrix to row-echelon form.)

-
Also note that you can take the determinant of your matrix (call it $A$) by subminors on the first column; this yields $\det(A) = \det(B) + (-1)^{n+1} \det(B^T)$, where $$B = \begin{bmatrix} 1 & 1 & & & \\ & 1 & & & \\ & & \ddots & & \\ & & & 1 & 1 \\ & & & & 1 \end{bmatrix}$$ Since $\det(B) = \det(B^T) \neq 0$, we have $\det(A) = 0$ (and therefore the columns are linearly dependent) iff $n$ is even. – Michael Seifert Feb 22 at 18:12

$$a_1(v_1+v_2) + a_2(v_2+v_3) + \cdots + a_{n-1}(v_{n-1}+v_n) + a_n(v_n + v_1) \\ = a_1v_1 + a_1v_2 + a_2v_2 + a_2v_3 + a_3v_3 + \cdots + a_{n-1}v_n + a_nv_n + a_nv_1 \\ = (a_1+a_n)v_1 + (a_1+a_2)v_2 + \cdots (a_{n-2} +a_{n-1})v_{n-1}+(a_{n-1}+a_n)v_n \\ = b_1v_1 + b_2v_2 + \cdots + b_{n-1}v_{n-1}+b_nv_n$$

Now make conclusions (casewise).

-

This is not in general linearly independent. If $n$ is odd, these are linearly independent, but if $n$ is even, they are not in general. For example: $(1,0,0,0),(0,1,0,0), (0,0,1,0)$ and $(0,0,0,1)$, we have $(1,1,0,0)+(0,0,1,1)-(0,1,1,0)-(1,0,0,1) = (0,0,0,0)$. If $n$ is odd, then if $v_1, v_2, \ldots , v_n$ is linearly independent and $c_1(v_1+v_2) + \ldots + c_n(v_n + v_1) = 0$, then $$(c_1+c_n)v_1 + (c_1+c_2)v_2 + \ldots + (c_{n-1} + c_n)v_n = 0.$$ It is easy to see that $c_i = -c_{i+1}$ and $c_i = c_{i+2}$ for all $i$ (for all $i = 1,2,\ldots, n-2$). Now, if $n=2k+1$, then we have $c_1 = c_3 = \ldots = c_{2k+1}$ and clearly $c_{2k+1} = c_2$, thus $c_1 = c_2= c_3 = \ldots = c_{2k+1}$ and since $c_i = -c_{i+1}$, this shows that $c_i= 0$ for each $i \in \{1,2,\ldots, n\}$.

-

Suppose there are $\lambda_1,\dotsc,\lambda_n\in \mathbb{R}$ with $$\lambda_1(v_1+v_2)+\dotsc+\lambda_n(v_n+v_1)=0$$

If $n$ is even we fix $\lambda\in K\setminus\{0\}$ and choose $\lambda_i=(-1)^{i}\lambda$ so for $n$ even the vectors aren't linear independent.

For $n$ odd we get from the above equation

$$(\lambda_1+\lambda_n)v_1+\dotsc +(\lambda_{n-1}+\lambda_n)v_n=0$$ and by linear independence of $v_1,\dotsc,v_n$ we get $$\lambda_1=-\lambda_n, \lambda_2=-\lambda_1,\dotsc, \lambda_n=-\lambda_{n-1}$$ So we get $-\lambda_1=\lambda_n=(-1)^{n-1}\lambda_1=\lambda_1$ and so $\lambda_1=0$. It follows $\lambda_i=0$ for all $i=1,\dotsc,n$ and so the vectors are linear independent in this case.

-