1
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Is the dimension of the matrix $n \times n$, and should $a_{n-1, n}$ be $1/2$ instead of zero? $\endgroup$ – Maxim Nov 14 '18 at 17:56
  • $\begingroup$ 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}$. $\endgroup$ – Jannik Nov 14 '18 at 18:12
  • $\begingroup$ 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. $\endgroup$ – Maxim Nov 14 '18 at 18:25
  • $\begingroup$ $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 ... $\endgroup$ – Jannik Nov 14 '18 at 19:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jannik Nov 15 '18 at 7:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Maxim Nov 15 '18 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.