# Find largest eigenvalue of specific nonnegative matrix

I look for the largest eigenvalue of the following matrix (or at least a small upper bound). The only thing I know is that the eigenvalue is smaller than 1 and converges to $$\cos(\frac{\pi}{2n+1})$$ with growing n.

In general, it is very hard to compute the characteristic polynomial to calculate the eigenvalue and that's why I hope for an easier way.

Has anyone some ideas?

The dimension of the matrix is $$n \times n$$. $$A = \begin{bmatrix} \frac{1}{2-\frac{1}{n+1}}& \frac{1}{2} & 0 & 0 & \dots & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & \dots & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 &0 & \frac{1}{2} & 0 \end{bmatrix}$$

• Is the dimension of the matrix $n \times n$, and should $a_{n-1, n}$ be $1/2$ instead of zero? – Maxim Nov 14 '18 at 17:56
• Yes, you are right. Instead of the zero I wanted to include $\vdots$but you are right that $a_{n-1,n}$ is $\frac{1}{2}$. – Jannik Nov 14 '18 at 18:12
• This is equivalent to maximizing $(n + 1) x_1^2/(2 n + 1) + x_1 x_2 + \ldots + x_{n - 1} x_n$ over the sphere $\lVert x \rVert = 1$. But that doesn't seem to make things simpler. – Maxim Nov 14 '18 at 18:25
• $1-\frac{1}{2(n-1)(2n-1)}$ seems to be an upper bound on the largest eigenvalue (verified via testing for $1 \leq n \leq 10 000$ in MatLab). Now, only the proof is missing ... – Jannik Nov 14 '18 at 19:31

An asymptotic expansion for large $$n$$ can be obtained as follows. Expanding $$A - \lambda I$$ by the first row and expanding one of the resulting matrices by the first column gives $$\det(A - \lambda I) = \left( \frac {n + 1} {2 n + 1} - \lambda \right) \det \tilde A_{n - 1} - \frac 1 4 \det \tilde A_{n - 2},$$ where $$\tilde A_n$$ is a tridiagonal Toeplitz matrix with $$-\lambda$$ on the main diagonal and $$1/2$$ on the two adjacent diagonals. The determinant of $$\tilde A_n$$ is $$2^{-n} U_n(-\lambda)$$, where $$U_n$$ is the Chebyshev polynomial of the second kind. Since $$U_n(-\cos \theta) = (-1)^n \csc \theta \,\sin \,(n + 1) \theta$$, $$\det(A - \lambda I) = 0$$ reduces to $$\cot n \theta = \left( \frac {2 n + 2} {2 n + 1} - \cos \theta \right) \csc \theta.$$ Taking $$\theta = \alpha/n$$ and expanding both sides of the equation into series, we obtain $$\cot \alpha = 1/(2 \alpha) + O(1/n)$$, determining $$\alpha$$. Then $$\lambda_{\max} = \cos \theta \sim 1 -\frac {\alpha^2} {2 n^2},$$ where $$\alpha$$ is the smallest positive root of $$\cot \alpha = 1/(2 \alpha)$$. The next terms can be obtained in the same manner.
• Wow, thanks for your help. This seems to be correct but I have a question. Why do you compute $U_n(\cos(\Delta))$? Because the largest eigenvalue of A seems to be related to a cosine term or is there a different mathematical evidence? – Jannik Nov 15 '18 at 7:25
• The change of variables is $\lambda = \cos \theta$, because we want to use the identity $U_n(-\cos x) = (-1)^n \csc x \,\sin \,(n + 1) x$. Then it's just some algebraic manipulations to get the equation for $\theta$. $\lambda$ close to one corresponds to $\theta$ close to zero. – Maxim Nov 15 '18 at 15:58