The DTFS
is just a change of basis in
CN
N
.
To start, we have
fn
f
n
in terms of the standard basis.
fn=f0
e
0
+f1
e
1
+…+fN−1
e
N

1
=∑k=0n−1fkδk−n
f
n
f
0
e
0
f
1
e
1
…
f
N
1
e
N

1
k
0
n
1
f
k
δ
k
n
(1)
f0f1f2⋮fN−1=f000⋮0+0f10⋮0+00f2⋮0+…+000⋮fN−1
f
0
f
1
f
2
⋮
f
N
1
f
0
0
0
⋮
0
0
f
1
0
⋮
0
0
0
f
2
⋮
0
…
0
0
0
⋮
f
N
1
(2)
Taking the DTFS, we can write
fn
f
n
in terms of the sinusoidal Fourier basis
fn=∑k=0N−1
c
k
ei2πNkn
f
n
k
0
N
1
c
k
2
N
k
n
(3)
f0f1f2⋮fN−1=
c
0
111⋮1+
c
1
1ei2πNei4πN⋮ei2πN(N−1)+
c
2
1ei4πNei8πN⋮ei4πN(N−1)+…
f
0
f
1
f
2
⋮
f
N
1
c
0
1
1
1
⋮
1
c
1
1
2
N
4
N
⋮
2
N
N
1
c
2
1
4
N
8
N
⋮
4
N
N
1
…
(4)
We can form the basis matrix (we'll call it
WW here instead of
BB) by stacking the basis vectors
in as columns
W=(
b
0
n
b
1
n…
b
N

1
n
)=(
111…1
1ei2πNei4πN…ei2πN(N−1)
1ei4πNei8πN…ei2πN2(N−1)
⋮⋮⋮⋮⋮
1ei2πN(N−1)ei2πN2(N−1)…ei2πN(N−1)(N−1)
)
W
b
0
n
b
1
n
…
b
N

1
n
1
1
1
…
1
1
2
N
4
N
…
2
N
N
1
1
4
N
8
N
…
2
N
2
N
1
⋮
⋮
⋮
⋮
⋮
1
2
N
N
1
2
N
2
N
1
…
2
N
N
1
N
1
(5)
with
b
k
n=ei2πNkn
b
k
n
2
N
k
n
the entry in the kth row and nth column is
W
j
,
k
=ei2πNkn=
W
n
,
k
W
j
,
k
2
N
k
n
W
n
,
k
So, here we have an additional symmetry
(W=WT)⇒(WT¯=W¯=1NW1)
W
W
W
W
1
N
W
(since
b
k
n
b
k
n
are orthogonal)
 WW
has the following properties:

WW is Vandermonde: the
nnth column of
WW is a polynomial in
W
N
n
W
N
n

WW is symmetric:
W=WT
W
W

1NW
1
N
W
is unitary:
(1NW)1NWH=1NWH(1NW)=I
1
N
W
1
N
W
H
1
N
W
H
1
N
W
I

1NW¯=W1
1
N
W
W
1
, the IDFT matrix.

For NN a power of 2, the FFT
can be used to compute the DFT using about
N2log2N
N
2
2
N
rather than
N2
N
2
operations.