eigen-decomposition (largest eigenvalue) of a block matrix

Question

Let $E = \left[\begin{array}{ccccc} I_d & -I_d & 0& \dots & 0\\ 0& I_d & -I_d &\dots& 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & I_d & -I_d\\ -I_d & 0 & 0 & \dots & I_d \end{array}\right] \in \mathbb{R}^{Nd \times Nd}$ be a block matrix, where $I_d$ is a $d$-dimensional identity matrix. And $M = E^\top E = \left[\begin{array}{ccccc} 2I_d & -I_d & 0& \dots & -I_d\\ -I_d& 2I_d & -I_d &\dots& 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 2I_d & -I_d\\ -I_d & 0 & 0 & \dots & 2I_d \end{array}\right] \in \mathbb{S}^{Nd \times Nd}$.

I was wondering what is the eigen-decomposition (or at least the largest eigenvalue) of $M$? I did some simulation and it seems that $\lambda_{\max} = N$. But I don't know if there is any formulation for this specific eigen-decomposition?

Thank you!

Answer 1

You should be able to explicitly compute the eigen-decomposition in view of the following facts:

1. If $$ C_n= \begin{bmatrix} e_n & e_1 & \cdots & e_{n-1} \end{bmatrix}$$ denotes the basic circulant matrix, then $$C_n = F_n\text{diag}(1,\omega,\dots,\omega^{n-1})F_n^*,$$ in which $\omega := \exp(2\pi i/n)$, $e_i$ denotes the $i^\text{th}$ column of the $n$-by-$n$ identity matrix, and $F_n$ denotes the discrete Fourier transform matrix of order $n$.

2. The eigen-decomposition of $I_n - C_n$ is $$F_n\text{diag}(0,1-\omega,\dots,1-\omega^{n-1})F_n^*,$$ in which $I_n$ denotes the $n$-by-$n$ identity matrix.

3. Notice that $E = (I_N-C)\otimes I_d = I_N \otimes I_d - C \otimes I_d = I_{Nd} - C \otimes I_d$, in which $\otimes$ denotes the Kronecker product.