Finding the eigenvalues of a $3N \times 3N$ block matrix

Question

I have a block matrix of size $3N \times 3N$ of the form

$$B = \begin{bmatrix} A & C & \ldots & C\\ C & A & \ldots & C\\ \vdots & \vdots & \ddots & \vdots\\ C & C & \ldots & A\\ \end{bmatrix}$$

where $A$ and $C$ are $3 \times 3$ matrices. Specifically, $C$ is given by

$$C = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & \gamma\\ \end{bmatrix}$$

I would like to find the eigenvalues of the matrix $B$. I have a paper that roughly states that the way to do this is as follows:

First, note that $B = I_N \otimes A + M_N \otimes C$ where $\otimes$ is the Kronecker product, $I_N$ is the $N \times N$ identity, and $M_N$ is the matrix

$$M_N = \begin{bmatrix} 0 & 1 & \ldots & 1 & 1\\ 1 & 0 & \ldots & 1 & 1\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & \dots & 0 & 1\\ 1 & 1 & \dots & 1 & 0\\ \end{bmatrix}$$

I understand this part. However, the argument proceeds as follows: Let the eigenvalues of $M_N$ be $\mu_1, \dots, \mu_N$. To find the eigenvalues $\lambda$ of $B$ we must use the characteristic equation $\det(B - \lambda) = 0$. Once again, I understand this.

However, I'm confused about the next bit of the argument. The paper states that we can diagonalize $M_N$ and that since this transformation does not affect the identity $I_N$, the characteristic equation for the determinant can be transformed into $N$ equations given by

$$\det(A + \mu_k C - \lambda) = 0, \qquad{} k = 1, \dots, N$$

I don't understand this final transformation, which involves diagonalizing $M_N$. Could someone explain this for me?

Answer 1

Let $P\in\operatorname{Mat}_N(K)$ be such that $PM_NP^{-1}=D$ where $D$ is the diagonal matrix with diagonal entries $\mu_1,\ldots,\mu_N$. Then $$ (I_3\otimes P)B(I_3\otimes P^{-1})=A\otimes PI_NP^{-1}+C\otimes PM_NP^{-1}=A\otimes I_N+C\otimes D, $$ which is block-diagonal with diagonal $3\times3$ blocks $A+\mu_kC$ for $k=1,\ldots,N$. The characteristic polynomial of this matrix, and of $B$, is then $\prod_{i=k}^N\det(X-(A+\mu_kC))$, whence the claim.

By the way, one can take $\mu_1=N-1$ and $\mu_k=-1$ for $1<k\leq N$, since $M_N+I_N$ is a rank-$1$ matrix, which therefore has characteristic polynomial $X^{N-1}(X-\operatorname{rk}(M_N+I_N))=X^{N-1}(X-N)$.