Can we say anything about the eigenvalues/eigenvectors of a matrix composed by submatrices in a 'circulant' way? Circulant matrices, that is matrices in $\mathbb{R}^{n \times n}$ of the form
$$\begin{pmatrix} c_0 & c_1 & c_2 & ... & c_n \\ c_n & c_0 & c_1 &... & c_{n-1} \\
c_{n-1} & c_n & c_0 &... & c_{n-2} \\ ...
& ... &... &... &... \end{pmatrix}$$
have a particularly easy eigenvalue/eigenvector structure - in particular, the eigenvectors are of the form $(\omega^0,\omega^{1},...,\omega^{n-1})$ for $\omega \in \mathbb{C}$ a $n-th$ root of unity.
I was wondering if we still can gain some insight into the spectrum/eigenvectors, if we relax the circulant condition to only hold for submatrices?
That is, if we have a matrix of the form
$$ C = \begin{pmatrix} C_0 & C_1 & C_2 & ... & C_m \\ C_m & C_0 & C_1 &... & C_{m-1} \\
C_{m-1} & C_m & C_0 &... & C_{m-2} \\ ...
& ... &... &... &... \end{pmatrix}$$
where $C_i \in \mathbb{R}^{k \times k}$ are square matrices (and $k$ divides $n$),
what are eigenvectors/values of $C$ and how do they relate to the $C_i$?
The only trivial thing that one could immediately see is the case where $v \in \mathbb{R}^{k}$ is an eigenvector of all the $C_i$. Then of course also
$(v,v,v,...,v)$ is an eigenvector of $C$ with eigenvalue $\sum_i \lambda_i$, where $v$ is an eigenvector of $C_i$ for eigenvalue $\lambda_i$.
But this is of course not a very interesting special case.
It would also be interesting to have some result under some additional assumptions, e.g. symmetry of $C$.
 A: Let $\omega$ be an $n$th root of unity. Suppose we have the block circulant matrix
$$C = \begin{pmatrix} C_0 & C_1 & \cdots & C_{n-2} & C_{n-1} \\ C_{n-1} & C_0 & \cdots & C_{n-3} & C_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ C_{1} & C_2 & \cdots & C_{n-1} & C_{0} \end{pmatrix}$$
Consider the matrix
$$D_\omega := C_0+\omega C_1 + \omega^2 C_2 + \cdots + \omega^{n-1} C_{n-1}$$
and suppose that $(\lambda, \vec v)$ is an eigenvalue-eigenvector pair for $D_\omega$. Then define
$$\vec x_{\omega, \vec v} = \begin{pmatrix} \vec v \\ \omega \vec v \\ \omega^2 \vec v \\ \vdots \\ \omega^{n-1} \vec v \end{pmatrix}$$
Observe that
\begin{align*}
C \vec x_{\omega, \vec v} &= \begin{pmatrix} C_0 & C_1 & \cdots & C_{n-2} & C_{n-1} \\ C_{n-1} & C_0 & \cdots & C_{n-3} & C_{n-2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ C_{1} & C_2 & \cdots & C_{n-1} & C_{0} \end{pmatrix} \begin{pmatrix} \vec v \\ \omega \vec v \\ \omega^2 \vec v \\ \vdots \\ \omega^{n-1} \vec v \end{pmatrix} \\
&= \begin{pmatrix} C_0 \vec v + C_1 \omega \vec v + \cdots + C_{n-1} \omega^{n-1} \vec v \\ C_{n-1} \vec v + C_0 \omega \vec v + \cdots + C_{n-2} \omega^{n-1} \vec v \\ \vdots \\ C_1 \vec v + C_2 \omega \vec v + \cdots + C_{0} \omega^{n-1} \vec v \end{pmatrix} \\
&= \begin{pmatrix} (C_0 + \omega C_1 + \omega^2 C_2 + \cdots + \omega^{n-1} C_{n-1}) \vec v \\ \omega (C_0 + \omega C_1 + \omega^2 C_2 + \cdots + \omega^{n-1} C_{n-1}) \vec v \\ \omega^2 (C_0 + \omega C_1 + \omega^2 C_2 + \cdots + \omega^{n-1} C_{n-1}) \vec v \\ \vdots \\ \omega^{n-1} (C_0 + \omega C_1 + \omega^2 C_2 + \cdots + \omega^{n-1} C_{n-1}) \vec v\end{pmatrix} \\
&= \begin{pmatrix} D_\omega \vec v \\ \omega D_\omega \vec v \\ \omega^2 D_\omega \vec v \\ \vdots \\ \omega^{n-1} D_\omega \vec v \end{pmatrix} = \begin{pmatrix} \lambda \vec v \\ \omega \lambda \vec v \\ \omega^2 \lambda \vec v \\ \vdots \\ \omega^{n-1}\lambda \vec v \end{pmatrix} = \lambda \begin{pmatrix} \vec v \\ \omega \vec v \\ \omega^2 \vec v \\ \vdots \\ \omega^{n-1}\vec v \end{pmatrix} \\
&= \lambda \vec x_{\omega, \vec v}
\end{align*}
We see that $(\lambda, \vec x_{\omega, \vec v})$ is an eigenvalue-eigenvector pair for $C$ (note that the same calculation goes through for generalized eigenvectors). I suspect, but haven't actually proven, that
$$\det C = \prod_{\omega^n = 1} \det(D_\omega)$$
(with $C$ and $D_\omega$ as defined above) even when the matrices $C_i$ don't commute. This would imply that all of the (generalized) eigenvalues of $C$ are (generalized) eigenvalues of some $D_\omega$, giving a pretty complete answer to your question.
Note that this is in the same spirit as the scalar circulant matrix case. Viewing the scalars $c_i$ as $1 \times 1$ matrices, they all have the $1$-dimensional eigenvector $(1)$, as do the $1 \times 1$ matrices $D_\omega$. The eigenvectors that you mention in the scalar case are then just $\vec x_{\omega, (1)}$.
