Applying DFT twice does not actually reverse an array. Instead, the first element stays in place while the rest of the array is reversed. Why?

Question

I've heard a million times that applying DFT twice will result in a reversed array, but that is not what actually happens. Instead, the first element remains where it was, and the rest of the elements are reversed. Is there an intuitive reason for that?

Octave code:

N = 16;
x = linspace(1, N, N);

fft(fft(x)) / N

Result:

1   16   15   14   13   12   11   10    9    8    7    6    5    4    3    2

Answer 1

The sequence is exactly what you should expect:

$$x[-n]=x[N-n]\tag{1}$$

Clearly, for $n=0$ $x[n]$ and $x[-n]$ have the same value.

It seems like you were expecting to see the sequence $x[N-1-n]$ instead of $x[N-n]$. If you wanted that sequence you would need to modulate the result of the first DFT:

N = 16;
x = 1:N;
c = exp(-1i*2*pi/N*(0:N-1));
x2 = real( fft( ( fft(x) .* c ) ) ) / N;    % real() just to remove rounding errors
x2 =

  16  15  14  13  12  11  10  9  8  7  6  5  4  3  2  1

Answer 2

Yes reversed (!) but not in the programming sense !

The sequence $N \cdot x[-n]$ which results after applying DFT twice to the N-point sequence $x[n]$ is a time-reversed (and amplitude scaled by $N$) sequence indicated by the minus sign in its argument.

Remembering from your math courses, a function with a negated argument such as $f(-t)$ means the function $f(t)$ is flipped about the (vertical) y-axis.

Then the seqence $x[-n]$ is also flipped about the y-axis, hence reversed. This reversal, however, is special in the sense that it's a circular reversion (a DFT sequence reversion) indicated by the modulus notation :

$$ x[-n] = x[ (-n)_N ] $$

And for the range $0 \le n < N$ , the modulus expands like :

$$ x[(-n)_N] = x[ N- n ] .$$

Note that you can avoid the modulus operator, and reach the same conclusion by simply interpreting the DFT sequence $x[n]$ to be a periodic sequence $\tilde{x}[n]$. Then $\tilde{x}[-n]$ will be the reversed sequence.

Answer 3

Using the duality property of the Fourier transform, you have that $$x[n] \overset{\mathcal F}{\longleftrightarrow}X[k]\implies X[n] \overset{\mathcal F}{\longleftrightarrow} \begin{cases}Nx[N - k] & \text{for} & k = 1, \ldots, N -1 \\Nx\left[(k)_N\right]&\text{for}&k = 0\end{cases}$$

You have then:

\begin{align} X[0] & = Nx[0]\\ X[1] & = Nx[N - 1]\\ X[2] & = Nx[N - 2]\\ \vdots &\qquad \vdots\\ X[N-1] & = Nx[1]\\ \end{align}

Which, to the factor $N$, is the sequence you have with $k = 0, \ldots, 15$.