One more time

Recall the $(n+1)\times(n+1)$ matrix $A[n]$ which I defined in my solution of your 666 Followers Problem , for which $\mathbf{x}^T A[n] \mathbf{x} \; = \; 2\left(\sqrt{2}x_1x_2 + \sum_{r=2}^nx_r x_{r+1}\right) \quad, \qquad \mathbf{x} \in \mathbb{R}^{n+1} \;.$ The eigenvalues of this matrix $A[n]$ were shown to be $2\cos \tfrac{(2k+1)\pi}{2(n+1)}$ for $0 \le k \le n$ .

For this problem, let us change variables by rotating the coordinates a little. If we define $y_1 \; = \; \tfrac{1}{\sqrt{2}}(x_1 - x_2)\;, \quad y_2 \; = \; \tfrac{1}{\sqrt{2}}(x_1 + x_2) \;, \quad y_r \; = \; x_r \quad (3 \le j \le 2016) \;,$ then we need to consider the quadratic form $Q \; = \; \sqrt{2}y_2y_3 + y_3y_4 + \cdots y_{2015}y_{2016} \; = \; \tfrac12\mathbf{\eta}^TA[2014]\mathbf{\eta} \;,$ where $\mathbf{\eta} \; = \; \left(\begin{array}{c} y_2 \\ y_3 \\ \vdots \\ y_{2016}\end{array} \right) \in \mathbb{R}^{2015}$ We can write $Q$ as $Q \; = \; \tfrac12 \mathbf{y}^T C \mathbf{y}$ where $C$ is the $2016 \times 2016$ matrix $C \; = \; \left( \begin{array}{cccc} 0 & 0 & \cdots & 0 \\ 0 & & & \\ \vdots & & A[2014] & \\ 0 & \end{array} \right)$ In other words, $C$ is the matrix $A[2014]$ with an extra column and row of zeros tacked on.

We are asked to maximize $\tfrac12\mathbf{y}^TC\mathbf{y}$ subject to the condition that $\Vert\mathbf{y}\Vert^2 = 1$ . The answer is half the largest eigenvalue of $C$ . The eigenvalues of $C$ are the eigenvalues of $A[2014]$ with $0$ added for good luck. Thus the maximum eigenvalue is $2\cos \tfrac{\pi}{4030}$ , and so $M = \cos\tfrac{\pi}{4030}$ , making the answer $\boxed{4030}$ .

Dr. Hennings has submitted a fine solution, based his solution to an earlier problem that turned out to be equivalent.

For the sake of variety, let me outline a solution in terms of Chebyshev polynomials:

Let $A_n$ be the symmetric matric of our quadratic form in $n$ variables, and let $p_n(x)$ be the characteristic polynomial of $A_n$ . Now let $q_n(x)$ be the normalized Chebyshev polynomial of the first kind, meaning that we divide by the leading coefficient to make the polynomial monic. We claim that $p_n(x)=xq_{n-1}(x)$ for $n\geq 2$ . Indeed, $p_2(x)=x^2=xq_1(x)$ and $p_3(x)=x^3-\frac{1}{2}x=xq_2(x)$ . Furthermore, $p$ and $q$ satisfy the same recursive equation, $p_n(x)=xp_{n-1}(x)-\frac{1}{4}p_{n-2}(x)$ and likewise for $q$ . Thus the maximum we seek is the largest eigenvalue of $A_n$ , which is the largest zero of $q_{n-1}$ . But that largest zero of the $(n-1)$ th Chebyshev polynomial of the first kind is $\cos\left(\frac{\pi}{2(n-1)}\right)$