Can the eigenvalues of this block circulant matrix be found? I have a matrix of the form
$$ M = \begin{pmatrix} A & A^T & & & I\\ I & A & A^T & & \\ &  I & A  & \ddots &\\ & & \ddots & \ddots & A^T\\ A^T & & & I & A \end{pmatrix}$$
where $I$ is an $n \times n$ identity matrix and $A$ is an $n \times n$-matrix given by
$$ A = \begin{pmatrix} 0 & 1 & 0 & \dots & 0\\ \vdots & \ddots& \ddots & \ddots & \vdots\\ 0 & \dots & 0 & 1 & 0\\ 0 & \dots &  & 0 & 1\\ 0 & \dots & & & 0 \end{pmatrix}$$
that is a matrix which has ones on the super diagonal and zeros everywhere else.

*

*Is there some way to find the eigenvalues of this matrix?


*If there is, can it be generalized to a more complicated $A$?
Since $A$ and $A^T$ don't commute, one cannot diagonalize them simultaneously (also, they are not even diagonalizable), otherwise that would have been a straightforward way to do it. I have tried computing the characteristic polynomial, but I cannot seem to find a way to simplify the determinant.
 A: The eigenvalues and eigenvectors can be found exactly. Let the number of block rows in $M$ be $K$. Let's write the eigenproblem as $MX = \lambda X$ where $X$ is a block vector
$$
X = \begin{pmatrix}
x_1\\
x_2\\
\vdots\\
x_K
\end{pmatrix}
$$
Each block row eigenvalue equation can now be written as
$$Ax_k + A^\top x_{k+1} + x_{k-1} = \lambda x_k, \quad k= 1, \dots, K.$$
Here $x_k$ are assumed to be periodical, so $x_{K+1} \equiv x_1$ and $x_0 \equiv x_K$. Each $x_k$ is a vector of length $n$.
Let's apply discrete Fourier transform, just like it is done for regular circulant matrices.
$$
x_k = \sum_{m=0}^{K-1} \omega^{m(k-1)} z_m
$$
Here $\omega = \exp \frac{2 \pi i} {K}$ and each $z_m$ is a vector of length $n$.
Let's call
$$X^{(m)} = \begin{pmatrix}
z_m\\
\omega^m z_m\\
\vdots\\
\omega^{m(k-1)} z_m\\
\vdots\\
\omega^{m(K-1)} z_m
\end{pmatrix}
= f_m \otimes z_m.
$$
the $m$-th harmonic of the solution $X$. Here $f_m$ is the $m$-th column of the $DFT$-like matrix and $\otimes$ denotes Kronecker product.
It is obvious that
$$
X = X^{(0)} + \dots + X^{(K-1)}.
$$
I state that all eigenvectors $X$ of the original problem can be found as pure harmonics, that is all $X^{(m)} = 0$ except for some $m = m_0$. Harmonics are linearly independent since they are orthogonal:
$$
(X^{(m)}, X^{(m')}) = (f_m \otimes z_m, f_{m'} \otimes z_{m'}) = (f_m, f_{m'}) (z_m, z_{m'}) = K \delta_{mm'} (z_m, z_{m'}).
$$
Each harmonic $X^{(m)}$ gives $n$ eigenvalues govern by
$$
[A + \omega^m A^\top + \omega^{-m}] z_m = \lambda z_m. \tag{*}
$$
We may introduce $B_m = \omega^{-m/2} A + \omega^{m/2} A^\top$ which for real matrices $A$ is hermitian.
$$
B_m z_m = \mu z_m, \quad \mu \in \mathbb R. \tag{**}
$$
Eigenvalues of (*) and (**) are related by
$$
\lambda = \omega^{-m} + \omega^{m/2} \mu.
$$
This is probably best we can do for the second question.
For the $A$ being upper shift matrix
we may proceed.
$$
B_m = \begin{pmatrix}
0 & \omega^{-m/2} \\
\omega^{m/2} & 0 & \omega^{-m/2} \\
&\ddots&\ddots&\ddots\\
&&\omega^{m/2} & 0 & \omega^{-m/2} \\
&&&\omega^{m/2} & 0
\end{pmatrix}
$$
Let's introduce $q = \omega^{m/2} = \exp \frac{\pi i m}{K}$. Then $\omega^{-m/2} = q^{-1} = \bar q$.
Again, rewriting the eigenproblem $B_m u = \mu u$ as a tridiagonal system of equations we get
$$
u_0 = 0\\
q u_{p-1} + \bar q u_{p+1} = \mu u_p, \qquad p = 1, \dots, n\\
u_{n+1} = 0.
$$
Plugging $u_p = e^{i \alpha p}$ as a general solution for the middle equations we get
$$
q e^{-i \alpha} + \bar q e^{i \alpha} = \mu \implies
\mu = 2 \cos (\alpha - \arg q) = 2 \cos \left(\alpha - \frac{m \pi}{K}\right)
$$
Note that sole $e^{i \alpha p}$ cannot satisfy the boundary conditions $u_0 = u_{n+1} = 0$. We might combine two $e^{i \alpha p} - e^{i \alpha' p}$ with different $\alpha$ provided that $\mu_\alpha = \mu_{\alpha'}$. Let's take
$$
\alpha - \frac{m \pi}{K} = -\alpha' + \frac{m \pi}{K} \implies
\alpha' = -\alpha + \frac{2 m \pi}{K}.
$$
Satisfying $u_{n+1} = 0$ gives an equation for $\alpha$
$$
0 = u_{n+1} = e^{i\alpha (n+1)} - e^{i \alpha' (n+1)} = e^{i \alpha' (n+1)} \left(
e^{i (\alpha - \alpha') (n+1)} - 1
\right).
$$
$$
\left(2\alpha - \frac{2m\pi}{K} \right) (n + 1) = 2\pi d, \qquad d = 1, \dots, n\\
\alpha = \frac{m \pi}{K} + \frac{\pi d}{n + 1}.
$$
This gives $n$ solutions for each of $K$ harmonics ($m = 0, \dots, K-1; d = 1,\dots,n$):
$$
\alpha_{m,d} = \frac{m \pi}{K} + \frac{\pi d}{n + 1}\\
\mu_{m,d} = 2\cos \left(\frac{\pi d}{n + 1}\right)\\
\lambda_{m,d} = \omega^{-m} + \omega^{m/2} \mu_{m,d}\\ 
(z_{m,d})_p = \exp \left(i \alpha_{m,d} p\right) - \omega^{mp}\exp \left(-i \alpha_{m,d} p\right)
$$
Here's a small verification in Python.
I can't hold myself from posting a plot of the eigenvalues for $K=16, n=24$. The eigenvalues are contained in a deltoid.

