# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 3 Inverse DFT  
The IDFT (inverse DFT) computation follows a similar development. The IDFT has the same unique eigenvalues as the DFT, only they differ in the eigenvalue multiplicity for eigenvalues \(j\) and \(-j\). Due to the conjugation difference in the DFT and the IDFT, the multiplicities of these eigenvalues are exchanged. Consequently, the eigenvalue multiplicities of the IDFT are  
\[m_{1} =\left\lfloor\frac{N}{4}\right\rfloor+1 m_{j} =\left\lfloor\frac{N+1}{4}\right\rfloor \tag{17}\] \[m_{-1} =\left\lfloor\frac{N+2}{4}\right\rfloor m_{-j} =\left\lfloor\frac{N-1}{4}\right\rfloor\]  
Similarly, the eigenvectors are unchanged from the DFT for the eigenvalues \(1\) and \(-1\), but they are exchanged for eigenvalues \(j\) and \(-j\). Thus, the eigenvector matrix for the IDFT \(V_{\text{IDFT}}\) can be obtained directly from the DFT eigenvector matrix \(V\).  
Figure 1: A block diagram showing the signal flow for our proposed DFT algorithm. Here \(\tilde{X}_{i}\) is the \((i+1)^{\text{th}}\) diagonal entry of \(\tilde{X}\). The scaler block multiplies the eigenvectors by the filter output (producing \(V\tilde{X}\)) while the combiner block multiplies the scaled result with \(u\)(producing the real and imaginary components of \(X\)).  
Using \(V_{\text{IDFT}}\), the steps described in Section 2 can be used to compute the IDFT. The block diagram of the IDFT follows directly from these definitions used to replace the DFT computations used to derive Figure 1. As in the case for the DFT, symmetries found in the input sequence can be used to improve the computational efficiency. Moreover, if the input or the output sequence is known to be real valued, the computational efficiency can be improved further. If the input to the IDFT is real, the procedure is similar to the DFT with real inputs.  
However, if the output of the IDFT is known to be real, the input will be complex and will have some symmetries which can be exploited to improve computational performance. Let \(x=\text{IDFT}(X)\), where \(X=X_{r}+X_{i}\) such that \(X_{r}=\text{real}(X)\) and \(X_{i}=\text{imag}(X)\). If \(x\) is real, \(X_{r}\) will be even symmetric and \(X_{i}\) will be odd symmetric (ch. 5 [10]). It is also known that the DFT eigenvectors are either even symmetric (for eigenvalues \(\pm 1\)) or odd symmetric (for eigenvalues \(\pm j\)) [8]. These eigenvector symmetries are further explored in Section 7. Let \(v_{ev}\) represent an even symmetric eigenvector for eigenvalues \(\pm 1\) and \(v_{od}\) denote an odd symmetric eigenvector for eigenvalues \(\pm j\). It is well understood that the product (Hadamard product) of two even sequences or two odd sequences will be even, and the product of an even and an odd sequence will be odd. We also know that the sum of the elements of an even sequence will be twice the sum of the first half of the sequence and the sum of the elements of an odd sequence will be zero. Combining this information for the calculation of the inner products for \(\widehat{X}_{r}\) and \(\widehat{X}_{i}\) in (10), we get \(\langle X_{r},v_{od}\rangle=\langle X_{i},v_{ev}\rangle=0\) and \(\langle X_{r},v_{ev}\rangle\), \(\langle X_{i},v_{od}\rangle\) require approximately \(N/2\) multiplications each. Therefore, the last \(N-m^{\prime}\) diagonal entries of \(\widehat{X}_{r}\) and the first \(m^{\prime}\) diagonal elements of \(\widehat{X}_{i}\) will be 0 where \(m^{\prime}=m_{1}+m_{-1}\). Thus, both the terms of (10) will be purely real. Similarly, for (14), \(Y^{\prime}=Y\) since \(Y_{2}=0\) again leading to a reduction in the number of operations. Comparable patterns also exist for (11) and (15).