2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for the help! I don't know circulant matrix or the discrete Fourier transform matrix, but it seems useful! I will look into them! $\endgroup$ – user3138073 Feb 14 '18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.