# Eigenvectors and eigenvalues of Tridiagonal matrix

Hi, is it possible to analytically evaluate the eigenvectors and the eigenvalues of a tridiagonal matrix of the form :

$$\mathcal{T}^{a}_n(p,q) = \begin{pmatrix} 0 & q & 0 & 0 &\cdots & 0 & 0 & 0 \\\ p & 0 & q & 0 &\cdots & 0 & 0 & 0 \\\ 0 & p & 0 & q &\cdots & 0 & 0 & 0 \\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots& \vdots \\\ 0 & 0 & 0 & 0 &\cdots & p & 0 & q \\\ 0 & 0 & 0 & 0 & \cdots & 0 & p & 0 \end{pmatrix}$$

where $p>0\ \ \& \ \ q > 0$ and where there are $n$ rows and $n$ columns in the matrix above?

Furthermore is it possible to do the same for the equivalent matrix where periodic boundary conditions are implemented? i.e.

$$\mathcal{T}^{b}_n(p,q) = \begin{pmatrix} 0 & q & 0 & 0 &\cdots & 0 & 0 & p \\\ p & 0 & q & 0 &\cdots & 0 & 0 & 0 \\\ 0 & p & 0 & q &\cdots & 0 & 0 & 0 \\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots& \vdots \\\ 0 & 0 & 0 & 0 &\cdots & p & 0 & q \\\ q & 0 & 0 & 0 & \cdots & 0 & p & 0 \end{pmatrix}$$

Thanks

-
See my edits, which fix the second case. –  Denis Serre Mar 16 '12 at 6:47
I wrote my answer before Denis had fixed the second case. Apologies for any redundancy. –  Yemon Choi Mar 16 '12 at 7:54

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

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

-
I don't think the eigenvalues of the second matrix given here are correct. The answer should be real when $p=q$, which the answer supplied here is not. –  alex o. Mar 15 '12 at 0:40
@alex. You're right. See my edit. –  Denis Serre Mar 15 '12 at 9:53
@Denis Serre - I think its still not right. It isn't true that the spectrum will be real - for example, if $p=2,q=1,n=4$ then $-i$ is an eigenvalue with eigenvector $[1,i,-1,-i]$. –  alex o. Mar 15 '12 at 20:43
@Alex. Yes, my trick does not work for the second matrix. I withdraw this point. –  Denis Serre Mar 15 '12 at 22:13

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 $$\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).$$ 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 Chebyshev polynomials of the first kind, $$T_{n+1}(x)=2x T_n(x)-T_{n-1}(x),$$ with $T_0(x)=1$, $T_1(x)=x$,which should make it clear that the identification is $$T_n(\lambda)=\frac{1}{2(\sqrt{pq})^n}\det\left(\mathcal{T}_n(p,q)+2\sqrt{pq}\lambda\right),$$ 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

Gautschi, Walter. Orthogonal Polynomials, Computation and Approximation. Numerical Mathematics and Scientic Computation, Oxford University Press, 2004..

-
Thanks. Just remembered this morning I had read a derivation in the context of field theory several years back, in "Field theory, a path integral approach" by Ashok Das, chapter 3.3 Harmonic Oscillator, Matrix Method. This approach parallels the one above. –  user22127 Mar 15 '12 at 20:51
@ Emilio: Could you please show how you get $\det(\mathcal{T}_n(p,q)-\lambda)=2(pq)^n T_n(-\lambda/2)$? –  Johann Cigler Mar 16 '12 at 9:02
@Johann: You can't - I made an error with the normalizations, it's corrected now. I think the easiest way is to say $\det(\mathcal{T}_n(p,q)-\lambda)=a b^n T_n\left(c\lambda\right)$ for some constants $a, b, c$. Comparing the recursion relations gives constraints for $b$ and $c$, and the first polynomial, for $n=1$, gives the overall normalization $a$. –  Emilio Pisanty Mar 16 '12 at 19:29
@Emilio: I think that the correct formula is as in my answer $\det(\mathcal{T}_n(p,q)-\lambda)=(\sqrt{pq})^n U_n\left(\frac{-\lambda}{2\sqrt{pq}}\right)$ with the Chebyshev polynomials of the second kind. –  Johann Cigler Mar 16 '12 at 20:37
@Emilio: Perhaps I should add a proof. Let $a(n, x)=\det(\mathcal{T}_n(p,q)-x)$. As you have shown this sequence satisfies the recurrence $a(n, x)=-x a(n-1, x)-pqa(n-2,x)$ with initial values $a(1, x)=-x$ and $a(2, x)= x^2-pq.$ Therefore $b(n,x)= (1/{\sqrt {pq}) ^n}a(n, - 2 \sqrt {pq} x)$ satisfies $b(n,x)=2xb(n-1,x)-b(n-2,x)$ with initial values $b(1,x)=2x$ and $b(2,x)=4x^2-1$ and therefore $b(n,x) = {U_n}(x).$ –  Johann Cigler Mar 17 '12 at 7:35

If I have read your question correctly, the second matrix is a so-called circulant matrix, and so one can read off the spectrum using known methods. Wikipedia gives you a formula that can be used.

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

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\omega^j + q\omega^{-j} : j=0,1,\dots, n-1\} \quad\quad(\omega=\exp(2\pi i/n)$$

with corresponding eigenvectors (depending on the values of $p$ and $q$ some of the eigenvalues may have non-trivial multiplicity).

-
Note: at the time I wrote this answer, Denis Serre's answer was temporarily missing an answer to the second part. –  Yemon Choi Mar 16 '12 at 7:52

@ Emilio: Could you please show how you get $\det(\mathcal{T}_n(p,q)-\lambda)=2(pq)^n T_n(-\lambda/2)$?

Sorry I wanted to comment another answer. I do not know how to delete this post.

Edit

I think the first problem can be reduced to Chebyshev polynomials of the second kind ${U_n}(x)$ because

$$\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).$$

implies

$$\det \left( {{T_n}(p,q) - \lambda } \right) ={(\sqrt {pq} )^n}{U_n}\left( {-\frac{\lambda }{{2\sqrt {pq} }}} \right).$$

From the fact that the zeros of ${U_n}(x)$ are $\cos \frac{{k\pi }}{{n + 1}}$ the eigenvalues are
$2\sqrt {pq} \cos \frac{{k\pi }}{{n + 1}}.$

-