eigenvectors of a circulant block matrix I am looking to find eigenvectors of circulant block matrices. I have a matrix given by:
$$
M= \begin{pmatrix}Z& A\\   
         B & Z
\end{pmatrix}
$$
where $Z$ is an $n\times n$ zero matrix, with all entries zero; and $A$ and $B$ are square circulant matrices. This can also be extended to more than two zero matrices as follows:
$$
M^\prime= \begin{pmatrix}Z& M & N\\   
         P& Z& O\\
         L &K& Z
\end{pmatrix}
$$
Is there an analytical eigenvector and eigenvalue for these kind of matrices?
What about if $M$ or $M^\prime$ are symmetric?
Thank you,
 A: I assume that you are working over the complex numbers. Let $v_j = \frac{1}{\sqrt{n}}(1, \omega_j, \ldots, \omega_j^{n-1})^T$ for $1 \leq j \leq n$ where $\omega_j = e^{\frac{2\pi i j}{n}}$. The vectors $v_j$ form a basis of $\mathbb{C}^n$ and are eigenvectors of all circulant matrices. If build a matrix $U$ whose columns are the vectors $v_j$, then $U$ will be invertible and $U^{-1} C U$ will be a diagonal matrix whenever $C$ is a circulant matrix.
Write $Av_j = \lambda_j v_j$ and $B v_j = \mu_j v_j$. Then
$$ \begin{pmatrix} U^{-1} & 0 \\ 0 & U^{-1} \end{pmatrix}\begin{pmatrix} 0 & A \\ B & 0 \end{pmatrix} \begin{pmatrix} U & 0 \\ 0 & U \end{pmatrix} = \begin{pmatrix} 0 & U^{-1} A U \\ U^{-1} B U & 0 \end{pmatrix} = \begin{pmatrix} 0 & \mathrm{diag}(\lambda_1, \ldots, \lambda_n) \\ \mathrm{diag}(\mu_1, \ldots, \mu_n) & 0 \end{pmatrix} = D $$
which shows that $M'$ is similar to $D$. For the matrix $D$ we can find the eigenvalues and eigenvectors explicitly. Note that we have
$$ De_i = \begin{cases} \mu_i e_{n+i} & 1 \leq i \leq n, \\
                        \lambda_{i-n} e_{i - n} & n + 1 \leq i \leq 2n. \end{cases} $$
and so each $\mathrm{span} \{ e_i, e_{n+i} \}$ (for $1 \leq i \leq n$) is a two-dimensional invariant subspace of $D$. Conjugating $D$ by a change of basis matrix, we see that $D$ is similar to the block diagonal matrix
$$ \begin{pmatrix} \begin{pmatrix} 0 & \lambda_1 \\ \mu_1 & 0 \end{pmatrix} & \cdots & 0 \\ \vdots & \ddots & \vdots  \\ 0 & \cdots & \begin{pmatrix}  0 & \lambda_n \\ \mu_n & 0 \end{pmatrix} \end{pmatrix} $$
whose eigenvalues are $\pm \sqrt{\lambda_i \mu_i}$ and whose eigenvectors can be found explicitly (I leave that to you). Note that $M'$ is not necessarily diagonalizable which can be seen by taking $1 \times 1$ blocks and considering
$$ M' = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}. $$
In fact, $M'$ will be diagonalizable if and only if $\lambda_i \mu_i \neq 0$ for all $1 \leq i \leq n$. 
Regarding the generalization, I doubt you'll be able to say something nice. Even the case where the blocks are $1 \times 1$ is unpleasant and requires you to analyze the possible eigenvalues and eigenvectors of all $3 \times 3$ matrices having zeros on the diagonal.
