# Representation of Fourier Transform's vectors

I am just learning FFTs and I am trying to debug a problem in MATLAB.

I think I don't understand how is MATLAB's FFT function handling the polynomial powers, or I am doing something wrong manually. My problem is that it seems that positions 1 .. n-1 are reversed.

OK, here is a very simple example: p(x) = x and I would like to compute the 4th order FFT

On paper it would be:

w0 = 1; w1 = i; w2 = -1; w3 = -i;
p(w0) = 1; p(w1) = i; p(w2) = -1; p(w3) = -i;


and for me it would mean the following in vector form:

p = [0,1,0,0]
fft(p) = [1,i,-1,-i]


But what happens is this:

fft(p)

ans =

1.0000                  0 - 1.0000i  -1.0000                  0 + 1.0000i


It means that somehow MATLAB is looking at the roots of unity in a 0,3,2,1 order. Why is this happening or is it me who is doing something wrong?

Update

I'm even more confused now that I tried it in Maple and Wolfram Alpha.

In Maple it returns:

v:=Vector[row]([ 0 , 1 , 0 , 0 ], datatype=complex[8]);
FourierTransform(v);
Vector[row](4, {(1) = .500000000000000+0.*I, (2) = 0.-.5000000000*I, (3) = -.500000000000000+0.*I, (4) = 0.+.500000000000000*I})


In Wolfram Alpha it is:

fft([0,1,0,0])
returns:
{0.5, 0.5 i, -0.5, -0.5 i}


So to sum up, here is how it looks totally different by using 4 different methods:

polynomial: x^2 or [0,1,0,0]
FFT on paper: [1, i, -1, -i]
in MATLAB: [1, -i, -1, i]
in Maple: [0.5, -0.5i, -0.5, 0.5i]
in Wolfram Alpha: [0.5, 0.5i, -0.5, -0.5i]

-
Have you compared your working definition (normalization and all that) of the FFT with the definition of whatever software you're using? – J. M. Oct 17 '11 at 10:35
Your "FFT on paper" is a bit suspect in that the more common formulation of the discrete Fourier Transform in engineering circles (which MATLAB caters to) gives the values of $f(x)$ at $\exp(-i 2\pi k/N)$ for $0 \leq k < N$. Your evaluation is at $\exp(+i 2\pi k/N)$ and so you get the complex conjugate of what MATLAB is giving you. The inverse discrete Fourier Transform has a factor of $1/N$, but, as J.M. has already noted, the normalization also can be different in different formulations. Maple and Wolfram Alpha probably use $1/\sqrt{N}$ in both directions instead of $1/N$ in one. – Dilip Sarwate Oct 17 '11 at 11:02
@Dilip: I know for a fact that Mathematica (and thus Wolfram Alpha) does use the $\frac1{\sqrt N}$ normalization; at least for Mathematica, you have the FourierParameters option to tweak if the default convention isn't to your liking... – J. M. Oct 17 '11 at 11:26
The short answer to this question: "FFT implementations vary." – endolith Oct 17 '11 at 13:22

$$\hat a_k=n_1\sum_{n=0}^{N-1}a_n\mathrm e^{-\sigma2\pi\mathrm i kn/N}$$
$$a_n=n_2\sum_{k=0}^{N-1}\hat a_k\mathrm e^{\sigma2\pi\mathrm i kn/N}$$
with $\sigma=\pm1$ and $n_1n_2=1/N$. Usual choices are to distribute the normalization symmetrically, that is $n_1=n_2=1/\sqrt N$, or to put it all into one of the transforms so that the other one doesn't require normalization. See also the last few paragraphs in this Wikipedia section for pros and cons of the different conventions.