7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There's always row reduction ... $\endgroup$ – Neal Sep 3 '16 at 6:52
  • 1
    $\begingroup$ 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? $\endgroup$ – ekkilop Sep 3 '16 at 12:59
  • $\begingroup$ @ekkilop There's no typo, it's a 1. $\endgroup$ – anderstood Sep 3 '16 at 13:11
  • $\begingroup$ Should $p$ be replaced by $k$ in $\lambda_k=\dots$? $\endgroup$ – Ignat Domanov Sep 3 '16 at 14:34
  • $\begingroup$ also $M_{23}=-1$? $\endgroup$ – Ignat Domanov Sep 3 '16 at 15:19
2
$\begingroup$

Partial answer: We can find the eigenvalues directly from the characteristic polynomial.

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.

$\endgroup$
1
$\begingroup$

Probably, an alternative way is to consider this matrix as an approximation up to a factor of the 1d laplacian with dirichlet boundary condition for x = 0 and neumann for x = 1. Then the eigenvector is a discrete version of a continuous eigenfunction which can be found by solving the corresponding differential eigenproblem

$\endgroup$

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.