Diagonalize tri-diagonal symmetric matrix How to diagonalize the following matrix?
\begin{pmatrix}
2  & -1 & 0 & 0 & 0 & \cdots \\
-1 & 2  & -1 & 0 & 0 & \cdots \\
0 & -1 & 2  & -1 & 0 & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
\cdots & 0 & 0 & -1 & 2  & -1 \\
\cdots & 0 & 0 & 0 & -1 & 2  \\
\end{pmatrix}
It seems like we need to first compute eigenvalues and eigenvectors for this matrix, like the following:
\begin{vmatrix}
2 - \lambda & -1 & 0 & 0 & 0 & \cdots \\
-1 & 2 - \lambda & -1 & 0 & 0 & \cdots \\
0 & -1 & 2 - \lambda & -1 & 0 & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
\cdots & 0 & 0 & -1 & 2 - \lambda & -1 \\
\cdots & 0 & 0 & 0 & -1 & 2 - \lambda \\
\end{vmatrix}
But I just don't know what to do next.
 A: Let $\mathbf{x}$ be the eigenvector of $A$ with eigenvalue $\lambda$.
$$
A \mathbf{x} = \lambda \mathbf{x}
$$
Note that $\mathbf{x}$ is a solution to the following difference equation:
$$
-x_{k+1} + 2x_k - x_{k-1} = \lambda x_k,\quad k = 1, \dots, n\\
x_0 = 0,\quad x_{n+1} = 0.
$$
The characteristic equation for that linear reccurence is
$$
q^2 - (2 -\lambda) q + 1 = 0
$$
Observe that $q_1 q_2 = 1$ due to Viète theorem. The discriminant of the quadratics is $\mathscr D = (2 - \lambda)^2 - 4 = \lambda^2 - 4 \lambda$. Let's consider different cases for $\mathscr D = 0$, $\mathscr D > 0$ and $\mathscr D < 0$.
Case 1a. $\lambda = 0$. The $q_{1,2} = 1$, so the general solution is
$$
x_k = C_1 k + C_2.
$$
From the boundary conditions we conclude that $C_1 = C_2 = 0$. The solution is trivial, so $\lambda = 0$ is not an eigenvalue.
Case 1b. $\lambda = 4$. The $q_{1,2} = -1$ and the solution is
$$
x_k = (-1)^k (C_1 k + C_2).
$$
Again, $C_1 = C_2 = 0$ and $\lambda = 4$ is not an eigenvalue.
Case 2a. $\lambda < 0$ or $\lambda > 4$. $q_{1,2} \in \mathbb{R}, |q_1| > 1, |q_2| < 1$. Generic solution is
$$
x_k = C_1 q_1^k + C_2 q_2^k
$$
From left condition $C_1 = C_2$. Let $C_1 = 1$
$$
x_{n+1} = q_1^{n+1} + q_2^{n+1} = 0 \implies q_1^{n+1} = -q_2^{n+1}.
$$
If $n$ is even then $q_1 = -q_2$. But then $|q_1| = |q_2|$ and we know that $|q_1| > 1 > |q_2|$. Contradiction, no solution is possible.
If $n$ is odd then sides of $q_1^{n+1} = -q_2^{n+1}$ have different sign (left is positive, right is negative or zero). Also no solutions here.
Case 3. $0 < \lambda < 4$. The $q_{1,2} = \frac{2-\lambda \pm \sqrt{(2-\lambda)^2 - 4}}{2} = e^{\pm i\phi}, \phi \in \mathbb{R}$. General solution in this case will be
$$
x_k = C_1 \cos \phi k + C_2 \sin \phi k.
$$
From $x_0 = 0$ we obtain $C_1 = 0$. Let $C_2 = 1$.
$$
x_{n+1} = \sin \phi (n+1) = 0
$$
This equation has exactly $n$ different solutions which give different $x_k$ vectors.
$$
\phi_m = \frac{\pi m}{n+1},\quad m = 1, \dots, n
$$
So
$$
x^{(m)}_k = \sin \frac{\pi m k}{n+1}\\
\lambda^{(m)} = 4 \sin^2 \frac{\pi m}{2(n+1)}
$$
will be the $n$ different eigenpairs.
Edit So I actually didn't show how to diagonalize $A$. Here it is.
Since the matrix $A$ is symmertic, all its eigenvalues are orthogonal.
$$
(x^{m}_k, x^{\ell}_k) = \sum_{k=1}^{n} \sin \frac{\pi m k}{n+1} \sin \frac{\pi \ell k}{n+1} = \begin{cases} \frac{n+1}{2} & m = \ell\\0 & m \neq \ell\end{cases}
$$
It is the same functions that form discrete Fourier basis (discrete sine transform to be precise).
Let's make eigenvectors orthonormal (they are only orthogonal for now). Divide them by $\sqrt{\frac{n+1}{2}}$:
$$
\tilde{x}^{(m)}_k =\sqrt{\frac{2}{n+1}} \sin \frac{\pi m k}{n+1}, \qquad (\tilde{x}^{(m)}_k, \tilde{x}^{(\ell)}_k) = \delta_{m,\ell}
$$
Putting the $\tilde{x}^{(m)}_k$ vectors in matrix $U$
$$
U = \begin{pmatrix}
\tilde{x}^{(1)}_1 & \tilde{x}^{(2)}_1 & \dots & \tilde{x}^{(n)}_1 \\
\tilde{x}^{(1)}_2 & \tilde{x}^{(2)}_2 & \dots & \tilde{x}^{(n)}_2 \\
\vdots & \vdots & \ddots & \vdots \\
\tilde{x}^{(1)}_n & \tilde{x}^{(1)}_n & \dots & \tilde{x}^{(n)}_n \\
\end{pmatrix}, \qquad U_{ij} = \sqrt{\frac{2}{n+1}} \sin \frac{\pi i j}{(n + 1)}
$$
Matrix $U$ is orthogonal, so $U^\mathsf{T} = U^{-1}$. Also $U_{ij} = U_{ji}$, so $U^\mathsf{T} = U$. Writing the $A \mathbf{x} = \lambda \mathbf{x}$ in matrix form we have
$$
A U = U \Lambda
$$
where $$\Lambda = \operatorname{diag} \begin{pmatrix}
4\sin^2 \frac{\pi}{2(n+1)} &
4\sin^2 \frac{2\pi}{2(n+1)} & \dots &
4\sin^2 \frac{n\pi}{2(n+1)}
\end{pmatrix}.$$
Hence,
$$
A = U \Lambda U^T = U \Lambda U\\
\Lambda = U A U
$$
