Building the DFT

I. Cnop
Vrije Universiteit Brussel
icnop@vub.ac.be

Sum of a geometric progression.

Recall the shorthand for directions in the plane

directions[
        n_] := (E^(I Range[n] 2 π/n ))

coords[z_] := {Re[z], Im[z]}

Take uniform lengths

coeffList = Table[1, {13}]

n =  Length[coeffList]

Multiply

Map[coords, coeffList directions[n] // N];

ListPlot[%, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Add

Making partial sums by adding these points is done wit a built-in  Mathematica  command

points = FoldList[Plus, {0, 0}, %%];

ListPlot[points, PlotJoined -> True, 
      AspectRatio -> Automatic, 
      PlotRange -> {{-4, 5}, {-2, 5}}]

The final result

We finally get back in the origin

The sum of all directions is zero

Maybe it is even more apparent if we add segments

Map[Line, 
        Transpose[{Table[{0, 0}, {n}], 
            Map[coords, coeffList directions[n]]}]];

Show[Graphics[%], AspectRatio -> Automatic, 
      PlotRange -> {{-4, 5}, {-2, 5}}]

The endpoints of the segments constitute the vertices of theregular  n -gon. 
Joining all segments as matchsticks one after the other draws the bigger   n - gon in the previous Graphics cell.

List programming for a sum

Obtaining the final sum is easiest with a   Dot  product command: try

afew = {a, b, c, d}
m = Length[afew]
counts = Range[m]
afew counts
afew . counts

We have performed

coeffList = Table[1, {13}];

n =  Length[coeffList];

coeffList . directions[n]

FullSimplify[%]

This will be used below to prove the inverse theorem

Discrete Fourier transform of a list.

Vectors with arbitrary lengths

We recommend that this buildup be first performed with a list of positive numbers for lengths. 
However it works as well with negative lengths; in this case the spokes representing vectors are sticking backward from the direction.

coeffList = { .2,  .8, - .2,  .6, - .9, 
          1, - .6,  .4, - .6,  .5, - .9, 1,  .3};

% // TableForm

For later reference, here is their sum:

Plus @@ coeffList

Start by using a fixed prime number

n =  Length[coeffList]

For esthetical reasons we use a prime number of directions

This is necessary to have the visual representations below.

Remark: we will explain later what is different if   n   is no longer a prime. 
Such numbers are actually used in practice and in a FFT (fast Fourier transform) version of the DFT, n   is a power of  2 .

Map[coords, coeffList directions[n] // N];

We now plot the endpoints of the vectors with lengths in  coeffList

Remark: since some numbers are negative, some of these endpoints lie on the other side of the origin, back from the original ray.

ListPlot[%, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Adding vectors one by one

produces a kind of walk from the origin:

points = FoldList[Plus, {0, 0}, %%];

ListPlot[%, PlotJoined -> True, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Map[Line, 
        Transpose[{Table[{0, 0}, {n}], 
            Map[coords, coeffList directions[n]]}]];

Show[Graphics[%], AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

This can also be done in colours corresponding to directions. We may even draw arrows using the

<< Graphics`Arrow`

package. This is not necessary here since we know all vectors start from the origin.

Selection of the k-th harmonic

Start by counting angles by  multiples   of   a fixed number    k   :

mixDirections[n_, 
        k_] := (E^(I k Range[n] 2 π/n ))

We are in fact using multiplication in  (Subscript[U, n])

Table[Mod[k Range[13], 13], {k, 13}] // TableForm

We will use this way of counting to make new sums.

Selection of the 2-nd harmonic

Map[coords, coeffList mixDirections[n, 2] // N];

ListPlot[%, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

makes two turns around the origin and is grouping even-numbered and odd-numbered lengths from coeffList before adding:

points = FoldList[Plus, {0, 0}, %%];

ListPlot[%, PlotJoined -> True, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Both end result and partial sums are strikingly different. Again we may also add lines

Map[Line, 
        Transpose[{Table[{0, 0}, {n}], 
            Map[coords, coeffList mixDirections[n, 2]]}]];

Show[Graphics[%], AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Selection of the 3-rd harmonic

Counting by three still gives a new result:

Map[coords, coeffList mixDirections[n, 3] // N];

ListPlot[%, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

points = FoldList[Plus, {0, 0}, %%];

ListPlot[%, PlotJoined -> True, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Map[Line, 
        Transpose[{Table[{0, 0}, {n}], 
            Map[coords, coeffList mixDirections[n, 3]]}]];

Show[Graphics[%], AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Selection of the 4-th harmonic

Map[coords, coeffList mixDirections[n, 2] // N];

ListPlot[%, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

points = FoldList[Plus, {0, 0}, %%];

ListPlot[%, PlotJoined -> True, AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

Map[Line, 
        Transpose[{Table[{0, 0}, {n}], 
            Map[coords, coeffList mixDirections[n, 4]]}]];

Show[Graphics[%], AspectRatio -> Automatic, 
      PlotRange -> {{-2, 2}, {-2, 2}}]

The 0-th harmonic

Is just the sum of all entries in coeffList

Animations are provided

Do[
Show[
        Graphics[
Map[Line, 
            Transpose[{Table[{0, 0}, {n}], 
                Map[coords, 
                  coeffList mixDirections[n, k]]}]]
], 
        AspectRatio -> Automatic, 
        PlotRange -> {{-2, 2}, {-2, 2}}], {k, n}]

Run these slowly.

Definition of the DFT

After division by the square root of  n,  the array of the all (complex)sums, for all harmonics, is called  the Discrete Fourier transform of  coeffList.

The command for obtaining this DFT is called Fourier in  Mathematica .

Fourier[coeffList] // TableForm

Here are the sums we have obtained:

Chop[(Sqrt[n]) % ] // TableForm

It is possible to check coordinates by hand in some of the graphs above.

Recovering the original coefficient List from these sums.

Introduction

We may ask now whether given all these   n   sums we can recover the original entries in  the original list we called coeffList. It boils down to solve an    n x n   system of linear equations with complex coefficients. Indeed, the coefficients in the system of equations are the   n  directions in the plane. These are repeated in each equation in a different order according to the way of counting in the harmonics. Solving such a system looks like a huge task, and at this point the reader may not know yet how to perform this. Only to know that a unique solution exists, one has to compute a  n x n   determinant of  all directions and be sure this determinant is not zero.

Fortunately, we can do this in a different way.
The only thing we have to know is the sum of the geometric progression at the start of this text.

Reversing directions

Recall that for the   k   harmonic we used directions in the following order

mixDirections[n_, 
        k_] := (E^(I k Range[n] 2 π/n ))

obtaining the   k  th sum. Let us write all these sums as

Array[s, {n}]

and use them as a new list of "lengths" replacing coeffList. 

These we are going to multiply by directions measured clockwise around the origin. Since these  sums are no longer real numbers, the vectors obtained do not point along direction (or in the opposite direction) but may point anywhere.
Drawing a graph gives no information, but we can still add these vectors in the plane and obtain new sums. 
For the    j th   harmonic, we use

mixDirections[n, - j]

e.g.

j = 4; mixDirections[n, - j]

The sum corresponding to this   4  th harmonic is

Array[s, {n}] . mixDirections[n, - j]

The result will be    n   times the   j th entry in coeffList.

Experimenting

Proving this result

Start with any coeffList

coeffList = Array[c, {n}]

Replace each  s[k]  by its value and write all new sums

Table[coeffList . mixDirections[n, k], {k, n}]

(Recall that we set   j  = 4  , but the following can be repeated for any   j )

Expand[% . mixDirections[n, - j]]

We group according to the numbering of the   c   and make a list of coefficients

Table[Coefficient[%, c[m]], {m, n}]

Except for one entry which is precisely   n   (can you find it?)  all the other sums are precisely the sum of all directions around the origin. By the heometric result we know that these add up to zero and  Mathematica  knows this too:

FullSimplify[%]

The final result is    n   times   c[j]  , and can be repeated for any  j .

Conclusion

\(If\ we\ first\ compute\ the\ \ \ DFT\ \ sums\ of\ the\ list\ \ \ {c[
          1]\ , \ \ \ \(\(...\)\(.\)\)\ \ , \ 
        c[n]}\ \ \((including\ the\ division\ \ by \@ n)\), 
\ 
    and\ next\ compute\ the\ \ \ \ InverseDFT\ sums\ of\ this\ list\ of\ sums\ using\ the\ directions\ with\ reversed\ angles\ \((again\ including\ the\ division\ \ by \@ n)\), 
\ 
    we\ obtain\ \ the\ initial\ list\ \(\({c[
            1]\ , \ \ \ \(\(...\)\(.\)\)\ \ , \ 
          c[n]}\)\(\ \)\(.\)\)\)

The corresponding  Mathematica  commands are

Fourier

InverseFourier

Numbers of data may be non-prime.

The same reasoning can be performed when  n  is not a prime number. 
For building   k-th harmonics with   k  and   n   no longer relatively prime, graphs are no longer clear. The number of spokes used in some harmonics is less than the original number of directions, and several vectors may be pointing in the same direction.

Task

Replay the second section after skipping one entry in coeffList (so that   n  = 12)  to convince oneself.