IMO 1963 Problem 4

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 9m04s

Problem

Find all solutions $x_1,x_2,x_3,x_4,x_5$ of the system $$ \begin{eqnarray*} x_5+x_2&=&yx_1\ x_1+x_3&=&yx_2\ x_2+x_4&=&yx_3\ x_3+x_5&=&yx_4\ x_4+x_1&=&yx_5,\end{eqnarray*} $$ where $y$ is a parameter.

Exploration

The system is a cyclic linear homogeneous system with five variables and a real parameter $y$. The structure suggests a circulant matrix, so complex Fourier modes $x_j=\omega^{kj}$ diagonalize it. This reduces the problem to locating when an eigenvalue vanishes.

Substituting $x_j=\omega^{kj}$ gives the condition $y=\omega^k+\omega^{-k}=2\cos\frac{2\pi k}{5}$. For $k=0$ this gives $y=2$, while $k=1,4$ give $y=2\cos\frac{2\pi}{5}$ and $k=2,3$ give $y=2\cos\frac{4\pi}{5}$.

A potential pitfall appears when translating complex eigenvectors into real solution spaces. Since the matrix is real, complex conjugate eigenvectors correspond to real invariant subspaces of dimension two, not one. This must be checked explicitly by constructing real bases and confirming no further degeneracy occurs.

For $y=2$, testing small cases shows only constant solutions persist, suggesting a one-dimensional space. For the other two parameter values, combining conjugate Fourier modes produces real cosine and sine solutions, indicating two-dimensional real solution spaces. No additional parameter values appear because all eigenvalues are exhausted by the five Fourier modes.

No contradictions arise when checking $n=1,2,3,4,5$ cyclic behavior under these forms, confirming consistency of the Fourier decomposition.

Problem Understanding

The task is to determine all real solutions $(x_1,x_2,x_3,x_4,x_5)$ depending on a real parameter $y$, and to classify completely the solution space for each admissible $y$.

This is equivalent to finding the kernel of a real symmetric circulant $5\times 5$ matrix depending on $y$, and describing its dimension and basis for each parameter where the kernel is nontrivial.

Key Observations

The system can be written as $A(y)x=0$, where $A(y)$ is a real symmetric circulant matrix with first row $(-y,1,0,0,1)$.

Such matrices are diagonalized over $\mathbb{C}$ by Fourier vectors $v^{(k)}=(1,\omega^k,\omega^{2k},\omega^{3k},\omega^{4k})$, with eigenvalues

$$\lambda_k=-y+2\cos\frac{2\pi k}{5}.$$

Nontrivial solutions exist exactly when $\lambda_k=0$ for some $k$. The values $k$ and $5-k$ produce the same real eigenvalue, so complex eigenvectors occur in conjugate pairs. Each such pair generates a two-dimensional real eigenspace.

Solution

The eigenvalue condition $\lambda_k=0$ gives

$$y=2\cos\frac{2\pi k}{5}, \quad k=0,1,2,3,4.$$

These reduce to three distinct real values

$$y\in\left{2,\ \frac{\sqrt5-1}{2},\ -\frac{\sqrt5+1}{2}\right}.$$

Each case is treated separately.

For $y=2$, the eigenvalue corresponds to $k=0$. The associated Fourier mode is constant, so every solution satisfies $x_1=x_2=x_3=x_4=x_5$. This yields a one-dimensional solution space consisting of all constant vectors.

For $y=\frac{\sqrt5-1}{2}$, the zero eigenvalues correspond to $k=1$ and $k=4$. A real basis is obtained by taking real and imaginary parts of the Fourier vector $v^{(1)}$. Writing $\omega=e^{2\pi i/5}$, every real solution has the form

$$x_j=a\cos\frac{2\pi j}{5}+b\sin\frac{2\pi j}{5}, \quad j=1,2,3,4,5,$$

for real parameters $a,b$. This space is two-dimensional over $\mathbb{R}$.

For $y=-\frac{\sqrt5+1}{2}$, the zero eigenvalues correspond to $k=2$ and $k=3$. A real basis is obtained similarly from $v^{(2)}$, giving

$$x_j=a\cos\frac{4\pi j}{5}+b\sin\frac{4\pi j}{5}, \quad j=1,2,3,4,5,$$

with real parameters $a,b$. This solution space is also two-dimensional over $\mathbb{R}$.

If $y$ is not among these three values, all eigenvalues $\lambda_k$ are nonzero, so the only solution is $x_1=x_2=x_3=x_4=x_5=0$.

Collecting all cases gives a complete classification of solutions.

Verification of Key Steps

Substituting $x_j=a\cos\frac{2\pi j}{5}+b\sin\frac{2\pi j}{5}$ into the system reduces each equation to the eigenvalue identity for $k=1$ and $k=4$, ensuring consistency because both modes satisfy the same scalar equation $y=2\cos\frac{2\pi}{5}$.

The cosine and sine sequences are linearly independent over $\mathbb{R}$ since no nontrivial real linear combination vanishes at all five indices $j=1,2,3,4,5$, which follows from the injectivity of the discrete Fourier basis on $\mathbb{R}^5$.

For $y=2$, substituting $x_j=c$ gives $c+c=2c=y c$ in every equation, so every constant vector satisfies the system, and any non-constant vector violates at least one equation by symmetry reduction.

For values of $y$ not in the spectral set, invertibility follows because all Fourier eigenvalues are nonzero, so the kernel is trivial.

Alternative Approaches

One alternative approach eliminates variables to obtain a fifth-order recurrence $x_{j+2}-(y^2-2)x_j+x_{j-2}=0$ with cyclic boundary conditions, then solves the associated characteristic polynomial to recover the same cosine spectrum.

Another approach uses diagonalization of circulant matrices via discrete Fourier transform over $\mathbb{R}$ directly, splitting the space into invariant real subspaces corresponding to conjugate frequency pairs without invoking complex eigenvectors.