Editing Discrete Fourier transform (section)

==Generalizations==

=== Representation theory ===
{{further|Representation theory of finite groups#Discrete Fourier transform}}

The DFT can be interpreted as a complex-valued [[representation theory|representation]] of the finite [[cyclic group]]. In other words, a sequence of <math>n</math> complex numbers can be thought of as an element of <math>n</math>-dimensional complex space <math>\mathbb{C}^n</math> or equivalently a function <math>f</math> from the finite cyclic group of order <math>n</math> to the complex numbers, <math>\mathbb{Z}_n \mapsto \mathbb{C}</math>. So  <math>f</math> is a [[class function]] on the finite cyclic group, and thus can be expressed as a linear combination of the irreducible characters of this group, which are the roots of unity.

From this point of view, one may generalize the DFT to representation theory generally, or more narrowly to the [[representation theory of finite groups]].

More narrowly still, one may generalize the DFT by either changing the target (taking values in a field other than the complex numbers), or the domain (a group other than a finite cyclic group), as detailed in the sequel.

=== Other fields ===
{{Main|Discrete Fourier transform (general)|Number-theoretic transform}}
Many of the properties of the DFT only depend on the fact that <math>e^{-\frac{i 2 \pi}{N}}</math> is a [[primitive root of unity]], sometimes denoted <math>\omega_N</math> or <math>W_N</math> (so that <math>\omega_N^N = 1</math>).  Such properties include the completeness, orthogonality, Plancherel/Parseval, periodicity, shift, convolution, and unitarity properties above, as well as many FFT algorithms. For this reason, the discrete Fourier transform can be defined by using roots of unity in [[field (mathematics)|fields]] other than the complex numbers, and such generalizations are commonly called ''number-theoretic transforms'' (NTTs) in the case of [[finite field]]s. For more information, see [[number-theoretic transform]] and [[discrete Fourier transform (general)]].

=== Other finite groups ===
{{Main|Fourier transform on finite groups}}
The standard DFT acts on a sequence ''x''<sub>0</sub>, ''x''<sub>1</sub>, ..., ''x''<sub>''N''−1</sub> of complex numbers, which can be viewed as a function {0, 1, ..., ''N'' − 1} → '''C'''. The multidimensional DFT acts on multidimensional sequences, which can be viewed as functions
:<math> \{0, 1, \ldots, N_1-1\} \times \cdots \times \{0, 1, \ldots, N_d-1\} \to \mathbb{C}. </math>
This suggests the generalization to [[Fourier transform on finite groups|Fourier transforms on arbitrary finite groups]], which act on functions ''G'' → '''C''' where ''G'' is a [[finite group]]. In this framework, the standard DFT is seen as the Fourier transform on a [[cyclic group]], while the multidimensional DFT is a Fourier transform on a direct sum of cyclic groups.

Further, Fourier transform can be on cosets of a group.