# Alternative computation of eigenvalues of this tridiagonal matrix

Consider the tridiagonal symmetric pd matrix

$$M=\begin{bmatrix} 2 & -1 &\dots \\ -1 & 2 &-1&\dots \\ \vdots & \ddots & \ddots & \ddots \\ 0 & \dots & -1 & 2 & -1 \\ 0 &\dots &\dots & -1 & 1\end{bmatrix}$$

The question is how to find eigenvalues and eigenvectors of $M$. I already know a way, which consists in short as introducing the sequence on the components $\phi_i$ of an eigenvector $\phi$ (the sequence is $-\phi_{k-1}+2\phi_k-\phi_{k+1}=\lambda \phi_k$). Then it is possible to find the general term and $\lambda$ using the polynomial associated with the sequence. After some manipulation, the final result is: $$\lambda_k=2\Big(1-\cos\Big(\dfrac{(2k-1)\pi}{2n+1}\Big)\Big)$$ and the eigenvectors are given by $$\phi_k^{(i)}=\sin\Big(\dfrac{i(2k-1)\pi}{2n+1}\Big)$$ where $i$ is the component index and $k$ the index of the eigenvector. I was just wondering if someone knew another way of finding the eigendecomposition.

• There's always row reduction ... – Neal Sep 3 '16 at 6:52
• Just to be safe: Is the bottom-right element supposed to be 1 or is it meant to be 2 like the other diagonal elements? – ekkilop Sep 3 '16 at 12:59
• @ekkilop There's no typo, it's a 1. – anderstood Sep 3 '16 at 13:11
• Should $p$ be replaced by $k$ in $\lambda_k=\dots$? – Ignat Domanov Sep 3 '16 at 14:34
• also $M_{23}=-1$? – Ignat Domanov Sep 3 '16 at 15:19

For simplicity, let $M_n$ be the $n$-dimensional version of $M$ and let $D_n(z)$ denote the characteristic polynomial $\det{(M_n - z I)}$ of $M_n$. If we for convenience define $D_0 = 1$ and $D_1 = 1 - z$, it shouldn't be too difficult to convince ourselves that the sequence of characteristic polynomials satisfies the recurrence \begin{align} D_0 &= 1 \\ D_1 &= 1-z \\ D_{n+2} &= (2-z)D_{n+1} - D_n, \quad n \geq 2. \end{align} The solution to the recurrence takes the form $$D_n(z) = c_+ r_+^n + c_- r_-^n,$$ where $r_{\pm} = [(2-z) \pm \sqrt{(z-2)^2 - 4}]/2$ are the roots of the polynomial $x^2 - (2-z)x + 1$. Using the prescribed values of $D_0$ and $D_1$ we soon find that $$c_+ = \frac{1 - z - r_-}{r_+ - r_-}, \\ c_- = \frac{1 - z - r_+}{r_+ - r_-},$$ such that $$D_n(z) = \frac{1 - z - r_-}{r_+ - r_-} r_+^n - \frac{1 - z - r_+}{r_+ - r_-} r_-^n.$$ Now make the substitution $z = 2(1- \cos{(\phi)})$ (Note: we should really first check that the eigenvalues are real and confined to $0 < \lambda < 4$ to do this, but that shouldn't be too hard). After a little trigonometry this comes out as $$D_n(\phi) = 2 \frac{\sin{(\phi/2)}}{\sin{(\phi)}} \cos{\left( \left(n + \frac{1}{2} \right)\phi \right)}.$$ Solving $D_n(\phi) = 0$ gives the desired $$\phi = \frac{(2k-1)\pi}{2n+1}, \quad k = 1, \dots, n,$$ or $$\lambda_k = z = 2 \left( 1 - \cos{\left( \frac{(2k-1)\pi}{2n+1} \right)} \right).$$ From here, I don't think there is a simpler way of finding the eigenvectors than the one you used, except that now we know $\lambda$ in advance.