Orthogonal Functions and Transforms
The DFT matrix is symmetric and unitary:
i.e., the rows/columns are mutually orthogonal
A number of transforms such as the Fourier, Walsh, Hadamard, and Discrete Cosine may be expressed as F = A f A.
The transform matrices may be decomposed into products of matrices with fewer nonzero elements, reducing redundancy and computational requirements.
The DFT matrix may be factored into a product of 2 ln N sparse and diagonal matrices, which may be considered to be the basis of the FFT algorithm.