Proof.
Since the
Rlinear map
DFT_{} is an endomorphism
(the source and target spaces are the same)
we only need to prove
that
DFT_{} is bijective.
Observe that the Vandermonde matrix
VDM(1,
,
,...,
)
is the matrix of the
Rlinear map
DFT_{}.
Then for proving that
DFT_{} is bijective
we need only to prove that
VDM(1,
,
,...,
)
is invertible which holds iff the values
1,
,
,...,
are pairwise different.
A relation
=
for
0
i <
j <
n would imply
(1 
) = 0.
Since
(1 
) cannot be zero or a zero divisor
then
and thus
must be zero.
Then
cannot be a root of unity. A contradiction.
Therefore the values
1,
,
,...,
are pairwise different and
DFT_{} is an isomorphism.
Proposition 3
Let
V_{} denote the matrix of the isomorphism
DFT_{}.
Then
the inverse of
is also a
primitive
nth root of unity and we have
where
I_{n} denotes the unit matrix of order
n.
Proof.
Define
^{} =
.
Observe that
^{} =
.
Thus
^{} is a root of unity.
We leave to the reader the proof that this a primitive
nth root of unity,
Let us consider the product of the matrix
V_{} and
V_{}.
The element at row i and column k is
(V_{} V_{})_{ik} 
= 
(V_{})_{ij}(V_{})_{jk} 

= 
(^{})^{jk} 

= 


= 
()^{j} 

(16) 
Observe that
is either a power of
or a power of its inverse.
Thus, in any case this is a power of
.
If
i =
k this power is 1 and
(
V_{} V_{})
_{ik} is equal to
n.
If
i k then the conclusion follows by applying the second statement of
Lemma
1
which shows that
(
V_{} V_{})
_{ik} = 0.