The Discrete Fourier Transform

Let n mathend000# be a positive integer and $\omega$ $\in$ R mathend000# be a primitive n mathend000#-th root of unity. In what follows we identify every univariate polynomial

$$\Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}} \in$$ (13)

of degree less than n mathend000# with its coefficient vector (f₀,..., f_n-1) $\in$ Rⁿ mathend000#.

Definition 2   The R mathend000#-linear map

$$\omega \left\{\vphantom{ \begin{array}{rcl} R^n & \longmapsto & R^n \\ ... ...1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array} }\right. \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$ mathend000# is called the Discrete Fourier Transform (DFT).

Proposition 2   The R mathend000#-linear map DFT_$\omega$ mathend000# is an isomorphism.

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

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

$$\omega \omega^{{{-1}}}$$ (15)

where I_n mathend000# denotes the unit matrix of order n mathend000#.

Proof. Define $\omega$^$\prime$ = $\omega^{{{-1}}}_{{}}$ mathend000#. Observe that $\omega$^$\prime$ = $\omega^{{{n-1}}}_{{}}$ mathend000#. Thus $\omega$^$\prime$ mathend000# is a root of unity. We leave to the reader the proof that this a primitive n mathend000#-th root of unity,

Let us consider the product of the matrix V_$\omega$ mathend000# and V_{$\omega$^$\prime$} mathend000#. The element at row i mathend000# and column k mathend000# is

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

(16)

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