# Finding eigenvalues of a nearly tridiagonal matrix

Consider the $2N\times 2N$ matrix

$$A=\begin{pmatrix} a &1 &0&0&0&\ldots&0&1 \\1 &-a&1 & 0 &0 & \ldots & 0&0 \\0 &1&a&1&0 &\cdots &0&0 \\ 0&0&1&-a &1 & \ldots &0&0 \\& & & \cdots \\ 1&0 &0&0&0&\ldots &1&-a\end{pmatrix}$$

Hopefully the structure is clear, but if not I can clarify further.

I am trying to find the eigenvalues of $A$ analytically.

There is a lot of literature exclusively on eigenvalues of tridiagonal matrices and circulant matrices, however $A$ is neither exactly circulant nor is it exactly tridiagonal. However it is very close to being both.

I have worked out a few cases:

For $N=2$, the eigenvalues are

$$\lambda_{1,2} = \pm a$$ $$\lambda_{3,4} = \pm \sqrt{a^2+4}$$

For $N = 3$, the eigenvalues are

$$\lambda_{1,2} = -\sqrt{1+a^2}$$ $$\lambda_{3,4} = \sqrt{1+a^2}$$ $$\lambda_{5,6} = \pm \sqrt{a^2+4}$$

So it seems there is some sort of 'pattern'.

Any ideas on how I would advance?

• There are recursion formulas for the characteristic polynomial for such symmetric banded matrices. One should be able to obtain an explicit formula here, compare with this question. – Dietrich Burde Mar 29 '16 at 13:05
• Could you recommend a way forward? – fosho Mar 29 '16 at 14:47

(Too long for a comment.) To stress the dependence on $N$, we write $A_{2N}$ for $A$. Some quick observations:

• $A_{2N}$ must possess a pair of eigenvalues $\pm\sqrt{a^2+4}$, because by considering $v=(x,y,x,y,\ldots,x,y)^T$, the equation $Av=\lambda v$ reduces to $\pmatrix{a&2\\ 2&-a}\pmatrix{x\\ y}=\lambda \pmatrix{x\\ y}$.
• When $N$ is even, $N$ eigenvalues of $A_{2N}$ are the eigenvalues of $A_N$, because if we consider an eigenvector of the form $v^T=(u^T,u^T)$ where $u\in\mathbb R^N$, then $A_{2N}v=\lambda v$ reduces to $A_Nu=\lambda u$. This includes the aforementioned pair of eigenvalues $\pm\sqrt{a^2+4}$.
• Eigenvectors of $A_4$ are of the forms $(x,y,x,y)^T,\ (1,0,-1,0)^T$ or $(0,1,0,-1)^T$.
• Eigenvectors of $A_6$ are of the forms $(x,y,x,y,x,y)^T,\ (x,y,0,-y,-x,0)^T$ or $(x,0,-x,-y,0,y)^T$. Not sure if there's a pattern.

Edit. More observations:

• Let $A=B+D$, where $D$ is the diagonal part of $A$. Let also $C$ be the permutation matrix for the cycle $(2,3,\ldots,n)$. Then $C^TBC=B$ and $C^TDC=-D$. It follows that if $(\lambda,v)$ is an eigenpair of $A$, then $(\lambda,C^{2k}v)$ is an eigenpair too for every integer $k$.
• When $N\ge4$ is even, suppose $(\lambda,u)$ is an eigenpair of $A_N$. Let $v^T=(u^T,u^T)$ and $w^T=(u^T,-u^T)$. Then $(\lambda,v)$ and $(\lambda,w)$ are eigenpairs of $A_{2N}$. Apparently, the set of vectors $\{v,C^2v,C^4v,\ldots,C^{2N-2}v, w,C^2w,C^4w,\ldots,C^{N-2}w\}$ span $\mathbb R^{2N}$. If this is really the case, then the eigenvalues of $A_{2N}$ are just the eigenvalues of $A_N$, but doubled in multiplicities.
• When $N\ge5$ is odd, suppose $(\lambda,u)$ is an eigenpair of $A_{N-1}$ (so that $u\in\mathbb R^{N-1}$). Let $v^T=(u^T,0,u^T,0)$ and $w^T=(u^T,0,-u^T,0)$. Then $(\lambda,v)$ and $(\lambda,w)$ are eigenpairs of $A_{2N}$. Apparently, the set of vectors $\{v,C^2v,C^4v,\ldots,C^{2N-2}v, w,C^2w,C^4w,\ldots,C^{N-2}w\}$ span $\mathbb R^{2N-2}$. If this is really the case, then the eigenvalues of $A_{2N}$ are just the eigenvalues of $A_{N-1}$ (but doubled in multiplicities) together with $\pm\sqrt{a^2+4}$.
• How can you tell the eigenvectors have that form in you last 2 bullets? – fosho Mar 29 '16 at 17:49
• @Daniel I simply got that from Wolfram Alpha. – user1551 Mar 29 '16 at 18:03
• Oh ok, I thought you were doing some magic! Thanks for your response, how would I get the eigenvalues from the eigenvectors? – fosho Mar 29 '16 at 18:05
• @Daniel If you put $v=(x,y,0,-y,-x,0)^T$, then $A_6v=\lambda v$ reduces to $A_2\pmatrix{x\\ y}=\lambda\pmatrix{x\\ y}$. This gives two eigenvalues $\pm\sqrt{a^2+1}$. The case $(x,0,-x,-y,0,y)^T$ is analogous. If you are lucky and there is indeed a pattern for the eigenvectors, this trick may help you determine all eigenvalues. But of course, it might also fail. – user1551 Mar 29 '16 at 18:18

Hint: If $a=0$, then your matrix is the adjacency matrix (denote by $\mathcal{A}(C_{2n})$) of a cycle graph ($C_{2n}$). The eigenvalues in this case are: $$2\cos\left(\frac{j\pi}{n}\right)\text{ for }j=0, 1, \ldots, 2n-1.$$ If $a\ne0$, then $A=\mathcal{A}(C_{2n})+D$, where $D$ is a diagonal matrix whose diagonal entries are form the alternate pattern $a, -a, a, -a, \cdots$. Further, $\mathcal{A}(C_{2n})\cdot D=-D\cdot\mathcal{A}(C_{2n})$. So consider the eigenvectors of both the matrices.

• How will considering the eigenvectors of both help the eigenvalues of A? – fosho Mar 30 '16 at 5:13
• @Daniel : Sorry! I was wrong in saying the eigenvectors will help. But I have computed further and for $n=5$ eigenvalues are $$\left\{\pm\sqrt{a^2+4}, \pm\sqrt{a^2\pm\frac{\sqrt{5}}{2}+\frac{3}{2}}\right\}$$ – G_0_pi_i_e Mar 30 '16 at 11:07
• Similarly, for $n=6$ $$\left\{\pm a, \pm\sqrt{a^2+1}, \pm\sqrt{a^2+3}, \pm\sqrt{a^2+4}\right\}$$ – G_0_pi_i_e Mar 30 '16 at 11:10