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?
 A: (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}$.

A: 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.
