Discrete Fourier transform (general)

In mathematics, the discrete Fourier transform over an arbitrary ring generalizes the discrete Fourier transform of a function whose values are complex numbers. In mathematics, the discrete Fourier transform over an arbitrary ring generalizes the discrete Fourier transform of a function whose values are complex numbers. Let R {displaystyle R} be any ring, let n ≥ 1 {displaystyle ngeq 1} be an integer, and let α ∈ R {displaystyle alpha in R} be a principal nth root of unity, defined by: The discrete Fourier transform maps an n-tuple ( v 0 , … , v n − 1 ) {displaystyle (v_{0},ldots ,v_{n-1})} of elements of R {displaystyle R} to another n-tuple ( f 0 , … , f n − 1 ) {displaystyle (f_{0},ldots ,f_{n-1})} of elements of R {displaystyle R} according to the following formula: By convention, the tuple ( v 0 , … , v n − 1 ) {displaystyle (v_{0},ldots ,v_{n-1})} is said to be in the time domain and the index j {displaystyle j} is called time. The tuple ( f 0 , … , f n − 1 ) {displaystyle (f_{0},ldots ,f_{n-1})} is said to be in the frequency domain and the index k {displaystyle k} is called frequency. The tuple ( f 0 , … , f n − 1 ) {displaystyle (f_{0},ldots ,f_{n-1})} is also called the spectrum of ( v 0 , … , v n − 1 ) {displaystyle (v_{0},ldots ,v_{n-1})} . This terminology derives from the applications of Fourier transforms in signal processing. If R {displaystyle R} is an integral domain (which includes fields), it is sufficient to choose α {displaystyle alpha } as a primitive nth root of unity, which replaces the condition (1) by: Proof: take β = α k {displaystyle eta =alpha ^{k}} with 1 ≤ k < n {displaystyle 1leq k<n} . Since α n = 1 {displaystyle alpha ^{n}=1} , β n = ( α n ) k = 1 {displaystyle eta ^{n}=(alpha ^{n})^{k}=1} , giving: where the sum matches (1). Since α {displaystyle alpha } is a primitive root of unity, β − 1 ≠ 0 {displaystyle eta -1 eq 0} . Since R {displaystyle R} is an integral domain, the sum must be zero. ∎ Another simple condition applies in the case where n is a power of two: (1) may be replaced by α n / 2 = − 1 {displaystyle alpha ^{n/2}=-1} .