Suppose that we have a matrix M which consists of block matrices with the same dimensions.
\begin{equation} M=\begin{pmatrix} A&D&0&0\cdots&0&0\\ D&P^{-1}AP&D&0\cdots&0&0\\ 0&D&P^{-2}AP^2&D\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&0\cdots&D&P^{-n}AP^n \end{pmatrix} \end{equation}
Suppose that A is a matrix whose eigenproblem we have solved and D is a diagonal matrix with arbitrary constants. The P matrix is the prmutation matrix and its action on $A$ permutates its rows and columns. For example:
\begin{equation} A= \begin{pmatrix} c_{11}&c_{12}&c_{13}\\ c_{21}&c_{22}&c_{23}\\ c_{31}&c_{32}&c_{33} \end{pmatrix} \end{equation}
then
\begin{equation} P^-1AP=\begin{pmatrix} c_{33}&c_{31}&c_{32}\\ c_{13}&c_{11}&c_{12}\\ c_{23}&c_{21}&c_{22} \end{pmatrix} \end{equation}
and
$$ P^{-2}AP^2=\begin{pmatrix} c_{22}&c_{23}&c_{21} \\ c_{32}&c_{33}&c_{31} \\ c_{12}&c_{13}&c_{11} \end{pmatrix} $$
My question is this: "can we solve the eigenproblem of the $M$ matrix?"
A consideration of the case without a permutation matrix: the matrix $M$ can be written as the sum of Kronecker products $M = I \otimes A + J \otimes D$, where $I$ denotes an identity matrix (of size $n+1$) and $J$ denotes the (size $n+1$) square matrix $$ J = \pmatrix{0&1\\1&0&\ddots\\ &\ddots&\ddots&1\\&&1&0}. $$ Let $F$ denote a "DST-I matrix" (I'm not sure if this is standard terminology), whose columns are the orthonormal set of vectors $$ \vec v_j = C_j\left[\sin\left(\frac{\pi j(1)}{n+2} \right), \dots, \sin\left(\frac{\pi j(n+1)}{n+2} \right)\right], \quad j = 1,\dots,n+1 $$ for a suitable normalization constant $C_j$. We find that $F^TJF$ is diagonal with $$ D_J = \text{diag}\left(-2 \cos\left(\frac{\pi(1)}{n+2}\right), \dots, -2 \cos\left(\frac{\pi(n+1)}{n+2}\right)\right), $$ so that $M$ is (orthogonally) similar to the matrix $$ \begin{align*} (F \otimes I)^TM(F \otimes I) &= (F \otimes I)^T[I \otimes A + J \otimes D](F \otimes I) \\ & = (F^TIF) \otimes A + (F^TJF) \otimes D \\ & = I \otimes A + D_J \otimes D, \end{align*} $$ which is block diagonal of the form $$ I \otimes A + D_J \otimes D = \text{diag}\left(A - 2 \cos\left(\frac{\pi(1)}{n+2}\right)D, \dots,A -2 \cos\left(\frac{\pi(n+1)}{n+2}\right)D\right). $$ Thus, the problem of finding the eigenvalues of $A$ is reduced to that of finding the eigenvalues of $A + \lambda_j D$ for $j = 1,\dots,n+1$, where $\lambda_j = - 2 \cos\left(\frac{\pi j}{n+2}\right)$.
There is no closed form for these eigenvalues in terms of the eigenvalues of $A$ and $D$.