Let $F=\frac{1}{\sqrt{n}}(w^{kl})_{k,l=0}^{n-1}$ be the discrete Fourier matrix of size $n$ where $w=\exp^{-\frac{2\pi i}{n}}$.

It is a well-known that $F_n^4 = I_n$ where $I_n$ represents the identity matrix of dimension $n$. This leads to the conclusion that $F$ possess precisely four eigenvalues, namely $\{\pm1,\pm i\}$, when $n\geq4$. Let $E_{\lambda}$ be the linear space consisting of all eigenvectors of $F$ corresponding to the eigenvalue $\lambda$.

Let $P_{\lambda}$ be the projection onto $E_{\lambda}$. We can construct four polynomials with roots at precisely three of the eigenvalues such that the remaining eigenvalue is passed through:





$P_a P_b = \delta_{a,b}$, so $P_{\lambda}$s are mutually orthogonal and $\sum P_{\lambda}=I$. Therefore, any signal $x$ is decomposed into four orthogonal components


If $y =P_{\lambda}x$, then $Fy=\lambda y$ is a direct consequence.

Q. What potential applications and advantages can be derived from this decomposition?

  • 1
    $\begingroup$ Have you tried to identify the four subspaces and describe them in simpler terms? If you have done that, I'll be happy to tell you about the applications for improving the performance of fast discrete Fourier transforms under certain circumstances. $\endgroup$
    – Jazzmaniac
    Commented Feb 15 at 11:48
  • $\begingroup$ I just spotted this now: Your assertion that $F^4=1$ only holds for unitary scaling, which you have not used in your definition of the DFT. And while you're at it, you might want to change $n$ to $N$ for sake of convention and readability. $\endgroup$
    – Jazzmaniac
    Commented Feb 15 at 20:42
  • $\begingroup$ And if you have trouble identifying the Eigen-subspaces in simpler terms then let me know and I can give you a hand. $\endgroup$
    – Jazzmaniac
    Commented Feb 15 at 20:43
  • $\begingroup$ are you not interested in this question anymore? $\endgroup$
    – Jazzmaniac
    Commented Feb 17 at 11:12
  • $\begingroup$ As you know $F^2=1\oplus J$ where $J$ is just the anti-diagonal matrix of size $n-1$. It makes all these projections describe in a simpler case. $\endgroup$
    – ABB
    Commented Feb 17 at 15:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.