Page 360 - Matrix Analysis & Applied Linear Algebra

356 Chapter 5 Norms, Inner Products, and Orthogonality
5.8 DISCRETE FOURIER TRANSFORM

2 n−1
Fora positive integer n, the complex numbers 1,ω,ω ,...,ω , where
2π 2π
2πi/n
ω =e = cos +i sin
n n
n
are called the n th roots of unity because they represent all solutions to z =1.
Geometrically, they are the vertices of a regular polygon of n sides as depicted
in Figure 5.8.1 for n =3 and n =6.

ω ω 2 ω

1 ω 3 1

ω 2 ω 4 ω 5

n = 3 n = 6
Figure 5.8.1
k
The roots of unity are cyclic in the sense that if k ≥ n, then ω = ω k (mod n) ,
where k (mod n) denotes the remainder when k is divided by n—for example,
3
7
2
8
9
6
when n =6,ω =1,ω = ω, ω = ω ,ω = ω ,....

2
The numbers 1,ξ,ξ ,...,ξ n−1 , where
2π 2π
−2πi/n
ξ =e = cos − i sin = ω
n n
are also the n th roots of unity, but, as depicted in Figure 5.8.2 for n =3 and
n =6, they are listed in clockwise order around the unit circle rather than
counterclockwise.
ξ 2 ξ 4 ξ 5
1 ξ 3 1

ξ ξ 2 ξ

n = 3 n = 6

Figure 5.8.2
The following identities will be useful in our development. If k is an integer,
k k
k 2
then 1 = |ξ | = ξ ξ implies that
k
k
ξ −k = ξ = ω . (5.8.1)