3
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

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

$\endgroup$

Your Answer

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

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