666 Followers Question

For any $n \in \mathbb{N}$ , consider the $(n+1)\times(n+1)$ matrix $A[n]$ , where $A[n]_{rs} \; = \; \left\{ \begin{array}{lll} \sqrt{2} & \qquad & r=1,s=2 \mbox{ or } r=2, s=1, \\ 1 & \qquad & r=j,s=j+1 \mbox{ or } r=j+1,s=j \quad \mbox{ for } 2 \le j \le n, \\ 0 & \qquad & \mbox{otherwise} \end{array} \right.$ so that $\mathbf{x}^T A[n] \mathbf{x} \; = \; 2\left(\sqrt{2}x_1x_2 + \sum_{r=2}^n x_r x_{r+1}\right)$ for any $\mathbf{x} \in \mathbb{R}^{n+1}$ .

For $\alpha \in \mathbb{R}$ define the vector $\mathbf{x}(\alpha) \in \mathbb{R}^{n+1}$ by $\mathbf{x}(\alpha)_r \; = \; \left\{ \begin{array}{lll} \tfrac{1}{\sqrt{2}} & \qquad & r = 1 \\ \cos(r-1)\alpha & \qquad & 2 \le r \le n+1 \end{array} \right.$ For then $\big[A[n]\mathbf{x}(\alpha)\big]_r \; = \; \left\{\begin{array}{lll} \sqrt{2}\mathbf{x}(\alpha)_2 \; = \; 2\cos\alpha \mathbf{x}(\alpha)_1 & \qquad & r = 1 \\ \sqrt{2}\mathbf{x}(\alpha)_1 + \mathbf{x}(\alpha)_3 \; = \; 2\cos\alpha \mathbf{x}(\alpha)_2 & \qquad & r = 2 \\ \mathbf{x}(\alpha)_{r-1} + \mathbf{x}(\alpha)_{r+1} \; = \; 2\cos\alpha \mathbf{x}(\alpha)_r & \qquad & 3 \le r \le n \\ \mathbf{x}(\alpha)_n \; = \; 2\cos\alpha \mathbf{x}(\alpha)_{n+1} - \cos(n+1)\alpha & \qquad & r = n+1 \end{array} \right.$ so that $A[n]\mathbf{x}(\alpha) \,=\, 2\cos\alpha \mathbf{x}(\alpha)$ provided that $\cos(n+1)\alpha = 0$ . Thus the matrix $A[n]$ has $n+1$ distinct real eigenvalues $2\cos\tfrac{(2k+1)\pi}{2(n+1)}$ , with corresponding eigenvector $\mathbf{x}\big(\tfrac{(2k+1)\pi}{2(n+1)}\big)$ , for $k \,=\, 0,1,2,\ldots,n$ .

The maximum value of $\mathbf{x}^T A[n] \mathbf{x}$ over all $\mathbf{x} \in \mathbb{R}^{n+1}$ for which $\Vert\mathbf{x}\Vert^2 = 1$ is the largest eigenvalue of $A[n]$ , namely $2\cos \tfrac{\pi}{2(n+1)}$ . Thus the largest value of $F(x_1,x_2,\ldots,x_n) \;=\; \sqrt{2}x_1x_2 + \sum_{r=2}^{n-1} x_rx_{r+1} + x_n\sqrt{1 - \sum_{r=1}^nx_r^2}$ for all $x_1,x_2,\ldots,x_n$ such that $x_1^2 + x_2^2 + \cdots + x_n^2 \le 1$ is $\cos \tfrac{\pi}{2(n+1)}$ . We are just introducing an extra variable $x_{n+1}$ so that $x_{n+1}^2 = 1 - x_1^2 - x_2^2 - \cdots - x_n^2$ . The fact that $F(x_1,x_2,\ldots,x_n)$ always requires $x_{n+1}$ to be positive is unimportant, since $\mathbf{x}^TA[n]\mathbf{x} = (-\mathbf{x})^TA[n](-\mathbf{x})$ , and one of $\mathbf{x}$ and $-\mathbf{x}$ must have positive last coefficient. Thus we can always achieve the maximum value of $\mathbf{x}^TA[n]\mathbf{x}$ with an $\mathbf{x}$ with positive last coefficient.

For the first part of the question we have $n=3$ , so the largest eigenvalue is $\cos\tfrac{\pi}{8}$ . The answer to the question is $\boxed{8}$ .

Here is a brief solution of the "bonus question" for those who know about Chebyshev polynomials.

If we introduce an auxiliary variable $x_{n+1}=\sqrt{1-\sum_{k=1}^{n}x_k^2}$ , then our problem amounts to finding the maximum of the quadratic form $q(x_1,...,x_{n+1})=\sqrt{2}x_1x_2+\sum_{k=2}^{n}x_kx_{k+1}$ subject to the constraint $\sum_{k=1}^{n+1}x_k^2=1$ .

Let $A$ be the symmetric matrix of $q$ ; the largest eigenvalue of $A$ is the maximal value of $q$ . It turns out that the characteristic polynomial of $A$ is a constant multiple of the Chebyshev polynomial of the first kind $T_{n+1}(x)$ . The zeros of $T_{n+1}(x)$ , of the form $\cos\left(\frac{(2k-1)\pi}{2(n+1)}\right)$ for $k=1,...,n+1$ , are the eigenvalues of $A$ . The largest eigenvalue, $\cos\left(\frac{\pi}{2(n+1)}\right)$ , is the maximal value of $q$ we seek.