next up previous
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 $ \omega$ $ \in$ R be a primitive n-th root of unity. In what follows we identify every univariate polynomial

f  =  $\displaystyle \Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ fi xi  $\displaystyle \in$ R[x] (13)

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

Definition 2   The R-linear map

DFT$\scriptstyle \omega$  :  $\displaystyle \left\{\vphantom{ \begin{array}{rcl} R^n & \longmapsto & R^n \\ ... ...1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array} }\right.$$\displaystyle \begin{array}{rcl} R^n & \longmapsto & R^n \\ f & \longmapsto & (f(1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array}$ (14)

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

Proposition 2   The R-linear map DFT$\scriptstyle \omega$ is an isomorphism.

Proof. Since the R-linear map DFT$\scriptstyle \omega$ is an endomorphism (the source and target spaces are the same) we only need to prove that DFT$\scriptstyle \omega$ is bijective. Observe that the Vandermonde matrix VDM(1,$ \omega$,$ \omega^{{2}}_{{}}$,...,$ \omega^{{{n-1}}}_{{}}$) is the matrix of the R-linear map DFT$\scriptstyle \omega$. Then for proving that DFT$\scriptstyle \omega$ is bijective we need only to prove that VDM(1,$ \omega$,$ \omega^{{2}}_{{}}$,...,$ \omega^{{{n-1}}}_{{}}$) is invertible which holds iff the values 1,$ \omega$,$ \omega^{{2}}_{{}}$,...,$ \omega^{{{n-1}}}_{{}}$ are pairwise different. A relation $ \omega^{{i}}_{{}}$ = $ \omega^{{j}}_{{}}$ for 0 $ \leq$ i < j < n would imply $ \omega^{{i}}_{{}}$ (1 - $ \omega^{{{j-i}}}_{{}}$) = 0. Since (1 - $ \omega^{{{j-i}}}_{{}}$) cannot be zero or a zero divisor then $ \omega^{{i}}_{{}}$ and thus $ \omega$ must be zero. Then $ \omega$ cannot be a root of unity. A contradiction. Therefore the values 1,$ \omega$,$ \omega^{{2}}_{{}}$,...,$ \omega^{{{n-1}}}_{{}}$ are pairwise different and DFT$\scriptstyle \omega$ is an isomorphism. $ \qedsymbol$

Proposition 3   Let V$\scriptstyle \omega$ denote the matrix of the isomorphism DFT$\scriptstyle \omega$. Then $ \omega^{{{-1}}}_{{}}$ the inverse of $ \omega$ is also a primitive n-th root of unity and we have

V$\scriptstyle \omega$ V$\scriptstyle \omega^{{{-1}}}$  =  nIn (15)

where In denotes the unit matrix of order n.

Proof. Define $ \omega$$\scriptstyle \prime$ = $ \omega^{{{-1}}}_{{}}$. Observe that $ \omega$$\scriptstyle \prime$ = $ \omega^{{{n-1}}}_{{}}$. Thus $ \omega$$\scriptstyle \prime$ 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$\scriptstyle \omega$ and V$\scriptstyle \omega$$\scriptscriptstyle \prime$. The element at row i and column k is

(V$\scriptstyle \omega$ V$\scriptstyle \omega$$\scriptscriptstyle \prime$)ik = $\displaystyle \Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}}$ (V$\scriptstyle \omega$)ij(V$\scriptstyle \omega$$\scriptscriptstyle \prime$)jk
  = $\displaystyle \Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}}$ $\displaystyle \omega^{{{ij}}}_{{}}$ ($\displaystyle \omega$$\scriptstyle \prime$)jk
  = $\displaystyle \Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}}$ $\displaystyle \omega^{{{ij}}}_{{}}$ $\displaystyle \omega^{{{{-jk}}}}_{{{}}}$
  = $\displaystyle \Sigma_{{{0 \, \leq \, j \, < \, n}}}^{{}}$ ($\displaystyle \omega^{{{i-k}}}_{{}}$)j
(16)

Observe that $ \omega^{{{i-k}}}_{{}}$ is either a power of $ \omega$ or a power of its inverse. Thus, in any case this is a power of $ \omega$. If i = k this power is 1 and (V$\scriptstyle \omega$ V$\scriptstyle \omega$$\scriptscriptstyle \prime$)ik is equal to n. If i $ \neq$ k then the conclusion follows by applying the second statement of Lemma 1 which shows that (V$\scriptstyle \omega$ V$\scriptstyle \omega$$\scriptscriptstyle \prime$)ik = 0. $ \qedsymbol$

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