Eigenvalues of a particular block circulant matrix I need to compute all the eigenvalues of the following block-circulant matrix for a research. Can anyone help me compute the eigenvalues of the following matrix?
$$\left[\begin{array}{l}2I&-I&0&0&0&...&0&0&-I\\-I&2I&-I&0&0&...&0&0&0\\0&-I&2I&-I&0&..&0&0&0\\.\\.\\.\\0&0&0&0&0&...&-I&2I&-I\\-I&0&0&0&0&...&0&-I&2I\end{array}\right]$$
In above, $I$ denotes the identity matrix of dimension $a$ and there are $r$ block-rows and block-columns, making the entire matrix have dimension $ar \times ar$. Any help will be greatly appreciated!
 A: This matrix can be written as the Kronecker product $M \otimes I_a$, where $M$ is the $r \times r$ circulant matrix
$$
M = \pmatrix{2&-1&0&\cdots&0&-1\\
-1&2&\ddots & \ddots & \vdots & 0\\
0 & \ddots & \ddots & \ddots & 0 & \vdots\\
\vdots &0&\ddots&\ddots&-1&0\\
0&\vdots&\ddots &-1 & 2 & -1\\
-1 & 0 &\cdots & 0& -1 & 2}.
$$
It follows that the eigenvalues of your matrix are simply the eigenvalues of $M$, each repeated with $a$-fold multiplicity.
The eigenvalues of the circulant matrix $M$ can be computed using the formula here to be
$$
\lambda_k = 2 - e^{2 \pi i k/r} - e^{-2 \pi i k/r} = 2(1 - \cos(2 \pi k/r)), \quad k = 0,1,\dots,r-1.
$$
A: The given matrix is the Kronecker product $C \otimes I$ of the circulant matrix
$$C=\left[\begin{array}{cccccccc}2&-1&0&0&0&...&0&0&-1\\-1&2&-1&0&0&...&0&0&0\\0&-1&2&-1&0&..&0&0&0\\.\\.\\.\\0&0&0&0&0&...&-1&2&-1\\-1&0&0&0&0&...&0&-1&2\end{array}\right]$$
with matrix $I$.
As such, its eigenvalues are all the possible products of the eigenvalues of $C$ which are known to be the Discrete Fourier Transform of the first line of $C$ (see here) and the eigenvalues of $I$, i.e., $1$ (multiple value).
In fact, in this case, the eigenvalues of $C$ can be given simple expressions.
