# A Sparse Algorithm for Computing the DFT Using Its Real Eigenvectors
## 2 Methodology  
A Fourier transform matrix \(F\) is diagonalizable and can be decomposed into its Jordan form \(F=V\Lambda V^{-1}\) where \(V\) is a matrix whose columns are the eigenvectors of \(F\) and \(\Lambda\) is a purely diagonal matrix containing the eigenvalues of \(F\). Since \(F\) is unitary, the eigenvalues in \(\Lambda\) have magnitude one and the eigenvector matrix \(V\) is also unitary. What may be less well-known is that it is possible find a real and orthonormal set of eigenvectors for \(F\)[7]. We use \(V^{\rm H}\) as the complex conjugate transpose of \(V\) and \(V^{\rm T}\) as the transpose of \(V\). However, since \(V\) is real, \(V^{\rm H}\) is the transpose of \(V\), i.e., \(V^{\rm H}=V^{\rm T}\). Of course, since \(V\) is unitary, \(V^{-1}=V^{\rm H}=V^{\rm T}\). So, we have the more useful Jordan form  
\[F=V\Lambda V^{\rm T} \tag{3}\]  
**Definition 1**. : _The function \(\text{diag}(\cdot)\) converts a vector to a diagonal matrix._  
Let \(e_{i}\) be a Euclidean basis vector where the \(i^{\text{th}}\) element is \(1\) and all other elements are zero. Thus, \(e_{0}=\left[ \begin{array}{ccccc}1&0&\cdots&0\end{array} \right]^{\mathsf{T}}\), \(e_{1}=\left[ \begin{array}{ccccc}0&1&0&\cdots&0\end{array} \right]^{\mathsf{T}}\) and so on. If \(a=\left[ \begin{array}{ccccc}a_{0}&a_{1}&\cdots&a_{N-1}\end{array} \right]^{ \mathsf{T}}\), \(\text{diag}(a)\) is defined as  
\[A =\text{diag}(a)\] \[=\sum_{i=0}^{N-1}a_{i}e_{i}e_{i}^{\mathsf{T}}\] \[=\left[ \begin{array}{ccccc}a_{0}&0&\cdots&0\\ 0&a_{1}&0&\vdots\\ \vdots&0&\ddots&0\\ 0&\cdots&0&a_{N-1}\end{array} \right]\]  
**Theorem 1**. : _If \(a\) and \(b\) are vectors, and \(A=\text{diag}(a)\) and \(B=\text{diag}(b)\), then \(Ab=Ba\)._  
Proof. : Let \(a=\left[ \begin{array}{ccccc}a_{0}&a_{1}&\cdots&a_{N-1}\end{array} \right]^{ \mathsf{T}}\) and \(b=\left[ \begin{array}{ccccc}b_{0}&b_{1}&\cdots&b_{N-1}\end{array} \right]^{ \mathsf{T}}\). \[Ab =\text{diag}(a)\cdot b\] \[=\sum_{i=0}^{N-1}a_{i}e_{i}e_{i}^{\mathsf{T}}b\] \[=\sum_{i=0}^{N-1}a_{i}e_{i}b_{i}=\sum_{i=0}^{N-1}b_{i}e_{i}a_{i}\] \[=\sum_{i=0}^{N-1}b_{i}e_{i}e_{i}^{\mathsf{T}}a\] \[=\text{diag}(b)\cdot a\] \[=Ba\]  
This completes the proof. If \(X\) is the Fourier transform of the vector \(x\) and \(F\) is the Fourier transform matrix,  
\[X =Fx\] \[=V\Lambda V^{\mathsf{T}}x\] \[=V\Lambda\tilde{x}\] \[=V\tilde{X}\lambda \tag{4}\]  
where \(\tilde{x}=V^{\mathsf{T}}x\), \(\tilde{X}=\text{diag}(\tilde{x})\) and \(\Lambda=\text{diag}(\lambda)\) such that \(\lambda\) is a column vector containing the eigenvalues of \(F\). Note that \(\Lambda\tilde{x}=\tilde{X}\lambda\) from Theorem 1. In (4), \(\lambda\) adds the columns of the matrix product \(V\tilde{X}\) in a particular manner defined by the eigenvalues of \(F\). It is well known that there are only four unique eigenvalues for the Fourier transform: \(\pm 1\) and \(\pm j\), where \(j=\sqrt{-1}\) is the imaginary unit [8, 9]. Denote the algebraic multiplicity of the DFT eigenvalues as \(m_{1}\), \(m_{-1}\), \(m_{j}\) and \(m_{-j}\) for the eigenvalues \(1\), \(-1\), \(j\) and \(-j\), respectively. So, for an \(N\)-point DFT, we have \(m_{1}+m_{-1}+m_{j}+m_{-j}=N\). From [7], these multiplicities are  
\[=\sum_{i=0}^{N-1}a_{i}e_{i}e_{i}^{\mathsf{T}}b\]0 \[=\sum_{i=0}^{N-1}a_{i}e_{i}e_{i}^{\mathsf{T}}b\]1Without loss of generality, let \(\lambda\) in (4) be constructed such that the unique eigenvalues are grouped together as shown in (6). This grouping simplifies our derivation. Note that the eigenvectors in the columns of \(V\) will correspond with their respective eigenvalues in the vector \(\lambda\). \[\lambda=\left[ \begin{array}{ccccccccccccc}1&\cdots&1&-1&\cdots&-1&j&\cdots&j&-j& \cdots&-j\end{array} \right]^{\mathrm{T}} \tag{6}\]  
Let \(u\) be an \(N\times 2\) matrix as defined in (7) where the first row contains \(m_{1}\) 1's and \(m_{-1}\) -1's and the second row contains \(m_{j}\) 1's and \(m_{-j}\) -1's. \[u=\left[ \begin{array}{ccccccccc}1&\cdots&1&-1&\cdots&-1&0&&\cdots&&&0\\ 0&&\cdots&&&0&1&\cdots&1&-1&\cdots&-1\end{array}