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

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?

• You said C is $3\times 3$ but wrote as if it is $4\times 3$. Commented Oct 30, 2013 at 14:21
• Thanks! I've corrected that now Commented Oct 30, 2013 at 14:30
• The paper has a minor error: $B$ should be $I_N\otimes A+M_N\otimes C$, not $A\otimes I_N+C\otimes M_N$. Commented Oct 30, 2013 at 19:24

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