Matrix Interpretation of the FFT Algorithm

The fast Fourier transform (FFT) algorithm can be interpreted as factoring the DFT matrix into a product of log_2(N) + 1 simple matrices consisting of one permutation matrix that represents the bit reversal stage (power of 2 decimation in time algorithm) and log_2(N) matrices representing the butterflies. Each butterfly matrix has only N nonunity or nonzero elements and can be implemented with N complex multiplications.