# Eigenvectors and eigenvalues of nonsymmetric Tridiagonal matrix

Hi, the question is following: We have one matrix $$\begin{pmatrix} -\beta & \Delta & 0 & 0 &\cdots & 0 & 0 & 0 \newline \beta & -(\beta+\Delta) & \Delta & 0 &\cdots & 0 & 0 & 0 \newline 0 & \beta & -(\beta + \Delta) & \Delta &\cdots & 0 & 0 & 0 \newline \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots& \vdots \newline 0 & 0 & 0 & 0 &\cdots & \beta & -(\beta + \Delta) & \Delta \newline 0 & 0 & 0 & 0 & \cdots & 0 & \beta & -(\beta + \Delta) \end{pmatrix}.$$

Is it possible to find analytically all eigenvalues and eigenvectors of this matrix? What I found here is quite similar, but not exactly the same. The element in the last row and last column $-(\beta +\Delta)$ can be replaced by $-\Delta$ if it simplifies the solution. $\beta>0$, $\Delta>0$.

Thanks

-
Your matrix is diagonally similar to a symmetric tridiagonal matrix, with 'off-diagonal entries' equal to $\sqrt{\beta\Delta}$. The characteristic polynomial will be a linear combination of two Chebyshev polynomials. –  Chris Godsil Aug 22 '12 at 12:23
What do you mean by analytically find all eigenvalues? These can of course be found by solving a polynomial equation. Now, in the limit, by using the work of Schmidt and Spitzer, you can also describe the limit set of eigenvalues. –  Per Alexandersson Aug 22 '12 at 16:30
I may be missing something, but the characteristic polynomial of this matrix satisfies a simple two-order linear recurrence (well, not exactly, as the first coefficient of the diagonal is not regular), which implies a closed-form at least for the eigenvalues –  Feldmann Denis Aug 22 '12 at 17:14
@Chris Godsil: Thanks! Sorry, I don't see your point. How exactly can I resolve this problem with a combination of Chebyshev polynomials? –  Cherep Aug 23 '12 at 8:17
@Paxinum: Thanks! I would like to get all eigenvalues in a closed form. The limit set of eigenvalues is not of interest. –  Cherep Aug 23 '12 at 8:17

As Denis remarked, the characteristic polynomial $P_n(\lambda)$ of the $n \times n$ matrix does satisfy a three-term linear recurrence $$P_{n+2}(\lambda) = (\lambda + \beta + \Delta) P_{n+1}(\lambda) - \beta \Delta P_n(\lambda)$$ with initial conditions $P_1(\lambda) = \lambda+\beta$, $P_2(\lambda) = \lambda^2+(2 \beta+\Delta)\lambda +\beta^2$, and then $$P_n(\lambda) = \frac{(P_2 - r_2 P_1)}{r_1 (r_1 - r_2)} r_1^n + \frac{(P_2 - r_1 P_1)}{r_2 (r_2 - r_1)} r_2^n$$ where $r_1$ and $r_2$ are the roots of $r^2 - (\lambda + \beta + \Delta) r + \beta \Delta$. However, I don't see how this implies a "closed form" for the eigenvalues.

EDIT: By scaling, we may as well assume $\Delta=1$. I don't know if this leads to a "closed form", but the eigenvalue $\lambda_0$ that is analytic in a neighbourhood of $\beta=0$ has some interesting regularities in its Maclaurin series:

$$\matrix{n=2 & -\beta^{2}+2 \beta^{3}-5 \beta^{4}+14 \beta^{5}-42 \beta^{6}\cr&+132 \beta^{7}-429 \beta^{8}+1430 \beta^{9}-4862 \beta^{10}\cr n=3 & -\beta^{3}+2 \beta^{4}-\beta^{5}-6 \beta^{6}+20 \beta^{7}\cr&-22 \beta^{8}-49 \beta^{9}+260 \beta^{10}-441 \beta^{11}\cr&-320 \beta^{12}+3652 \beta^{13}\cr n=4 & -\beta^{4}+2 \beta^{5}-\beta^{6}-8 \beta^{8}+26 \beta^{9}\cr&-28 \beta^{10}+10 \beta^{11}-100 \beta^{12}+442 \beta^{13}\cr&-729 \beta^{14}+532 \beta^{15}-1641 \beta^{16}\cr n=5 & -\beta^{5}+2 \beta^{6}-\beta^{7}-10 \beta^{10}+32 \beta^{11}\cr&-34 \beta^{12}+12 \beta^{13}-155 \beta^{15}+672 \beta^{16}\cr&-1089 \beta^{17}+782 \beta^{18}-210 \beta^{19}\cr n=6 & -\beta^{6}+2 \beta^{7}-\beta^{8}-12 \beta^{12}+38 \beta^{13}\cr&-40 \beta^{14}+14 \beta^{15}-222 \beta^{18}+950 \beta^{19}\cr&-1521 \beta^{20}+1080 \beta^{21}-287 \beta^{22}\cr n=7 & -\beta^{7}+2 \beta^{8}-\beta^{9}-14 \beta^{14}+44 \beta^{15}\cr&-46 \beta^{16}+16 \beta^{17}-301 \beta^{21}+1276 \beta^{22}\cr&-2025 \beta^{23}+1426 \beta^{24}-376 \beta^{25}\cr n=8 & -\beta^{8}+2 \beta^{9}-\beta^{10}-16 \beta^{16}+50 \beta^{17}\cr&-52 \beta^{18}+18 \beta^{19}-392 \beta^{24}+1650 \beta^{25}\cr&-2601 \beta^{26}+1820 \beta^{27}-477 \beta^{28}\cr n=9 & -\beta^{9}+2 \beta^{10}-\beta^{11}-18 \beta^{18}+56 \beta^{19}\cr&-58 \beta^{20}+20 \beta^{21}-495 \beta^{27}+2072 \beta^{28}\cr&-3249 \beta^{29}+2262 \beta^{30}-590 \beta^{31}\cr n=10 & -\beta^{10}+2 \beta^{11}-\beta^{12}-20 \beta^{20}+62 \beta^{21}\cr&-64 \beta^{22}+22 \beta^{23}-610 \beta^{30}+2542 \beta^{31}\cr&-3969 \beta^{32}+2752 \beta^{33}-715 \beta^{34}\cr}$$

All coefficients are integers, and it starts with $-\beta^n + 2 \beta^{n+1} - \beta^{n+2} - 2 n \beta^{2n} + (6n+2) \beta^{2n+1} - (6n+4) \beta^{2n+2} + (2n+2) \beta^{2n+3} - (6n+1)n \beta^{3n} \ldots$

-
Yes, my mistake : I forgot the $\lambda$ dependency of $r_1$ and $r_2$... –  Feldmann Denis Aug 22 '12 at 19:10
@Robert Israel: this makes sense. Two questions: 1) how to get $P_n(\lambda) = \frac{(P_2 - r_1 P_1)}{r_1 (r_1 - r_2)} r_1^n + \frac{(P_2 - r_2 P_1)}{r_2 (r_2 - r_1)} r_2^n$? 2) I also don't see how it leads to a closed form solution for $\lambda$. Any further ideas? Many thanks! –  Cherep Aug 23 '12 at 8:14
@Cherep: Oops, the $P_2 - r_1 P_1$ and $P_2 -r_2 P_1$ should have been interchanged. I'll correct it. How to get this? Let $P_n(\lambda) = a_1 r_1^n + a_2 r_2^n$ where $r_1^n$ and $r_2^n$ satisfy the recurrence, and solve for $a_1$ and $a_2$ to make it work for $n=1$ and $n=2$. –  Robert Israel Aug 23 '12 at 17:00
Is "two-term recurrence" correct? Or should we say "three-term recurrence"? –  Pantelis Damianou Aug 24 '12 at 7:37
You're right. Thanks for spotting it. –  Robert Israel Aug 24 '12 at 16:23

Various commenters have pointed out that one can easily get asymptotic estimates for the eigenvalues as $n \rightarrow \infty$ (specifically, with $\beta, \Delta > 0$ they converge to $-2 (\beta + \Delta) \cos(\pi k/2 n)^2$ for $k = 1$ to $n$). OTOH, you specify in the comments that you require the eigenvalues in exact form. This is not possible. Even for $n = 5$, $\beta = 2$, and $\Delta = 1$, the characteristic polynomial of the matrix above is $$x^5 + 14 x^4 + 70 x^3 + 150 x^2 + 129 x + 32$$ whose splitting field has Galois group $S_5$, and hence there cannot be any exact formula (in radicals) for the roots by a theorem of Abel. This suggests that it is highly unlikely that there exists any "exact" formula for the roots, although "exact formula" is a somewhat nebulous notion, since of course one can define a function $f_{n,k}(\beta,\Delta)$ to be the $k$th smallest root of the corresponding characteristic polynomial.

-
Don't you have some memoirs to be getting back to? ;-) –  Yemon Choi Aug 24 '12 at 22:19
Perhaps, but the truth is,—I am not a wise man;—and besides am a mortal of so little consequence in the world, it is not much matter what I do: so I seldom fret or fume at all about it. –  Tristram Shandy Aug 24 '12 at 22:27
There is no expression in terms of radicals. There are expressions in terms of special functions. See e.g. en.wikipedia.org/wiki/… –  Robert Israel Aug 24 '12 at 23:02
@Israel: You missed the point. Presumably any "exact" solution (already a somewhat nebulous notion) that applies for all $n$ is not going to specialize for $n = 5$ into an expression involving special functions related to the symmetries of the Icosahedron. But thanks, anyway, for taking the time to stop, read my answer, post a condescending and irrelevant link to something I already know, and not upvote my answer. –  Tristram Shandy Aug 24 '12 at 23:36

There are such formulas, but beware: they are rather intimidating.

Look at this paper:

"EXPLICIT EIGENVALUES AND INVERSES OF TRIDIAGONAL TOEPLITZ MATRICES WITH FOUR PERTURBED CORNERS" by WEN-CHYUAN YUEH and SUI SUN CHENG2, ANZIAM J. 49(2008), 361–387.

-
I found another paper which is cited in the paper you've mentioned: "Eigenvalues of several tridiagonal matrices" by W.C. Yueh. If I apply eq.6 from there, I get in my case something like: $\beta \sin(n+1)\theta - \sqrt{\beta \Delta} \sin n\theta=0$ where all eigenvalues, $\lambda$'s, can be written in the form $\lambda = -(\beta+\Delta)+2\sqrt{\beta \Delta} \cos \theta$. Do you think there is a way how to solve $\beta \sin(n+1)\theta - \sqrt{\beta \Delta} \sin n\theta=0$? Of course, it can be solved for $\beta=\Delta$, but this is not what we are looking for... :) –  Cherep Aug 29 '12 at 7:48