From Wikipedia I saw that there is a symmetry of the Fourier transformation
$F(F(f))(x) = f(-x)$
This matches the graphical explanation of the (German) Youtube video (9:15 to 9:45).
I tried to see that symmetry in various tools, but somehow it does not match my expected result.
My input: [1, 0, 0, 0]
Expected output: [0, 0, 0, 1]
The example fft(fft([1,0,0,0]) in Wolfram Alpha produces [1, 0, 0, 0] as output.
The wxMaxima script
load(fft);
Input:[1,0,0,0];
Once: fft(Input);
Twice: fft(Once);
results in [0.25, 0, 0, 0].
So now I am confused twice:
- why do Wolfram and Maxima produce different output?
- where is the symmetry? Is it because of the optimization of FFT, so I should use DFT to get better results?
Your expected output is wrong. For the purpose of the Fourier transform, the array is
0-indexed. In terms of Fourier transform on finite groups, the first element is the value for the function evaluated on the identity element. In any case, $-0 = 0$. So you should expect that the double Fourier transform of $$ [a,b,c,d] $$ to be $$ [a, d, c, b] $$Therefore Wolfram does it as expected.
There are two main ways of normalizing the Fourier transform (on finite groups). The first method (as assumed by Wikipedia and Wolfram), takes $$ \hat{f}(s) = \langle f(x), \chi_s(x) \rangle $$ where $\chi_s$ is the corresponding irreducible character (basically $e^{isx}$). Then the inverse transform is given by $$ f(x) = \frac{1}{|G|} \langle \hat{f}(s), \bar{\chi}_s(x)\rangle $$ where $|G|$ is the size of the group (the number of elements).
The other method is to make the two formulae more symmetrical by definiting the forward transform as $$ \hat{f}(s) = \frac{1}{\sqrt{|G|}} \langle f(x), \chi_s(x)\rangle $$ and now the inverse transform will also have just the square-root factor. Evidently Maxima chooses this latter normalisation which means that in its implementation $$ \mathcal{F}(\mathcal{F}(f))(x) = \left(\frac{1}{\sqrt{|G|}}\right)^2 f(-x) $$ which accounts for the difference of a factor of 4 (your group is of size 4).