Finding eigenvalues of an 'almost-tridiagonal' circulant matrix

Question

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 tridaigonal. 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?

Answer 1

If you make an even-odd permutation, your matrix becomes $$ \begin{bmatrix} aI & I+Z\\ I+Z^{-1} & -aI \end{bmatrix}, $$ where $Z$ is the generator of the circulant algebra. Let $Z=FDF^{-1}$ be its eigendecomposition. It is well known that $F$ is the Fourier matrix and $D$ has $\zeta^i$, $i=0,1,\dots,n-1$ on its diagonal, where $\zeta$ is a primitive $n$th root of 1. Then, pre- and post-multiply by $\operatorname{diag}(F,F)$ and its inverse, to get $$ \begin{bmatrix} aI & I+D\\ I+D^{-1} & -aI \end{bmatrix}, $$ Make an even-odd permutation again, and your matrix decouples into the direct sum of $n$ $2\times 2$ matrices of the form $$ \begin{bmatrix} a & \zeta^i+1\\ \zeta^{-i}+1 & -a \end{bmatrix}, \quad i=0,1,\dots,n-1, $$ of which you can easily compute the eigenvalues.