Eigenvalues of a symmetric matrix that every block is circulant

Question

For a matrix like \begin{bmatrix} A & B \\ B & A \\ \end{bmatrix} which A and B are block matrix and are circulant, is there any simple way to find eigenvalues and eigenvectors? To be clear, following matrix is an example of my described matrix. \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \end{bmatrix}

Answer 1

Your matrix commutes with the matrices $$P_2 = P \oplus P$$ and $$X = \begin{pmatrix} 0 & I \\ I& 0\end{pmatrix}$$ where $P$ is the cyclic permutation matrix on one subblock. Moreover, also $P_2$ and $X$ commute. Thus the three matrices can be simultaneously diagonalized. The combined eigenspaces of $P_2$ and $X$ have the form $$E_{\lambda,\pm} = \mathop{\rm span}\begin{pmatrix}v_\lambda \\ \pm v_\lambda \end{pmatrix}$$ with the eigenvalues $\lambda_j =e^{2\pi i j/n}$ and $$v_\lambda =(1,\lambda, \lambda^2, ...)^t.$$

As the eigenspaces are 1 dimensional, the eigenvectors of your matrix are given by $$\begin{pmatrix}v_{\lambda_j} \\ \pm v_{\lambda_j} \end{pmatrix}$$ and the eigenvalues are easily found.

In particular, the unitary transformation $$U=\frac{1}{\sqrt{2}} \begin{pmatrix} U_\text{DFT} & U_\text{DFT} \\ U_\text{DFT} & -U_\text{DFT}\end{pmatrix}$$ with $U_\text{DFT}$ the discrete Fourier transform brings your matrix onto diagonal form.