I know that the eigenvalues for 4 point DFT matrix can be found from $F_4^4=I$. Is this also valid for 8, 16 and higher orders? For example with 8 points, will it be $F_8^8=I$ ? If not, how can I can compute them?
$\begingroup$ $\endgroup$
0 
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
The eigenvalues belong to the same set of quartic roots of unity verifying $\lambda^4=1$, whatever the order of the DFT. Indeed, this is a consequence of Fourier conjugation (adapted from Fourier transform):
$$\left(f(x)\right)^* \stackrel{\mathcal{F}}{\Longleftrightarrow} \left(\widehat{f}(-\xi)\right)^*\,.$$
Denoting $\mathcal{P}$ the parity operator such that $(\mathcal{P} f)(x) = f(-x)$, then:
$$\begin{align} \mathcal{F}^0 &= \mathrm{id}, \\ \mathcal{F}^1 &= \mathcal{F}, \\ \mathcal{F}^2 &= \mathcal{P}, \\ \mathcal{F}^3 &= \mathcal{F}^{-1} = \mathcal{P} \circ \mathcal{F} = \mathcal{F} \circ \mathcal{P}, \\ \mathcal{F}^4 &= \mathrm{id} \end{align}$$
These propositions are valid only under suitable conditions on $f$ (existence, uniqueness, etc.). However, the situation is simpler for the DFT, and its associated matrices. As a side note, remember that an involutory matrix is its own inverse: $\mathcal{A}^2 = \mathrm{id}$ (like reflections, Pauli matrices); the property for the DFT matrix is a kind on high-order (fourth order) version.
For more details on their multiplicity, you can read: Eigenvectors and Functions of the Discrete Fourier Transform, 1982, Dickinson and Steiglitz (online).