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

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

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

Definition 2   The R-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$ is called the Discrete Fourier Transform (DFT).

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

Proof. Since the R-linear map DFT_$\omega$ is an endomorphism (the source and target spaces are the same) we only need to prove that DFT_$\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_$\omega$. Then for proving that DFT_$\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_$\omega$ is an isomorphism. $\qedsymbol$

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

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

where I_n denotes the unit matrix of order n.

Proof. Define $\omega$^$\prime$ = $\omega^{{{-1}}}_{{}}$. Observe that $\omega$^$\prime$ = $\omega^{{{n-1}}}_{{}}$. Thus $\omega$^$\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_$\omega$ and V_{$\omega$^$\prime$}. The element at row i and column k 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}}}_{{}}$ 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_$\omega$ V_{$\omega$^$\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_$\omega$ V_{$\omega$^$\prime$})_ik = 0. $\qedsymbol$