Discrete Fourier transform over a ring

In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring. Let R be any ring, let be an integer, and let be a principal nth root of unity, defined by: The discrete Fourier transform maps an n-tuple of elements of R to another n-tuple of elements of R according to the following formula: By convention, the tuple is said to be in the time domain and the index j is called time. The tuple is said to be in the frequency domain and the index k is called frequency. The tuple is also called the spectrum of . This terminology derives from the applications of Fourier transforms in signal processing. If R is an integral domain (which includes fields), it is sufficient to choose as a primitive nth root of unity, which replaces the condition () by: for Take with . Since , , giving: where the sum matches (). Since is a primitive root of unity, . Since R is an integral domain, the sum must be zero. ∎ Another simple condition applies in the case where n is a power of two: () may be replaced by . The inverse of the discrete Fourier transform is given as: where is the multiplicative inverse of n in R (if this inverse does not exist, the DFT cannot be inverted). Substituting () into the right-hand-side of (), we get This is exactly equal to , because when (by () with ), and when . ∎ Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows: The matrix for this transformation is called the DFT matrix. Similarly, the matrix notation for the inverse Fourier transform is Sometimes it is convenient to identify an n-tuple with a formal polynomial By writing out the summation in the definition of the discrete Fourier transform (), we obtain: This means that is just the value of the polynomial for , i.e.