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$.
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)}$.