5
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can we then get the solution of $ -X_{k-1} + 2X_{k} -X_{k+1} = (N + 1)^2 $ ? $\endgroup$ – YVvjhvbh May 10 '15 at 2:05
  • $\begingroup$ 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$$ $\endgroup$ – uranix May 10 '15 at 8:17
  • $\begingroup$ @YVvjhvbh I suggest you read this wikipedia article en.wikipedia.org/wiki/… $\endgroup$ – uranix May 10 '15 at 9:01

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.