# When are $\beta_1, \beta_2, \ldots, \beta_n$ linear independent?

Given $n$ linear independent vectors, $\alpha_1, \alpha_2, \ldots, \alpha_n$.

Now, let

$$\beta_1 = \alpha_1 + \alpha_2 + \cdots + \alpha_m$$ $$\beta_2 = \alpha_2 + \alpha_3 + \cdots + \alpha_{m+1}$$ $$\ldots$$ $$\beta_{n-m} = \alpha_{n-m} + \alpha_{n-m+1} + \cdots + \alpha_n$$ $$\beta_{n-m+1} = \alpha_{n-m+1} + \alpha_{n-m+2} + \cdots + \alpha_{n+1}$$ $$\ldots$$ $$\beta_{n-1} = \alpha_{n-1} + \alpha_{n} + \cdots + \alpha_{m-2}$$ $$\beta_{n} = \alpha_{n} + \alpha_{1} + \cdots + \alpha_{m-1}$$

where $1 \lt m \lt n$.

For example, if $n=3$ and $m=2$, then

$$\beta_1 = \alpha_1 + \alpha_2$$ $$\beta_2 = \alpha_2 + \alpha_3$$ $$\beta_3 = \alpha_3 + \alpha_1$$

The question is, to which condition $n$ and $m$ must meet when $\beta_1, \beta_2, \ldots, \beta_n$ are linear independent?

A guess is that $n$ and $m$ must be relatively prime, but I can neither prove or disprove it.

• There is no $\alpha_{n+1}$. Where it says so, you seem to mean $\alpha_1$. – Marc van Leeuwen Oct 27 '16 at 9:36

Isn't the implied matrix a circulant matrix?

Then, because of this determinant formula, your problem (for the case of linearly dependent vectors) appears to ask, for given $m < n$

When is it the case that there is a $j \mid n$ such that $\omega_{j}$ is a root of $f_{m} = x^{m-1} + \dots + x + 1$, or equivalently $\phi_{j}$ divides $f_{m}$?

Here $\omega_{j}$ is a primitive $j$-th root of unity, and $\phi_{j}$ is the $j$-th cyclotomic polynomial.

If $\phi_{j}$ divides $f_{m}$, then $j > 1$ (as $f_{m}(\omega_{1}) = f_{m}(1) = m \ne 0$), and $\phi_{j}$ divides $x^{m} - 1 = (x-1) f_{m}$, so $j \mid m$. Conversely, if $j > 1$ and $j \mid m$, then $\phi_{j}$ divides $x^{j} - 1$ which divides $x^{m} - 1 = (x - 1) f_{m}$, so that $\phi_{j}$ divides $f_{m}$, as $j > 1$.

Therefore the condition for linear dependence appears indeed to be that $\gcd(n, m) \ne 1$.

Addendum. The key point here is really $$\gcd(x^{n} - 1, x^{k} - 1) = x^{\gcd(n, k)} - 1.$$

You are right. Write $V$ for your vector space. If $n,m$ are not coprime, let us say that $k = \gcd(m,n) > 1$. Then let $\omega$ be a primitive $k$-th root of unity, and note that the mapping $V \to \mathbb C$ $$\sum_{i}v_i\alpha_i \mapsto \sum_i \omega^iv_i$$ takes all your $\beta_i$ to zero, but does not do this to (say) $\alpha_1$. If you are working over $\mathbb R$ instead, you can take the real (or imaginary) part of these equations, to get an expression in terms of sines or cosines.

If however $n,m$ are coprime, then define (interpret all indices as "mod $n$") $$\gamma_i = \beta_i - \beta_{i+1} = \alpha_i - \alpha_{i+m}.$$ Since the sequence $\alpha_i,\alpha_{i+m},\alpha_{i+2m},\cdots$ covers all the $\alpha$, we might as well reorder the indices of the $\alpha_i$ such that $\gamma_i = \alpha_i - \alpha_{i+1}$. Then it is clear that $\langle \gamma_1,\ldots,\gamma_n\rangle$ spans all vectors which (in $\alpha$-coordinates) have coordinates which sum up to zero. Hence these are all in the span of $\langle \beta_1,\ldots,\beta_n\rangle$. Finally, $\sum_i \beta_i$ is also in this span, and together they clearly span the entire space. Since the $n$ vectors span the entire $n$-dimensional space, they are a basis.