Matrix recursive expressions of the DFT of even and odd complex sequences

The discrete Fourier transform of even complex sequences involves, in matrix formulation, a cosine matrix and, in the same way, the discrete Fourier transform of odd complex sequences is related with a sine matrix. Using structural characteristics of the two matrices, whose order is half the length of the symmetric input data, some recursive expressions of them will be constructed. Unlike the previous classical forms of the discrete Fourier transform of an even or odd real vector, the recursive terms in the matrix expressions derived here only involve the same cosine and sine matrices, with halved order. That is, it is shown that, as for the FFT of a general complex sequence, a divide and conquer approach can also be used to compute the DFT of even or odd sequences. The recursion is closed in the family of the sine and cosine matrices used to describe the DFT of even and odd sequences and no other kind of sine or cosine based matrices are required in recursive terms. Although the obtained results give a new theoretical view on the problem of computing the DFT of even and odd complex sequences, these are not of immediate practical use since the computational cost is higher than other currently employed algorithms. Copyright © 2005 John Wiley & Sons, Ltd.