averaging numbers on a circle

159 Views Asked by At

Suppose you have $n$ numbers $a_1, \dots, a_n$ arranged on a circle. You replace each number with the average of its neighbors, i.e, you replace $a_1$ with $\frac{a_n+a_2}{2}$, and $a_2$ with $\frac{a_1+a_3}{2}$, and so on. If you do this sufficiently many times will the numbers be roughly equal?

Giving a negative answer for even $n$ is not hard, but I'm interested in a careful analysis of the problem. I can prove that the matrix of this operation, say $A$, is diagonalizable and has eigenvalues $\lambda_k=\cos(2\pi k/n)$ for $k=0, 1, \dots, n-1$. So in the case that $n$ is odd all eigenvalues satisfy $|\lambda_k|<1$ except for $\lambda_0=1$. And when $n$ is even, $k=n/2$ gives the eigenvalue $-1$.

What would be a good strategy to finish the solution from here? (Feel free to suggest a different method if you prefer...)

Note: This appears as a "baby problem" in Kirillov's notes (page 7) on Lie groups but the solution he gives is not quite complete.

1

There are 1 best solutions below

2
On BEST ANSWER

The matrix of the operation, $A$, is symmetric, and thus has orthogonal eigenvectors. Define $q_i$ as the $i$th eigenvector. Let $u_0$ be the vectorized version of the initial set of numbers: $u_0 := [a_1 \; a_2 \; \dots \; a_n]$ . We can express $u_0$ in terms of $q_i$ as \begin{align*} u_0 = \sum_{i=1}^n \alpha_i q_i. \end{align*} for some $\alpha_i$, $i=1,\dots,n$. Then application of the operation $A$ $k$ times would give the vector \begin{align*} u_k=A^k u_0 = A^k \sum_{i=1}^n \alpha_i q_i = \sum_{i=1}^n \alpha_i A^k q_i = \sum_{i=1}^n \alpha_i \lambda_i^k q_i, \end{align*} where $\lambda_i$ is the $i$th eigenvalue of $A$.

Next, note that $\mathbf{1}$ (all ones vector) is an eigenvector of $A$ with eigenvalue 1 since $A\mathbf{1} = \mathbf{1}$.

For $n$ odd, since all $\lambda_i$'s except one (say $\lambda_0$) satisfy $|\lambda_i|<1$ (and therefore $\lambda_i^k \to 0$), we have that \begin{align*} u_k \to \lambda_0^k \alpha_0q_0 = \alpha_0 \mathbf{1}, \end{align*} which shows the desired result. When $n$ is even, we have \begin{align*} u_k \to \alpha_0 \mathbf{1} + (-1)^k \alpha_n q_n, \end{align*} where $q_n$ is the eigenvector corresponding to the eigenvalue -1. Hence for $n$ even the second term causes oscillation.