2
$\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$
4
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 19:31

1 Answer 1

2
$\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$
2
  • $\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, 2018 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, 2018 at 15:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .