Eigenvalues of a particular block circulant matrix

Question

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!

Answer 1

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

Answer 2

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.