Proving that $T$:$(x_1,...,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},...,\frac {x_n+x_1}{2})$ leads to nonintegral components

Question

Start with $n$ paiwise different integers $x_1,x_2,...,x_n,(n>2)$ and repeat the following step:

$T$:$(x_1,...,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},...,\frac {x_n+x_1}{2})$

Show that $T,T^2,...$ finally leads to nonintegral components.

---

I have solved this problem with the approach written below, but is there a more elegant elementary way to solve this problem using the fact that the sum of the components is invariant ?

Denote $y_k =(z(k)_1,....,z(k)_n) = T^k(x)$ where $x=(x_1,...,x_n)$.

Then $||y_{k+1}||^2=(\frac {z(k)_1+z(k)_2}{2})^2+(\frac {z(k)_2+z(k)_3}{2})^2+...+(\frac {z(k)_n+z(k)_1}{2})^2$

$=\frac {1} {2}(z(k)_1^2+....+z(k)_n^2)+\frac {1} {4}(2z(k)_1z(k)_2+2z(k)_2z(k)_3+...+2z(k)_nz(k)_1)$

$\le z(k)_1^2+...+z(k)_n^2$ ,Since $2xy\le x^2+y^2$

Thus $||y_{n+1}|| \le ||y_n||$.

The equality holds if and only if $z(k)_i=z(k)_{i+1}$ for $i=1,2..,n-1$ and $z(k)_n=z(k)_{1} \rightarrow z(k)_1=z(k)_2=....=z(k)_n$

If the components remain integers then the sum of squares are strictly decreasing until all components are equal.Suppose $T^k(x)$ consists of equal components and $T^{k-1}(x)$ consists of components such that not all of them are equal.

Then $$T^k(x)=(\frac {z(k-1)_1+z(k-1)_2} {2},...,\frac {z(k-1)_n+z(k-1)_1} {2})$$ with $$\frac {z(k-1)_1+z(k-1)_2} {2}=\frac {z(k-1)_2+z(k-1)_3} {2}=...=\frac {z(k-1)_n+z(k-1)_1}{2}$$

$\rightarrow z(k-1)_1=z(k-1)_3=z(k-1)_5... $ , $z(k-1)_2=z(k-1)_4=z(k-1)_6...$ and $z(k-1)_n=z(k-1)_2$.

If $n$ is odd it follows that $z(k-1)_1=z(k-1)_2=...=z(k-1)_n$ which is a contradiction.

If $n$ is even we have that $T^{k-1}(x)=(r,s,r,s,....,r,s)$

$$\frac {z(k-2)_1+z(k-2)_2} {2}=\frac {z(k-2)_3+z(k-2)_4} {2}=...=\frac {z(k-2)_{n-1}+z(k-2)_n} {2}=r $$ and $$ \frac {z(k-2)_2+z(k-2)_3} {2}=\frac {z(k-2)_4+z(k-2)_5} {2}=...=\frac {z(k-2)_{n}+z(k-2)_1} {2}=s $$

It follows that $$ \frac {z(k-2)_1+z(k-2)_2} {2}+\frac {z(k-2)_3+z(k-2)_4} {2}+...+\frac {z(k-2)_{n-1}+z(k-2)_n} {2}=\frac {n} {2} r $$

and $$ \frac {z(k-2)_2+z(k-2)_3} {2}+\frac {z(k-2)_4+z(k-2)_5} {2}+...+\frac {z(k-2)_{n}+z(k-2)_1} {2}= \frac {n} {2} s $$

$ \rightarrow r=s $.Thus we have arrived to a contradiction. It follows that $T,T^2,...$ finally leads to nonintegral values.

Answer 1

The determinant of $T$, when nonzero, has to be an integer for $T$ to maintain integrality of vectors (proof: a simplex with integer vertices and minimal volume has to map to a finite union of such). This rules out odd $n$. Computation of the determinant can be accomplished using the formula for eigenvalues of circulant matrices, here $(1+\omega)/2$ with $\omega$ any $n$th root of unity.

For even $n$ the determinant of $T$ is $0$, but the map is not nilpotent, so there is potentially an integer sublattice to which the same argument applies (since there is only one $0$ eigenvalue). Indeed, $T$ preserves the $(n-1)$ dimensional subspace with $\sum (-1)^i x_i = 0$, and does not map any element of that subspace to $0$. This means that it is the invariant subspace of $T$ complementary to the $0$ eigenspace,and the determinant of $T$ restricted to that subspace is the product of the nonzero eigenvalues. The determinant again is not an integer.

Answer 2

First find the eigenvalues of $T$:

$Ty = \lambda y$ is equivalent to ${y_i + y_{i+1} \over 2} = \lambda y_i$ for all $i$, where $y_{n+1}$ is taken to mean $y_1$. This translates into $y_{i+1} = (2\lambda - 1)y_i$. Iterating $n$ times we have $(2\lambda - 1)^n y_i = y_i$. Since some $y_i$ is nonzero one has $(2\lambda - 1)^n = 1$ or equivalently $\lambda = {1 + \omega \over 2}$ where $\omega$ is any $n$th root of unity. Conversely, one can see that each such $\lambda$ is an eigenvector by using $y_1 = 1$ and $y_i = (2\lambda - 1)^{i-1} = w^{i-1}$ for each $i > 1$.

So the eigenvalues are of the form $\lambda_k = {\displaystyle{1 + e^{2\pi i (k-1) \over n} \over 2}}$ for $1 \leq k \leq n$ with some corresponding eigenvectors $v_k$. Any initial vector $x = (x_1,...,x_n)$ can be written in the form $c_1v_1 + .... + c_nv_n$ for some $c_i$. Since the $x_i$ are distinct and $v_1 = (1,...,1)$, we have that $c_i \neq 0$ for at least one $i > 0$. In the case where $n$ is even, $v_{{n \over 2} + 1} = (1,-1,1,-1,...,1,-1)$, so since the $x_i$ are distinct, if $n$ is even then $c_i \neq 0$ for some $i >1$, $i \neq {n \over 2} + 1$.

Next, note that $$T^k x = c_1 v_1 + \lambda_2^k c_2 v_2 + ... + \lambda_n^k c_n v_n$$ Since $|\lambda_i| < 1$ for all $i > 1$, as $k$ goes to infinity $T^k x$ converges to $c_1v_1$. By the last paragraph, there is always a $c_i \neq 0$ for which $i > 1$ and $\lambda_i^k \neq 0$, so since the $v_i$ are linearly independent for $i > 1$ it is not possible that for some $k$ one already has $T^k x = c_1 v_1$.

Next note that there is some $\epsilon > 0$ such that if $0 < ||w - c_1v_1|| < \epsilon$ then $w$ has noninteger components. Since $T^kx$ converges to $c_1v_1$ as $k$ goes to infinity and each $T^k x$ is not equal to $c_1v_1$, we have that for $k$ large enough $T^k x$ has noninteger components as needed.