Recently encountered the following matrix:
$$A = \begin{pmatrix} 0^{2 \times (N-2)} & D^{2 \times 2} \\ D^{(N-2) \times (N-2)} & 0^{(N-2) \times 2} \end{pmatrix}$$
where $0^{(k \times l)}$ is the matrix of all zeros of the corresponding size, and $D^{(k \times l)}$ is diagonal. So, it consists only of two non-trivial diagonal blocks, however, they are not on the diagonal. Is there any simple way to diagonalize that?
What I also know is that $A^{m}$ is diagonal, where $m=N$ if $N$ is odd, and $m=N/2$ if $N$ is even. I believe that there is an analytical formula for that as I ran some symbolic tests.
I assume that $A$ is complex and nonsingular. If so, it is always diagonalisable over $\mathbb C$. Let all matrices below be zero-indexed. Let $$ C=\begin{bmatrix}0&1\\ &\ddots&\ddots\\ &&\ddots&1\\ 1&&&0\end{bmatrix}. $$ Then $A$ is in the form of $\operatorname{diag}(\mathbf a)\,C^{N-2}$ for some vector $\mathbf a=(a_0,a_1,\ldots,a_{N-1})^\top\in\mathbb C^N$.
When $N$ is odd, let $J$ be the index vector $(0,N-2,N-4,\ldots,1,N-1,N-3,\ldots,2)$ and $P=I(\,:\,,J)$ be the permutation matrix such that $p_{i,K(i)}=1$ for each $i$ and $p_{ij}=0$ elsewhere. Let also $\mathbf b=\mathbf a(J)=P^\top\mathbf a$. Then $$ P^TAP=A(J,J)=\operatorname{diag}(\mathbf b)C.\tag{1} $$ When $N=2m$ is even, let $J_1=(0,N-2,N-4,\ldots,2),\,J_2=(1,N-1,N-3,\ldots,3)$ and $J=(J_1,J_2)$ be the concatenation of $J_1$ and $J_2$. Let $P=I(\,:\,,J),\,\mathbf b_1=\mathbf a(J_1),\,\mathbf b_2=\mathbf a(J_2)$ and $\mathbf b=\begin{bmatrix}\mathbf b_1\\ \mathbf b_2\end{bmatrix}=\mathbf a(J)=P^\top\mathbf a$. Then $$ P^TAP=A(J,J) =\begin{bmatrix} \operatorname{diag}(\mathbf b_1)C\\ &\operatorname{diag}(\mathbf b_2)C \end{bmatrix}. $$ So, in either case, the problem reduces to finding an eigen-decomposition of a nonsingular matrix in the form of $\operatorname{diag}(\mathbf b)C$. Let $k$ be any $N$-th root of $b_0b_1\cdots b_{N-1}$. Define $D=\operatorname{diag}(d_0,d_1,\ldots,d_{N-1})$ where $$ d_i=\frac{b_ib_{i+1}\cdots b_{N-1}}{k^{N-i}};\quad 0\le i<N. $$ Then $\operatorname{diag}(\mathbf b)C=kDCD^{-1}$. However, it is well-known that the circulant matrix $C$ has a unitary diagonalisation $U\Lambda U^\ast$ where \begin{aligned} \Lambda&=\operatorname{diag}(1,\omega,\omega^2,\ldots,\omega^{N-1}),\\ u_{ij}&=\frac{1}{\sqrt{N}}\omega^{ij} \text{ for each $i,j\in\{0,1,\ldots,N-1\}$},\\ \omega&=\exp\left(\frac{2\pi\mathbf i}{N}\right) \text{ (with $\mathbf i=\sqrt{-1}$)}. \end{aligned} It follows that $(DU)(k\Lambda)(DU)^{-1}$ is an eigen-decomposition of $\operatorname{diag}(\mathbf b)C=kDCD^{-1}$.
So, when $N$ is odd, $A=(PDU)(k\Lambda)(PDU)^{-1}$ is an eigen-decomposition.
When $N$ is even, if $(D_1U)(k_1\Lambda)(D_1U)^{-1}$ and $(D_2U)(k_2\Lambda)(D_2U)^{-1}$ are respectively eigen-decompositions of $\operatorname{diag}(\mathbf b_1)C$ and $\operatorname{diag}(\mathbf b_2)C$, then $$ \left(P\begin{bmatrix}D_1U\\ &D_2U\end{bmatrix}\right) \begin{bmatrix}k_1\Lambda_1\\ &k_2\Lambda_2\end{bmatrix} \left(P\begin{bmatrix}D_1U\\ &D_2U\end{bmatrix}\right)^{-1} $$ is an eigen-decomposition of $A$.