Proof.
Since the
linear map
is an endomorphism
(the source and target spaces are the same)
we only need to prove
that
is bijective.
Observe that the Vandermonde matrix
is the matrix of the
linear map
.
Then for proving that
is bijective
we need only to prove that
is invertible which holds iff the values
are pairwise different.
A relation
for
would imply
.
Since
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
are pairwise different and
is an isomorphism.
Proof.
Define
.
Observe that
.
Thus
is a root of unity.
We leave to the reader the proof that this a primitive
th root of unity,
Let us consider the product of the matrix
and
.
The element at row
and column
is

(16) 
Observe that
is either a power of
or a power of its inverse.
Thus, in any case this is a power of
.
If
this power is
and
is equal to
.
If
then the conclusion follows by applying the second statement of
Lemma
1
which shows that
.