Editing Discrete Fourier transform (section)

=== Eigenvalues and eigenvectors ===

The [[eigenvalue]]s of the DFT matrix are simple and well-known, whereas the [[eigenvector]]s are complicated, not unique, and are the subject of ongoing research. Explicit formulas are given with a significant amount of number theory.<ref>{{cite journal |last1=Morton |first1=Patrick |title=On the eigenvectors of Schur's matrix |journal=Journal of Number Theory |date=1980 |volume=12 |issue=1 |pages=122–127 |doi=10.1016/0022-314X(80)90083-9 |url=https://dx.doi.org/10.1016/0022-314X%2880%2990083-9|hdl=2027.42/23371 |hdl-access=free }}</ref>

Consider the unitary form <math>\mathbf{U}</math> defined above for the DFT of length ''N'', where
:<math>\mathbf{U}_{m,n} = \frac 1{\sqrt{N}}\omega_N^{(m-1)(n-1)} = \frac 1{\sqrt{N}}e^{-\frac{i 2\pi}N (m-1)(n-1)}.</math>
This matrix satisfies the [[matrix polynomial]] equation:
:<math>\mathbf{U}^4 = \mathbf{I}.</math>
This can be seen from the inverse properties above: operating <math>\mathbf{U}</math> twice gives the original data in reverse order, so operating <math>\mathbf{U}</math> four times gives back the original data and is thus the [[identity matrix]].  This means that the eigenvalues <math>\lambda</math> satisfy the equation:
:<math>\lambda^4 = 1.</math>
Therefore, the eigenvalues of <math>\mathbf{U}</math> are the fourth [[roots of unity]]: <math>\lambda</math> is +1, −1, +''i'',  or −''i''.

Since there are only four distinct eigenvalues for this <math>N\times N</math> matrix, they have some [[algebraic multiplicity|multiplicity]].  The multiplicity gives the number of [[linearly independent]] eigenvectors corresponding to each eigenvalue.  (There are ''N'' independent eigenvectors; a unitary matrix is never [[defective matrix|defective]].)

The problem of their multiplicity was solved by McClellan and Parks (1972), although it was later shown to have been equivalent to a problem solved by [[Carl Friedrich Gauss|Gauss]] (Dickinson and Steiglitz, 1982).  The multiplicity depends on the value of ''N'' [[modular arithmetic|modulo]] 4, and is given by the following table:

{| class="wikitable" style="margin:auto;"
|+ align="bottom" | Multiplicities of the eigenvalues λ of the unitary DFT matrix '''U''' as a function of the transform size ''N'' (in terms of an integer ''m'').
|-
! size ''N''
! λ = +1
! λ = −1
! λ = −''i''
! λ = +''i''
|-
|    4''m''  ||  ''m'' + 1  ||  ''m''  ||  ''m''  ||  ''m'' − 1
|-
|    4''m'' + 1  ||  ''m'' + 1  ||  ''m''  ||  ''m''  ||  ''m''
|-
|    4''m'' + 2  ||  ''m'' + 1  ||  ''m'' + 1  ||  ''m''  ||  ''m''
|-
|    4''m'' + 3  ||  ''m'' + 1  ||  ''m'' + 1  ||  ''m'' + 1  ||  ''m''
|}

Otherwise stated, the [[characteristic polynomial]] of <math>\mathbf{U}</math> is:
:<math>\det (\lambda I - \mathbf{U})=
(\lambda-1)^{\left\lfloor \tfrac {N+4}{4}\right\rfloor}
(\lambda+1)^{\left\lfloor \tfrac {N+2}{4}\right\rfloor}
(\lambda+i)^{\left\lfloor \tfrac {N+1}{4}\right\rfloor}
(\lambda-i)^{\left\lfloor \tfrac {N-1}{4}\right\rfloor}.</math>

No simple analytical formula for general eigenvectors is known.   Moreover, the eigenvectors are not unique because any linear combination of eigenvectors for the same eigenvalue is also an eigenvector for that eigenvalue.  Various researchers have proposed different choices of eigenvectors, selected to satisfy useful properties like [[orthogonality]] and to have "simple" forms (e.g., McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan ''et al.'', 2000; Hanna ''et al.'', 2004; Gurevich and Hadani, 2008).

One method to construct DFT eigenvectors to an eigenvalue <math>\lambda</math> is based on the linear combination of operators:<ref>Bose, N. K. "Eigenvectors and eigenvalues of 1-D and nD DFT matrices." [[AEU — International Journal of Electronics and Communications]] 55.2 (2001): 131-133.</ref><ref name="candan">Candan, Ç. (2011). On the eigenstructure of DFT matrices [DSP education]. IEEE Signal Processing Magazine, 28(2), 105-108.</ref><ref name="pei">Pei, S. C., Ding, J. J., Hsue, W. L., & Chang, K. W. (2008). Generalized commuting matrices and their eigenvectors for DFTs, offset DFTs, and other periodic operations. IEEE Transactions on Signal Processing, 56(8), 3891-3904.</ref>

<math> \mathcal{P}_\lambda=\frac{1}{4}\left( \mathbf{I}+\lambda^{-1}\mathbf{U}+\lambda^{-2}\mathbf{U}^2+\lambda^{-3} \mathbf{U}^3\right)</math>

For an arbitrary vector <math>\mathbf{v}</math>, vector <math>\mathbf{u}(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}</math> satisfies:

<math> \textbf{U}\mathbf{u}(\lambda)=\lambda \mathbf{u}(\lambda) </math>

hence, vector <math>\mathbf{u}(\lambda)</math> is, indeed, the eigenvector of DFT matrix <math>\mathbf{U}</math>. Operators <math> \mathcal{P}_{\lambda} </math> project vectors onto subspaces which are orthogonal for each value of <math>\lambda</math>.<ref name="candan"/> That is, for two eigenvectors, <math>\mathbf{u}(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}</math> and <math>\mathbf{u}'(\lambda')=\mathcal{P}_{\lambda'}\mathbf{v}'</math> we have:

<math>\mathbf{u}^\dagger(\lambda) \mathbf{u}'(\lambda')= \delta_{\lambda\lambda'}\mathbf{u}^\dagger(\lambda) \mathbf{v}' </math>

However, in general, projection operator method does not produce orthogonal eigenvectors within one subspace.<ref name="pei"/> The operator <math>\mathcal{P}_{\lambda}</math> can be seen as a matrix, whose columns are eigenvectors of <math>\mathbf{U}</math>, but they are not orthogonal. When a set of vectors <math>\{\mathbf{v}_n\}_{n=1,\dots,N_{\lambda}}</math>, spanning <math>N_{\lambda}</math>-dimensional space (where <math>N_{\lambda}</math> is the multiplicity of eigenvalue <math>\lambda</math>) is chosen to generate the set of eigenvectors <math>\{\mathbf{u}_n(\lambda)=\mathcal{P}_{\lambda}\mathbf{v}_n\}_{n=1,\dots,N_{\lambda}}</math> to eigenvalue <math>\lambda</math>, the mutual orthogonality of <math>\mathbf{u}_n(\lambda)</math> is not guaranteed. However, the orthogonal set can be obtained by further applying orthogonalization algorithm to the set <math>\{\mathbf{u}_n(\lambda)\}_{n=1,\dots,N_{\lambda}}</math>, e.g. [[Gram-Schmidt process]].<ref>Erseghe, T., & Cariolaro, G. (2003). An orthonormal class of exact and simple DFT eigenvectors with a high degree of symmetry. IEEE transactions on signal processing, 51(10), 2527-2539.</ref>

A straightforward approach to obtain DFT eigenvectors is to discretize an eigenfunction of the continuous [[Fourier transform]],
of which the most famous is the [[Gaussian function]].
Since [[periodic summation]] of the function means discretizing its frequency spectrum
and discretization means periodic summation of the spectrum,
the discretized and periodically summed Gaussian function yields an eigenvector of the discrete transform:
* <math>F(m) = \sum_{k\in\mathbb{Z}} \exp\left(-\frac{\pi\cdot(m+N\cdot k)^2}{N}\right).</math>

The closed form expression for the series can be expressed by [[Jacobi theta function]]s as
* <math>F(m) = \frac1{\sqrt{N}}\vartheta_3\left(\frac{\pi m}N, \exp\left(-\frac{\pi}N \right)\right).</math>

Several other simple closed-form analytical eigenvectors for special DFT period ''N'' were found (Kong, 2008 and Casper-Yakimov, 2024):

For DFT period ''N'' = 2''L'' + 1 = 4''K'' + 1, where ''K'' is an integer, the following is an eigenvector of DFT:
* <math>F(m) = \prod_{s=K+1}^L \left[\cos\left(\frac{2\pi}{N}m\right) - \cos\left(\frac{2\pi}{N}s\right)\right]</math>

For DFT period ''N'' = 2''L'' = 4''K'', where ''K'' is an integer, the following are eigenvectors of DFT:
* <math>F(m) = \sin\left(\frac{2\pi}{N}m\right) \prod_{s=K+1}^{L-1}\left[\cos\left(\frac{2\pi}{N}m\right)- \cos\left(\frac{2\pi}{N}s\right)\right]</math>
* <math>F(m) = \cos\left(\frac{\pi}{N}m\right)\prod_{s=K+1}^{3K-1} \sin\left(\frac{\pi(s-m)}{N}\right)</math>

For DFT period ''N'' = 4''K'' - 1, where ''K'' is an integer, the following are eigenvectors of DFT:
* <math>F(m) = \sin\left(\frac{2\pi}{N}m\right)\prod_{s=K+1}^{3K-2} \sin\left(\frac{\pi(s-m)}{N}\right)</math>
* <math>F(m) = \left(\cos\left(\frac{2\pi}{N}m\right)-\cos\left(\frac{2\pi}{N}K\right)\pm\sin\left(\frac{2\pi}{N}K\right)\right)\prod_{s=K+1}^{3K-2} \sin\left(\frac{\pi(s-m)}{N}\right)</math>

The choice of eigenvectors of the DFT matrix has become important in recent years in order to define a discrete analogue of the [[fractional Fourier transform]]—the DFT matrix can be taken to fractional powers by exponentiating the eigenvalues (e.g., Rubio and Santhanam, 2005).  For the [[continuous Fourier transform]], the natural orthogonal eigenfunctions are the [[Hermite function]]s, so various discrete analogues of these have been employed as the eigenvectors of the DFT, such as the [[Kravchuk polynomials]] (Atakishiyev and Wolf, 1997).  The "best" choice of eigenvectors to define a fractional discrete Fourier transform remains an open question, however.