## The Discrete Fourier Transform

Let be a positive integer and be a primitive -th root of unity. In what follows we identify every univariate polynomial

 (13)

of degree less than with its coefficient vector .

Definition 2   The -linear map

 (14)

which evaluates a polynomial at the powers of is called the Discrete Fourier Transform (DFT).

Proposition 2   The -linear map is an isomorphism.

Proof. Since the -linear map is an endomorphism (the source and target spaces are the same) we only need to prove that is bijective. Observe that the Vandermonde matrix is the matrix of the -linear map . Then for proving that is bijective we need only to prove that is invertible which holds iff the values are pairwise different. A relation for would imply . Since cannot be zero or a zero divisor then and thus must be zero. Then cannot be a root of unity. A contradiction. Therefore the values are pairwise different and is an isomorphism.

Proposition 3   Let denote the matrix of the isomorphism . Then the inverse of is also a primitive -th root of unity and we have

 (15)

where denotes the unit matrix of order .

Proof. Define . Observe that . Thus is a root of unity. We leave to the reader the proof that this a primitive -th root of unity,

Let us consider the product of the matrix and . The element at row and column is

 (16)

Observe that is either a power of or a power of its inverse. Thus, in any case this is a power of . If this power is and is equal to . If then the conclusion follows by applying the second statement of Lemma 1 which shows that .

Marc Moreno Maza
2008-01-07