What is the general formula for stacked DFT on the same signal?

Question

Let us assume a finite, aperiodic signal $x[n]$ upon which we perform DFT n times, as such:

DFT{DFT{DFT{...{DFT{$x[n]$}}...}

How can we calculate this directly instead of applying the DFT n times?

Answer 1

Let $\text{DFT}_2 = \text{DFT}(\text{DFT}(...))$. Then,

$$ \begin{align} \text{DFT}_2(x[n]) &= N \cdot x[-n] \\ \text{DFT}_3(x[n]) &= N \cdot \text{DFT}(x[-n]) \\ \text{DFT}_4(x[n]) &= N^2 \cdot x[n] \end{align} $$ and thus

$$ \text{DFT}_M(x[n]) = N^{\lfloor M/2 \rfloor} \cdot \begin{cases} \sum_{n=0}^{N-1} x[n\cdot (-1)^{\lfloor M/2 \rfloor}] e^{-j2 \pi k n /N}, & M=\text{odd} \\\ x[n\cdot(-1)^{\lfloor M/2 \rfloor}], & M=\text{even} \end{cases} $$

Note that $\text{DFT}_4(x[n])/N^2 = x[n]$.

Testing

import numpy as np
from numpy.fft import fft


def dft(x):
    N = len(x)
    out = np.zeros(N, dtype='complex128')
    for k in range(N):
        for n in range(N):
            out[k] += x[n] * np.exp(-2j*np.pi * k * n / N)
    return out

def dft_M(x, M=1):
    N = len(x)
    sign = (-1)**(M//2)

    if sign == -1:
        x_flip = np.zeros(N, dtype=x.dtype)
        x_flip[0] = x[0]
        x_flip[1:] = x[1:][::-1]
        x = x_flip

    if M % 2 == 0:
        out = N**(M//2) * x
    else:
        out = N**(M//2) * dft(x)
    return out


for N in (128, 129):
    x = np.random.randn(N) + 1j*np.random.randn(N)
    assert np.allclose(fft(x), dft(x))

    assert np.allclose(fft(fft(x)), dft_M(x, 2))
    assert np.allclose(fft(fft(x)), dft_M(x, 2))
    assert np.allclose(fft(fft(fft(x))), dft_M(x, 3))
    assert np.allclose(fft(fft(fft(fft(x)))), dft_M(x, 4))