Next: Convolution of polynomials Up: Fast Polynomial Multiplication based on Previous: Primitive roots of unity

## The Discrete Fourier Transform

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

 f  =   fi xi  R[x] (13)

of degree less than n with its coefficient vector (f0,..., fn-1) Rn.

Definition 2   The R-linear map

 DFT  : (14)

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

Proposition 2   The R-linear map DFT is an isomorphism.

Proof. Since the R-linear map DFT is an endomorphism (the source and target spaces are the same) we only need to prove that DFT is bijective. Observe that the Vandermonde matrix VDM(1,,,...,) is the matrix of the R-linear map DFT. Then for proving that DFT is bijective we need only to prove that VDM(1,,,...,) is invertible which holds iff the values 1,,,..., are pairwise different. A relation = for 0 i < j < n would imply  (1 - ) = 0. Since (1 - ) 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 1,,,..., are pairwise different and DFT is an isomorphism.

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

 V V  =  nIn (15)

where In denotes the unit matrix of order n.

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

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

 (V V)ik = (V)ij(V)jk = ()jk = = ()j
(16)

Observe that is either a power of or a power of its inverse. Thus, in any case this is a power of . If i = k this power is 1 and (V V)ik is equal to n. If i k then the conclusion follows by applying the second statement of Lemma 1 which shows that (V V)ik = 0.

Next: Convolution of polynomials Up: Fast Polynomial Multiplication based on Previous: Primitive roots of unity
Marc Moreno Maza
2003-06-06