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 \ = \ {\Sigma}_{0 \, \leq \, i \, < \, n} \ f_i \, x^i \ \in R[x]$$ (13)

of degree less than $n$ with its coefficient vector $(f_0, \ldots, f_{n-1}) \in R^n$ .

Definition 2   The $R$ -linear map

$$DFT_{\omega} \, : \ \left\{ \begin{array}{rcl} R^n & \longmapsto ... ...(1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array} \right.$$ (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, \ldots, {\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, \ldots, {\omega}^{n-1})$ is invertible which holds iff the values $1, {\omega}, {\omega}^2, \ldots, {\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, \ldots, {\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

$$V_{\omega} \, V_{{\omega}^{-1}} \ = \ n I_n$$ (15)

where $I_n$ denotes the unit matrix of order $n$ .

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

$$\begin{array}{rcl} (V_{\omega} \, V_{{\omega}'})_{ik} & = & {... ..._{0 \, \leq \, j \, < \, n} \ ({\omega}^{i-k})^j \\ \end{array}$$ (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}'})_{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}'})_{ik} = 0$ . $\qedsymbol$