arXiv:1803.09239v1 [math.GR] 25 Mar 2018

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER
TRANSFORM
JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS

Abstract. In this paper we deal with a finite abelian group G and the abstract Fourier transform F : CG → CĜ . Then, we consider j̃ ◦ F : CG → CĜ
where j̃ : CĜ → CG is defined by the composition with a bijection j : G → Ĝ.
(j̃ is a pullback of j.) In particular, we show that (j̃ ◦ F )2 is a permutation if
and only if j is a group isomorphism. Then, we study how the spectra of j̃ ◦ F
depends on the isomorphism j.

1. Introduction
Let G be a finite abelian group and Ĝ its dual. Abstractly, a Fourier transform
is a linear operator F : CG → CĜ . So, it is a linear map from one space to another
and it is worthless to speak about its spectrum and period, etc. In order to do it,
we have to identify CG with CĜ . To this end, we may take a bijection j : G → Ĝ
and consider j̃ : CĜ → CG defined as (j̃f )(g) = f (j(g)). A “concrete” Fourier
transform is a composition j̃ ◦ F. Our first result: (j̃ ◦ F)2 is a permutation if
and only if j is an isomorphism. In this case (j̃ ◦ F)2 is (a pullback of) ĵ −1 ◦ j
which is an automorphism of G. Here, ĵ : G → Ĝ is the dual of j. This result
distinguishes isomorphisms from other bijections by “Fourier transform’s point of
view”. So, further we consider the case when j is an isomorphism. But, which
isomorphism j should we take? From the pure group theoretic point of view, there
are no natural choices for j. Of course, we may try to find j with ĵ −1 ◦ j equal
to a fixed automorphism. Such a choice is not always possible and, if possible, is
not unique. For example, if G is an additive group of Z/nZ, then ĵ −1 ◦ j is always
the map x → −x. Still, we show that, in this case, the spectra (the multiplicities
of eigenvalues) of j̃ ◦ F does depend on j. If G = (Z/nZ)m , then there are more
flexibility in the choice of ĵ −1 ◦ j. Particularly, ĵ −1 ◦ j could be the identical
transformation for even m. We consider several other examples and show how the
spectra may be calculated in those cases.
We do not give a receipt for choosing j. We just point out that there are several
choices and the properties of the Fourier transform do depend on these choices. In
applied mathematics, for an additive group Z/nZ, which is a cyclic group Cn , up
to an isomorphism, we choose j(x) = wx , where w is the n-th root of unity closest
to 1. This corresponds to the choice of a generator of Cn . If G = (Z/nZ)m , we may
choose j to be the m-th power of the above defined j. Are those choices natural?
Of course, the answer to this question depends on the problem. If G comes with
presentation as a direct product (which is not unique), then there is a naturally
2010 Mathematics Subject Classification. Primary 11T06; Secondary 13M10.
This paper is in final form and no version of it will be submitted for publication elsewhere.
1

2

JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS

defined presentation of Ĝ as a direct product. So, in this case, the choice of j as
a direct product might be natural. On the other hand, it is known that there are
no natural isomorphism G → Ĝ in the category of abelian groups. So, it looks
like that for a pure group-theoretical problem (without some additional structure)
there is no natural choice for an isomorphism j. So, it is interesting to study the
dependence of j̃ ◦ F on the isomorphism j.
2. Preliminaries
Let G be a finite abelian group. Set CG = {f : G → C}, the C-valued functions
on G. This is a C-vector space of functions. Every f ∈ CG can be expressed as a
linear combination of the delta functions δg : G → {0, 1} defined by

 1 if x = g,
δg (x) =

0 if x 6= g,
for every g ∈ G, as follows
f=

X

f (g)δg .

g∈G

Indeed, evaluate both sides at each x ∈ G and we get
Pthe same value. The functions
δg span CG and they are linearly independent: if g∈G ag δg = 0, then evaluating
the sum at x ∈ G shows ax = 0. Thus, the functions δg are a basis of CG , so
dim CG = |G|.
A character of G is a homomorphism χ : G → S 1 . For a character χ on G, the
conjugate character is the function χ : G → S 1 given by χ(g) := χ(g). Since for
any complex number z with |z| = 1, z = z1 , we have that χ(g) = χ(g)−1 = χ(g −1 ).
The dual group, or character group, of G is the set of homomorphisms G → S 1
with the group law of pointwise multiplication of functions: (χψ)(g) = χ(g)ψ(g).
The dual group of G is denoted by Ĝ.
The following result is well known.
Theorem 2.1. If G is a finite abelian group, then G and Ĝ are isomorphic.
The next theorem is the first step leading to an expression for each δg as a linear
combination of characters of G, which will lead to a Fourier series expansion of f
(see [2]).
Theorem 2.2 (Orthogonality relations). Let G be a finite abelian group. Then


 |G| if χ = χ0 ,
 |G| if g = 1,
X
X
χ(g) =
χ(g) =


0
if χ 6= χ0 ,
0
if g 6= 1.
g∈G
b
χ∈G
The Fourier transform F : CG → CĜ is the linear map defined as
1 X
F(f )(χ) = p
f (g)χ(g)
|G| g∈G
where CG and CĜ are C-vector spaces of dimension |G| = |Ĝ|.
The process of recovering f from its Fourier transform F(f ) is called Fourier
inversion. The following theorem is a direct corollary of the Orthogonality relations.

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER TRANSFORM

3

Theorem 2.3 (Fourier inversion). Let G be a finite abelian group. If f ∈ CG , then
1 X
f (x) = p
F(f )(χ)χ̄(x)
|G| b
χ∈G

for all x ∈ G.
Since F is an isomorphism of two different vector spaces, we are not allowed to
talk about F 2 , the spectra of F, etc.
On CG there is a natural unitary scalar product h·, ·i defined as follows
1 X
f1 (g)f2 (g).
hf1 , f2 i = p
|G| g∈G
With this scalar product, CG and CĜ are unitary C-vector spaces. The orthogonality relations imply that
hF(f1 ), F(f2 )i = hf1 , f2 i
G

for all f1 , f2 ∈ C . So, F is a unitary transform CG → CĜ .
3. Main results of this paper
G

Let us note, that C forms an algebra under pointwise addition and multiplication:
(f1 + f2 )(g) = f1 (g) + f2 (g),
(f1 f2 )(g) = f1 (g)f2 (g).
So, CG contains multiplicative subgroup (S 1 )G . Naturally, Ĝ ⊂ (S 1 )G ⊂ CG .
Let j : G → Ĝ be a function and ĵ : G → CG be its dual function defined
by ĵ(h)(x) = j(x)(h). Notice that ĵ(G) ⊆ (S 1 )G and G → (S 1 )G is always a
homomorphism (even if j is not).
Theorem 3.1. ĵ(G) ⊂ Ĝ if and only if j is a homomorphism.
Proof. Suppose that j is a homomorphism and let g ∈ G. Then, for all x, y ∈ G we
have
ĵ(g)(xy) = j(xy)(g) = (j(x)j(y))(g) = j(x)(g)j(y)(g) = j(x)(g) · j(y)(g)
= ĵ(g)(x)ĵ(g)(y)
and hence ĵ(G) ⊂ Ĝ.
Conversely, suppose that ĵ(G) ⊂ Ĝ and let x, y, h ∈ G. Then,
j(xy)(h) = j(xy)(h) = ĵ(h)(xy)
= ĵ(h)(x)ĵ(h)(y)
= j(x)(h)j(y)(h) = (j(x)(h))(j(y)(h)) = (j(x)j(y))(h),
and therefore j(xy) = j(x)j(y) for all x, y ∈ G, that is, j is a homomorphism.



Corollary 3.2. j is an isomorphism if and only if ĵ(G) = Ĝ.
Proof. Suppose that j is an isomorphism. By Theorem 3.1 we have ĵ(G) ⊂ Ĝ and
ĵ : G → Ĝ. Moreover, ĵ is a homomorphism. We will prove that ĵ is injective and
thus it will be an isomorphism since |G| = |Ĝ| and G is finite. Let h ∈ ker ĵ. Then,
ĵ(h)(x) = 1 for all x ∈ G. It follows that j(x)(h) = 1 for all x ∈ G and, therefore,

4

JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS

P

x∈G j(x)(h) = |G|. Since j is a bijection, j(x) runs over all Ĝ as x runs over all
G. By the orthogonality relations we obtain that h is the identity of G. Therefore,
ĵ is injective.
Suppose now that ĵ(G) = Ĝ. It follows that ĵ : G → Ĝ is an isomorphism
and we deduce, applying the above arguments to ĵ, that ˆĵ(G) = Ĝ and ˆĵ is an

isomorphism. We just have to check that ˆĵ = j.



Let j : G → Ĝ be a bijection. Then, j induces a unitary linear map j̃ : CĜ → CG
defined as
j̃(φ)(g) = φ(j(g)).
Now, the composition j̃ ◦ F : CG → CG is a unitary linear function. We will say
that P : CG → CG is a permutation if P (f ) = f ◦p for all f ∈ CG , where p : G → G
is a bijection.
Theorem 3.3. Let G be a finite abelian group, j : G → Ĝ a bijection and P =
(j̃ ◦ F)2 . Then, P is a permutation if and only if j is an isomorphism. In this case
p = ĵ −1 ◦ j is an isomorphism.
Proof. Suppose that P is a permutation. Then there is a bijection p : G → G such
that P (f ) = f ◦ p for all f ∈ CG . It is enough to prove that j is a homomorphism
since j is a bijection.
Recall that δg : G → {0, 1} is the g-delta function (g ∈ G). Then for every x ∈ G
we have
1 X
1 X
F(δg )(j(h)) · (j(x))(h) =
(j(h))(g) · (j(x))(h).
P (δg )(x) = p
|G|
|G|
h∈G

h∈G

−1

Since j is a bijection there exists an inverse map j
: Ĝ → G. Then, for every
χ ∈ Ĝ we have


1 X
1 X
1
P (fg )(j −1 (χ)) =
j(h)(g)χ(h) =
ĵ(g)(h)χ(h) = p F ĵ(g) (χ).
|G|
|G|
|G|
h∈G

h∈G

On the other hand we have
P (δg )(j

−1

(χ)) = δg (p(j

−1

(χ))) =


1

if g = p(j −1 (χ)),

0

if g 6= p(j −1 (χ)).


It follows that for every χ ∈ Ĝ,

p
 |G| if g = p(j −1 (χ)),

F ĵ(g) (χ) =

0
if g 6= p(j −1 (χ)).


(3.1)

Now, by the Fourier inversion formula and relation (3.1) we have that for every
x∈G

1 X 
ĵ(g)(x) = p
F ĵ(g) (χ)χ(x) = α(x),
|G|
χ∈Ĝ

−1

where α = j(p (g)). Hence, ĵ = j ◦ p−1 and thus ĵ(G) ⊂ Ĝ. Now, by Theorem 3.1
it follows that j is a homomorphism as well as p = ĵ −1 ◦ j.

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER TRANSFORM

5

Conversely, suppose that j is an isomorphism and let f ∈ CG . Then, for every
g ∈ G we have
P (f )(g) = (j̃ ◦ F)2 (f )(g) = (j̃ ◦ F)(j̃(F(f ))(g) = j̃(F(j̃(F(f )))(g)
1 X
j̃(F(f ))(h) · (j(g))(h)
= F(j̃(F(f )))(j(g)) = p
|G| h∈G
1 X
=p
F(f )(j(h)) · (j(g))(h)
|G| h∈G
1 X 1 X
p
f (l) · (j(h))(l) · (j(g))(h)
=p
|G| h∈G |G| l∈G
1 XX
f (l) · (j(h))(l) · (j(g))(h)
=
|G|
l∈G h∈G
1 XX
=
f (l)ĵ(l)(h)j(g)(h)
|G|
l∈G h∈G
X
1 X
f (l)
ĵ(l)j(g)(h).
=
|G|
l∈G

h∈G

From the orthogonality relations we have that

|G| if ĵ(l) = j(g),
X
ĵ(l)j(g)(h) =

h∈G
0 if ĵ(l) =
6 j(g).
Thus, for every g ∈ G, we have P (f )(g) = f (l) where l = ĵ −1 (j(g)). This shows
that P is a permutation and p = ĵ −1 ◦ j.

4. Examples
Example 4.1. Consider the additive group (Z/nZ)ad of the ring Z/nZ. So, starting
from this point we will denote the group operation by +. The multiplication will
denote the ring multiplication. Consider the standard isomorphism s : (Z/nZ)ad →
\ad defined by s(x)(y) = en (xy) where en (x) = e2πix/n . Then any other
(Z/nZ)
\ad has the form j = s◦h for some isomorphism
isomorphism j : (Z/nZ)ad → (Z/nZ)
h : (Z/nZ)ad → (Z/nZ)ad . The isomorphism h is defined by its value h(1) = l where
l and n are relatively prime. So, for all x, y ∈ Z/nZ
j(x)(y) = s(h(x))(y) = s(xl)(y) = en (xyl).
Now, since j is an isomorphism, we have that P = (j̃ ◦ F)2 is a permutation with
p = ĵ −1 ◦ j by Theorem 3.3. Calculations shows that p(x) = −x for all such j. This
shows that P 2 = (j̃ ◦ F)4 is the identity on CZ/nZ . Thus, the spectrum of j̃ ◦ F is
a subset of the set {1, −1, i, −i} of 4th roots of unity. In the next example we show
that the multiplicities of eigenvalues do depend on j, but not too much.
The following example is a particular case of Example 4.1.
Example 4.2. Consider the additive group (Z/pZ)ad where p is an odd prime. To
calculate the multiplicities of the eigenvalues in this case we use the multiplicative
characters of Z/pZ. The point is that j̃ ◦ F decomposes on 2 × 2 and 1 × 1 matrix
blocks in the bases of multiplicative characters. It is well known but we do the

6

JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS

corresponding calculation here to point out the dependence on j, and that we may
calculate the possible spectra of j̃ ◦ F without calculating Gauss sums.
A multiplicative character is a function ψ : G → C such that ψ(xy) = ψ(x)ψ(y)
for all x, y ∈ Z/pZ and ψ(0) = 0. Fix a generator g of a multiplicative group of
Z/pZ. Define ψ0 , ψ1 , . . . , ψp−2 : G → C by setting ψa (0) = 0, ψa (g b ) = e2πiab/(p−1) .
It is trivial to verify that ψa , a = 0, 1, . . . , p − 2 are multiplicative characters and
account for all such. Setting

 1 if x = 0,
δ0 (x) =

0 if x 6= 0,
G
we have that β
√ = (δ0 , αψ0 , αψ1 , . . . , αψp−2 ) is an orthonormal ordered basis of C ,
where α = 1/ p − 1.
b be an isomorphism. Then, from Example 4.1, we have that j := jl
Let j : G → G
for some l ∈ {1, 2, . . . , p − 1}, where jl (x)(y) = ep (xyl). It follows that for every
f ∈ CG and for all x ∈ G,
1 X
1 X
j̃(F(f ))(x) = F(f )(jl (x)) = √
f (y)jl (x)(y) = √
f (y)ep (xyl).
p
p
y∈G

y∈G

In particular, we have that
1
1
1
1
j̃(F(δ0 ))(x) = √ = √ δ0 (x) + √ ψ0 (x) = √ δ0 (x) +
p
p
p
p

√

p−1
√ αψ0 (x)
p

for all x ∈ G.
Similarly, from the orthogonality relations we have that

1
6 0,

 − √p if x =
j̃(F(ψ0 ))(x) =

 p−1
√
if x = 0,
p
p−1
1
= √ δ0 (x) − √ ψ0 (x)
p
p
and so

√
j̃(F(αψ0 ))(x) =

1
p−1
√ δ0 (x) − √ αψ0 (x).
p
p

It follows, that the matrix of j̃ ◦ F relative to β begins in the “northwest” with
the 2 × 2 matrix block
√
 1

p−1
√


√

p

p−1
√
p

√

p

− √1p


.

(4.1)

Now, let ψ 6= ψ0 be a multiplicative character on G. Then, for all x ∈ G we have
that
1 X
j̃(F(ψ))(x) = √
ψ(y)ep (xyl).
p
y∈G

If x = 0, then ep (0yl) = 1 and j̃(F(ψ))(0) =
equality follows by the orthogonality relations.

√1
p

P

y∈G

ψ(y) = 0 where the last

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER TRANSFORM

7

If x 6= 0, then
1 X
j̃(F(ψ))(x) = √
ψ(x−1 y)ep (ly) = Sl (ψ) · ψ(x),
p
y∈G

where Sl (ψ) =

√1
p

P

y∈G

ψ(y)ep (ly).

If ψ 6= ψ, we have that (j̃ ◦ F)(ψ) = Sl (ψ) · ψ and (j̃ ◦ F)(ψ) = Sl (ψ) · ψ.
Relative to the pair (ψ, ψ), we get a 2 × 2 matrix block of the form


0
Sl (ψ)
.
Sl (ψ)
0
To determine the spectra of this matrix we must determine the product Sl (ψ)·Sl (ψ).
We have that
1 X
1 X
ψ(x)ep (lx)ψ(y)ep (ly) =
ep (l(x + y))ψ(x)ψ(y)
Sl (ψ) · Sl (ψ) =
p
p
x,y∈G

x,y∈G

X
1X
ep (la) ·
ψ(a − y)ψ(y)
=
p
a∈G

y∈G

X
1X
1 X
ψ(−y)ψ(y) +
ep (la)
ψ(a − y)ψ(y).
=
p
p
×
y∈G

y∈G

a∈G

Since ψ(0) = 0, for the first sum we have that
X
X
X
ψ(−y)ψ(y) =
ψ(−y)ψ(y)−1 =
ψ(−1) = (p − 1)ψ(−1).
y∈G×

y∈G

y∈G×

From the orthogonality relations, it follows that

X
X a
ψ(a − y)ψ(y) =
− 1 = −ψ(−1)
ψ
y
×
y∈G

×

since for y ∈ G , x =
Thus,

y∈G

a
y

− 1 if and only if y =

a
x+1

for x ∈ G − {−1}.



p−1
ψ(−1) X
p−1 1
ψ(−1) −
+
= ψ(−1),
Sl (ψ) · Sl (ψ) =
ep (la) = ψ(−1)
p
p
p
p
×
a∈G

P

since
a∈G× ep (la) = −1 by the orthogonality relations. It follows that Sl (ψ) ·
Sl (ψ) = ±1 because of 1 = ψ(1) = (ψ(−1))2 . Since ψk (g r ) = e2πirk/(p−1) and
g (p−1)/2 = −1, we have that ψ(−1) = −1 for p−1
2 nontrivial multiplicative characp−3
ters and ψ(−1) = 1 for p−1
−
1
=
nontrivial
multiplicative characters.
2
2
x
If ψ = ψ, then ψ(x) = ψ p−1 = ( p ) is the Legendre symbol of x mod p. In
2
P
P
this case, Sl (ψ) = √1p y∈G ep (ly)( yp ) = √1p y∈G ep (ly 2 ) where the last equality
follows by Theorem 4.17 of [3]. From the consideration above, we know that


  1 if p ≡ 1 (mod 4),
−1
Sl (ψ p−1 )2 =
=
2

p
−1 if p ≡ 3 (mod 4).

8

JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS

Thus,
Sl (ψ p−1 ) =
2


 ±1

if p ≡ 1

(mod 4),

±i

if p ≡ 3

(mod 4).



(4.2)

So, we just need to choose the proper sign. Notice that Sl (ψ) = ψ(l)S1 (ψ). It
follows that any sign in Eq.4.2 is possible depending on whether l is a quadratic
residue mod p or not. We know that all two possibilities happen, but we are not
able to decide which one corresponds to which l without evaluating the Gauss sum.
The evaluation of the Gauss sum is less elementary than the calculations used here.
Finally, since (j̃ ◦ F)(ψ) = Sl (ψ) · ψ, relative to the pair (ψ, ψ) we get a 1 × 1
matrix of the form (Sl (ψ)).
It follows that the characteristic polynomial of j̃ ◦ F is
p−3

2

(λ − 1)

2
Y

(λ2 − ψj (−1))(λ ± 1), if p ≡ 1

mod 4

(λ2 − ψj (−1))(λ ± i), if p ≡ 3

mod 4

j=1

and
p−3

2

(λ − 1)

2
Y

j=1

where the choice of signs depend on l and, consequently, j.
Let R4 = {1, −1, i, −i} be a group of 4th roots of unity and Z[R4 ] its group
algebra. We write an element a ∈ Z[R4 ] as a = a1 + a−1 [−1] + ai [i] + a−i [−i].
Where we suppose that [1] = 1. The sum in Z[R4 ] is defined by
(a1 + a−1 [−1] + ai [i] + a−i [−i]) + (b1 + b−1 [−1] + bi [i] + b−i [−i]) =
(a1 + b1 ) + (a−1 + b−1 )[−1] + (ai + bi )[i] + (a−i + b−i )[−i]
and the multiplication is the prolongation of the multiplication in R4 ([α][β] = [αβ])
by linearity. We say that a ∈ Z[R4 ] represents the spectrum of an operator A
(A4 = id) if aα is the multiplicity of the eigenvalue α. Let s = 1 + [−1] + [i] + [−i]
Theorem 4.3. Let p > 2 be a prime.
p−1
If p ≡ 1 mod 4 then either p−1
4 s + 1 or 4 s + [−1] represents the spectrum of
Zp
Zp
j̃ ◦ F : C → C . Both cases are possible depending on j.
p+1
If p ≡ 3 mod 4 then either p+1
4 s − [i] or 4 s − [−i] represents the spectrum of
j̃ ◦ F : CZp → CZp . Both cases are possible depending on j.
Example 4.4. Consider the abelian group G = (Z/nZ)m . Then, the automorphism
group of G is GLm (Z/nZ), the group of invertible m × m matrices in Z/nZ. Let
h·, ·i : G × G → Z/nZ be the natural scalar product on G:
hh, gi = h1 g1 + h2 g2 + · · · + hm gm .
For an isomorphism j : G → Ĝ, there is Mj ∈ GLm (Z/nZ) such that
j(g)(h) = en (hh, Mj gi).
We can check that Mĵ = −Mjt where Mjt denotes the transpose matrix of Mj . It
follows that, in this case, p(g) = −(Mjt )−1 Mj g.

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER TRANSFORM

9

Lemma 4.5. Let Mj 0 = T t Mj T for some T ∈ GLm (Z/nZ). Then j˜0 ◦ F is unitary
equivalent to j̃ ◦ F. The unitary equivalence comes from base change in (Z/nZ)m
by T .
If M t = M , then p(g) = −g for all g ∈ G and, hence, P 2 = id. As in Example 4.1
it follows that the set of eigenvalues of j̃ ◦ F is a subset of R4 . Let n = p > 2
be a prime. Then it is not hard to calculate the spectrum of j̃ ◦ F. Indeed, if
M ∈ GLm (Z/pZ) is symmetric (M t = M ), then there exists T ∈ GLm (Z/pZ) such
that


1
0


1


M = Tt 
 T,
.
..


0
l
(see [1], Theorem 9.4). So, changing the base in (Z/pZ)m , we get that j̃ ◦ F is
isomorphic to a tensor product of m Fourier transforms of Z/pZ, all but one with
l = 1. We need the following lemma.
Lemma 4.6. Let s = 1 + [−1] + [i] + [−i], k ∈ Z and α ∈ R4 .
• Let a, b ∈ Z[R4 ] represent the spectrum of A and B, respectively. Then ab
represents the spectrum of A ⊗ B.
• s · [α] = s.
• sm = 4m−1 s.
m
• (ks + [α])m = (4k+1)4 −1) s + [αm ].
m
m
• (ks − [α])m = (4k−1) 4−(−1) s + (−1)m [αm ].
This lemma with Theorem 4.3 imply the following corollary.
Corollary 4.7. Let p > 2 be a prime and the isomorphism j : (Z/pZ)m → (Z/pZ)m
be symmetric (with Mjt = Mj ).
m
If p ≡ 1 mod 4 then p 4−1 s + [±1] represents the spectrum of j̃ ◦ F. Both cases
are possible, depending on the choice of j.
m
m
If p ≡ 3 mod 4 then p −(−1)
s+(−1)m [±(i)m ] represents the spectrum of j̃ ◦F.
4
Both cases are possible, depending on the choice of j.
In a similar way, if M t = −M then p = id for all g ∈ G. In this case, the
eigenvalues of j̃ ◦ F are ±1.
In principle, using multiplicative characters we can calculate spectra of different
Fourier transforms on (Z/pZ)m . As multiplicative characters with δ0 form a basis
m
on CZ/pZ , the tensor products of these characters form a basis on C(Z/pZ) . We
show how to use it by an example. First of all, we remind that if f1 , f2 ∈ CZ/pZ ,
2
then f1 ⊗ f2 ∈ C(Z/pZ) is defined as (f1 ⊗ f2 )(x1 , x2 ) = f1 (x1 )f2 (x2 ).
Example 4.8. Let G = (Z/pZ)2 and j : G → G be defined by


1 0
Mj =
.
1 1
Notice that Mj is not symmetric. In this case we may find a transformation T ∈
GL2 (Z/pZ) such that




1 0
0 1
=T
T t,
1 1
k 0

10

JAVIER DIAZ-VARGAS, LEV GLEBSKY, AND CARLOS JACOB RUBIO-BARRIOS
√

where k = 1− 2 −3 . Generally speaking, k is not necessarily in Z/pZ but may belong
to its quadratic extension. Let p ≡ 1 mod 3. Then k ∈ Z/pZ. We only consider
this case. The other case require additional considerations. So, let p ≡ 1 mod 3.
Then by changing the base in (Z/pZ)2 , we obtain


0 1
M̃j =
.
k 0
So, we have to study j̃ ◦ F with j defined by M̃j . Let ψ1 , ψ2 be nontrivial multiplicative characters on Z/pZ. Then (j̃ ◦ F)(ψ1 ⊗ ψ2 ) = S(ψ1 )S(ψ2 )ψ2 (k)(ψ2 ⊗ ψ1 ).
So, for non-trivial multiplicative characters, we have the following two cases:
I: ψ1 6= ψ2 . Then the restriction of j̃ ◦ F on subspace spanned by
ψ1 ⊗ ψ2 , ψ2 ⊗ ψ1 is


0
S(ψ1 )S(ψ2 )ψ1 (k)
.
0
S(ψ1 )S(ψ2 )ψ2 (k)
q
The corresponding eigenvalues are λ = ± ψ1 (−k)ψ2 (−k).
II: For nontrivial multiplicative characters ψ, the vectors ψ ⊗ ψ are eigenvectors with eigenvalues λ = ψ(−k).
We are left with the study of√tensor products involving
δ and trivial multiplicative
√ 0
p−1
p+1
character ψ0 . Let v1 = δ0 + √p−1 ψ0 and v−1 = δ0 − √p−1 ψ0 . Notice that vα is an
α-eigenvector of one-dimensional Fourier transform, see Eq.4.1.
III: Let ψ be a nontrivial multiplicative character. On subspaces spanned by
vα ⊗ ψ, ψ ⊗ vα , the j̃ ◦ F acts as


0
S(ψ)
α
.
S(ψ)ψ(k)
0
q
The corresponding eigenvalues are λ = ± ψ(−k).
IV: The restriction of j̃ ◦ F on 1-dimensional subspace spanned by vα ⊗ vα ,
is the identity operator, that is, λ = 1.
V: The restriction of j̃ ◦ F on subspace spanned by v1 ⊗ v−1 , v−1 ⊗ v1 is


0 −1
.
−1 0
The corresponding eigenvalues are λ = ±1.
Notice that (−k)3 = 1. It follows that there are
• p−4
3 nontrivial multiplicative characters ψ on Z/pZ with ψ(−k) = 1;
2πi
p−1
• 3 nontrivial characters with ψ(−k) = e 3 ;
− 2πi
3 .
• p−1
3 nontrivial characters with ψ(−k) = e
Based on the above considerations, we get the following theorem.
Theorem 4.9. Let p > 2 be a prime and j : (Z/pZ)2 → (Z/pZ)2 be an isomorphism
with


1 0
Mj =
.
1 1
Then, the eigenvalues of j̃ ◦F are the 6th roots of unity. If p ≡ 1 mod 3 and p ≥ 7,
then the multiplicities of the eigenvalues are the following:

WHAT IS A TRUE SPECTRA OF A FINITE FOURIER TRANSFORM

λ
+1
−1
e
e

− 2πi
6

−e
−e

2πi
6

2πi
6

− 2πi
6

11

multiplicity
1
2
1
2
3
2
3
2
3
2
3
2

(p−4)(p−7)
9
(p−4)(p−7)
9
(p−4)(p−1)
9
(p−4)(p−1)
9
(p−4)(p−1)
9
(p−4)(p−1)
9

+
+
+
+

(p−1)2
9
(p−1)2
9
2 p−1
3
2 p−1
3

+p−1
+ 2 p−4
3 +1

+p−1
+p−1

References
[1] Finkbeiner D.: Introduction to Matrices and Linear Transformations. W. H. Freeman and
Company (1960). 4
[2] Luong B.: Fourier Analysis on Finite Abelian Groups. Birkhäuser (2009). 2
[3] Nathanson M.: Elementary Methods in Number Theory. Graduate Texts in Mathematics.
Springer (2000). 4.2
Universidad Autónoma de Yucatán
E-mail address: javier.diaz@correo.uady.mx
Universidad Autónoma de San Luis Potosı́
E-mail address: glebsky@cactus.iico.uaslp.mx
Universidad Autónoma de Yucatán
E-mail address: carlos.rubio@correo.uady.mx

