Proof.
Since the
![$ R$](img4.png)
-linear map
![$ DFT_{\omega}$](img111.png)
is an endomorphism
(the source and target spaces are the same)
we only need to prove
that
![$ DFT_{\omega}$](img111.png)
is bijective.
Observe that the Vandermonde matrix
![$ VDM(1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1})$](img112.png)
is the matrix of the
![$ R$](img4.png)
-linear map
![$ DFT_{\omega}$](img111.png)
.
Then for proving that
![$ DFT_{\omega}$](img111.png)
is bijective
we need only to prove that
![$ VDM(1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1})$](img112.png)
is invertible which holds iff the values
![$ 1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1}$](img113.png)
are pairwise different.
A relation
![$ {\omega}^i = {\omega}^j$](img114.png)
for
![$ 0 \leq i < j < n$](img115.png)
would imply
![$ {\omega}^i \, (1 - {\omega}^{j-i}) = 0$](img116.png)
.
Since
![$ (1 - {\omega}^{j-i})$](img117.png)
cannot be zero or a zero divisor
then
![$ {\omega}^i$](img118.png)
and thus
![$ {\omega}$](img67.png)
must be zero.
Then
![$ {\omega}$](img67.png)
cannot be a root of unity. A contradiction.
Therefore the values
![$ 1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1}$](img113.png)
are pairwise different and
![$ DFT_{\omega}$](img111.png)
is an isomorphism.
Proof.
Define
![$ {\omega}' = {\omega}^{-1}$](img123.png)
.
Observe that
![$ {\omega}' = {\omega}^{n-1}$](img124.png)
.
Thus
![$ {\omega}'$](img125.png)
is a root of unity.
We leave to the reader the proof that this a primitive
![$ n$](img2.png)
-th root of unity,
Let us consider the product of the matrix
and
.
The element at row
and column
is
![\begin{displaymath}\begin{array}{rcl} (V_{\omega} \, V_{{\omega}'})_{ik} & = & {...
..._{0 \, \leq \, j \, < \, n} \ ({\omega}^{i-k})^j \\ \end{array}\end{displaymath}](img129.png) |
(16) |
Observe that
![$ {\omega}^{i-k}$](img130.png)
is either a power of
![$ {\omega}$](img67.png)
or a power of its inverse.
Thus, in any case this is a power of
![$ {\omega}$](img67.png)
.
If
![$ i=k$](img131.png)
this power is
![$ 1$](img25.png)
and
![$ (V_{\omega} \, V_{{\omega}'})_{ik}$](img132.png)
is equal to
![$ n$](img2.png)
.
If
![$ i \neq k$](img133.png)
then the conclusion follows by applying the second statement of
Lemma
1
which shows that
![$ (V_{\omega} \, V_{{\omega}'})_{ik} = 0$](img134.png)
.