# 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.

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.

Case 1. $\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 2. $\lambda < 0$. $q_{1,2} \in \mathbb{R}, |q_1| > 1, |q_2| < 1$. Generic solution is $$x_k = C_1 e^{q_1 k} + C_2 e^{q_2 k}$$ From left condition $C_1 = C_2$. Let $C_1 = 1$ $$x_{n+1} = e^{q_1 (n+1)} + e^{q_2 (n+1)} = 0$$ No solution of that when $q_1, q_2$ are real exist.

Case 3. $\lambda > 0$. 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$$

• Can we then get the solution of $-X_{k-1} + 2X_{k} -X_{k+1} = (N + 1)^2$ ? – YVvjhvbh May 10 '15 at 2:05
• For the homogenous equation $X_k = A k + B$. Since $(k+1)^2 - 2k + (k-1)^2 = 2$ the (one) solution of the equation is $X_k = -\frac{(N+1)^2}{2}k^2$. So all of the solutions are $$X_k = -\frac{(N+1)^2}{2}k^2 + A k + B$$ – uranix May 10 '15 at 8:17
• @YVvjhvbh I suggest you read this wikipedia article en.wikipedia.org/wiki/… – uranix May 10 '15 at 9:01