Eigenvectors and eigenvalues of Tridiagonal matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T23:12:37Z http://mathoverflow.net/feeds/question/91161 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix Eigenvectors and eigenvalues of Tridiagonal matrix surfstack 2012-03-14T10:51:09Z 2012-03-18T16:55:55Z <p>Hi, is it possible to analytically evaluate the eigenvectors and the eigenvalues of a tridiagonal matrix of the form : </p> <p>$$\mathcal{T}^{a}_n(p,q) = \begin{pmatrix} 0 &amp; q &amp; 0 &amp; 0 &amp;\cdots &amp; 0 &amp; 0 &amp; 0 \\ p &amp; 0 &amp; q &amp; 0 &amp;\cdots &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; p &amp; 0 &amp; q &amp;\cdots &amp; 0 &amp; 0 &amp; 0 \\ \vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots&amp; \vdots \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp;\cdots &amp; p &amp; 0 &amp; q \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; \cdots &amp; 0 &amp; p &amp; 0 \end{pmatrix}$$</p> <p>where $p>0\ \ \&amp; \ \ q > 0$ and where there are $n$ rows and $n$ columns in the matrix above?</p> <p>Furthermore is it possible to do the same for the equivalent matrix where periodic boundary conditions are implemented? i.e.</p> <p>$$\mathcal{T}^{b}_n(p,q) = \begin{pmatrix} 0 &amp; q &amp; 0 &amp; 0 &amp;\cdots &amp; 0 &amp; 0 &amp; p \\ p &amp; 0 &amp; q &amp; 0 &amp;\cdots &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; p &amp; 0 &amp; q &amp;\cdots &amp; 0 &amp; 0 &amp; 0 \\ \vdots &amp; \vdots &amp; \vdots &amp; \vdots &amp; \ddots &amp; \vdots &amp; \vdots&amp; \vdots \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp;\cdots &amp; p &amp; 0 &amp; q \\ q &amp; 0 &amp; 0 &amp; 0 &amp; \cdots &amp; 0 &amp; p &amp; 0 \end{pmatrix}$$</p> <p>Thanks</p> http://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix/91166#91166 Answer by Denis Serre for Eigenvectors and eigenvalues of Tridiagonal matrix Denis Serre 2012-03-14T12:08:03Z 2012-03-16T06:47:13Z <p>Here is the calculation of the spectrum of the first matrix, which I write $pJ+qK$ with $K=J^T$. Define $D={\rm diag}(1,a,a^2,\ldots,a^{n-1})$. Then $D^{-1}JD=a^{-1}J$ and $D^{-1}KD=aK$. Thus, taking $a=\sqrt{p/q}$, one sees that you matrix is similar to $\sqrt{pq}(J+K)$. Its eigenvalues are $\sqrt{pq}$ times those of $J+K$. The spectrum of the latter matrix is made of numbers $2\cos\frac{k\pi}{n+1}$ for $k=1,\ldots,n$.</p> <p>The second case is easy too. Eigenvectors are $n$-periodic solutions of the recursion $qu_{j+1}+pu_{j-1}=\lambda u_j$. This means that some power of $\omega=\exp\frac{2i\pi}n$ is a root of the characteristic equation $qr^2+p=\lambda r$. Whence the spectrum $\lambda_1,\ldots,\lambda_n$ $$\lambda_j=p\omega^{-j}+q\omega^j.$$</p> http://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix/91229#91229 Answer by Emilio Pisanty for Eigenvectors and eigenvalues of Tridiagonal matrix Emilio Pisanty 2012-03-14T22:39:40Z 2012-03-16T19:26:55Z <p>Another way to look at this problem, from the ground up, is to expand the characteristic polynomial of your first matrix, $\mathcal{T}_n(p,q)$, along the last row and then along the last column, from which you'll quickly get <code>$$\det(\mathcal{T}_n(p,q)-\lambda)=-\lambda \det(\mathcal{T}_{n-1}(p,q)-\lambda)-pq \det(\mathcal{T}_{n-2}(p,q)-\lambda).$$</code> You can then compare this with the recurrence relations for the standard orthogonal polynomials; it is then rather easy to match it to that for the <a href="http://en.wikipedia.org/wiki/Chebyshev_polynomials" rel="nofollow">Chebyshev polynomials of the first kind</a>, <code>$$T_{n+1}(x)=2x T_n(x)-T_{n-1}(x),$$</code> with $T_0(x)=1$, $T_1(x)=x$,which should make it clear that the identification is <code>$$T_n(\lambda)=\frac{1}{2(\sqrt{pq})^n}\det\left(\mathcal{T}_n(p,q)+2\sqrt{pq}\lambda\right),$$</code> or the equivalent $\det(\mathcal{T}_n(p,q)-\lambda)=2(\sqrt{pq})^n T_n\left(\frac{-\lambda}{2\sqrt{pq}}\right)$. Since the Chebyshev polynomials are given by $T_n(\cos(\theta))=\cos(n\theta)$, this gives all the eigenvalues. The reason this happens is that (Denis' symmetric version of) your matrix is the Jacobi matrix for the Chebyshev polynomials. You can exploit this to get the eigenvectors in terms of lower order polynomials $T_m$, $m\leq n$, evaluated at the eigenvalue; the construction is in </p> <p>Gautschi, Walter. Orthogonal Polynomials, Computation and Approximation. Numerical Mathematics and Scientic Computation, Oxford University Press, 2004..</p> http://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix/91338#91338 Answer by Yemon Choi for Eigenvectors and eigenvalues of Tridiagonal matrix Yemon Choi 2012-03-15T23:25:14Z 2012-03-15T23:25:14Z <p>If I have read your question correctly, the second matrix is a so-called <a href="http://en.wikipedia.org/wiki/Circulant_matrix" rel="nofollow">circulant matrix</a>, and so one can read off the spectrum using known methods. Wikipedia gives you a formula that can be used.</p> <p>That said, I prefer to approach things from scratch. A circulant $n\times n$ matrix can always be written as $f(S)$ where $f$ is a polynomial of degree $\leq n-1$ and $S$ is a cyclic shift matrix of order $n$. If the first column of the matrix reads $a_0, \dots, a_{n-1}$, then take $S$ to be the shift matrix $e_1\mapsto e_2 \mapsto \dots \mapsto e_n \mapsto e_1$, and take $f(z)=a_0+a_1z+ \dots + a_{n-1}z^{n-1}$.</p> <p>So in your case, the matrix is just $A=pS+ qS^{n-1} = pS + qS^{-1}$, and since we know the eigenvalues of $S$ (they are the $n$ distinct complex $n$th roots of unity) and corresponding one-dimensional eigenspaces, this allows us to write down the eigenvalues of $A$</p> <p><code>$$\{ p\omega^j + q\omega^{-j} : j=0,1,\dots, n-1\} \quad\quad(\omega=\exp(2\pi i/n)$$</code></p> <p>with corresponding eigenvectors (depending on the values of $p$ and $q$ some of the eigenvalues may have non-trivial multiplicity).</p> http://mathoverflow.net/questions/91161/eigenvectors-and-eigenvalues-of-tridiagonal-matrix/91358#91358 Answer by Johann Cigler for Eigenvectors and eigenvalues of Tridiagonal matrix Johann Cigler 2012-03-16T08:58:17Z 2012-03-18T16:55:55Z <p>@ Emilio: Could you please show how you get $\det(\mathcal{T}_n(p,q)-\lambda)=2(pq)^n T_n(-\lambda/2)$?</p> <p>Sorry I wanted to comment another answer. I do not know how to delete this post.</p> <p><strong>Edit</strong></p> <p>I think the first problem can be reduced to Chebyshev polynomials of the second kind ${U_n}(x)$ because </p> <p>$$\det \left( {{T_n}(p,q) - \lambda } \right) = - \lambda \det \left( {{T_{n - 1}}(p,q) - \lambda } \right) - pq\det \left( {{T_{n - 2}}(p,q) - \lambda } \right).$$</p> <p>implies</p> <p>$$\det \left( {{T_n}(p,q) - \lambda } \right) ={(\sqrt {pq} )^n}{U_n}\left( {-\frac{\lambda }{{2\sqrt {pq} }}} \right).$$</p> <p>From the fact that the zeros of ${U_n}(x)$ are $\cos \frac{{k\pi }}{{n + 1}}$ the eigenvalues are<br> $2\sqrt {pq} \cos \frac{{k\pi }}{{n + 1}}.$</p>