Matrix formulation of the Fourier transform of a sequence – example

Taken from an email conversation with Gary W. Adamson on February 14 2012.

Just one thing, (the number theoretic) Schramm triangle “B” or “chaotic set” (?) is:

cos(2*Pi*1/1),
cos(2*Pi*1/2), cos(2*Pi*2/2),
cos(2*Pi*1/3), cos(2*Pi*2/3), cos(2*Pi*3/3),
cos(2*Pi*1/4), cos(2*Pi*2/4), cos(2*Pi*3/4), cos(2*Pi*4/4),
cos(2*Pi*1/5), cos(2*Pi*2/5), cos(2*Pi*3/5), cos(2*Pi*4/5), cos(2*Pi*5/5),
cos(2*Pi*1/6), cos(2*Pi*2/6), cos(2*Pi*3/6), cos(2*Pi*4/6), cos(2*Pi*5/6), cos(2*Pi*6/6),
cos(2*Pi*1/7), cos(2*Pi*2/7), cos(2*Pi*3/7), cos(2*Pi*4/7), cos(2*Pi*5/7), cos(2*Pi*6/7), cos(2*Pi*7/7),
=B

While the (numerical method used in signal processing) Fourier array “F” is a square array:

cos(-2*Pi*(1-1)*(1-1)/4), cos(-2*Pi*(2-1)*(1-1)/4), cos(-2*Pi*(3-1)*(1-1)/4), cos(-2*Pi*(4-1)*(1-1)/4)
cos(-2*Pi*(1-1)*(2-1)/4), cos(-2*Pi*(2-1)*(2-1)/4), cos(-2*Pi*(3-1)*(2-1)/4), cos(-2*Pi*(4-1)*(2-1)/4)
cos(-2*Pi*(1-1)*(3-1)/4), cos(-2*Pi*(2-1)*(3-1)/4), cos(-2*Pi*(3-1)*(3-1)/4), cos(-2*Pi*(4-1)*(3-1)/4)
cos(-2*Pi*(1-1)*(4-1)/4), cos(-2*Pi*(2-1)*(4-1)/4), cos(-2*Pi*(3-1)*(4-1)/4), cos(-2*Pi*(4-1)*(4-1)/4)

=F

which has the general form:

F(n,k) = cos(-2*Pi*(k-1)*(n-1)/N)

where capital “N” is the dimension of the 4*4 matrix or the length of the sequence to be

Fourier transformed, and n=1,2,3… and k=1,2,3…

(The definition in wikipedia “Discrete Fourier Transform”

is exactly the same but with shifted indexes for “n” and “k”.

Also, I would have written a 7*7 array as in the example with the Schramm triangle

but it does not fit on the screen in a mail, so I use a 4*4 array as example instead.)

So to take the Fourier transform of a sequence

x=2,3,1,5

just multiply the matrix “F” with the vector “x”

2*cos(-2*Pi*(1-1)*(1-1)/4), 3*cos(-2*Pi*(2-1)*(1-1)/4), 1*cos(-2*Pi*(3-1)*(1-1)/4), 5*cos(-2*Pi*(4-1)*(1-1)/4)
2*cos(-2*Pi*(1-1)*(2-1)/4), 3*cos(-2*Pi*(2-1)*(2-1)/4), 1*cos(-2*Pi*(3-1)*(2-1)/4), 5*cos(-2*Pi*(4-1)*(2-1)/4)
2*cos(-2*Pi*(1-1)*(3-1)/4), 3*cos(-2*Pi*(2-1)*(3-1)/4), 1*cos(-2*Pi*(3-1)*(3-1)/4), 5*cos(-2*Pi*(4-1)*(3-1)/4)
2*cos(-2*Pi*(1-1)*(4-1)/4), 3*cos(-2*Pi*(2-1)*(4-1)/4), 1*cos(-2*Pi*(3-1)*(4-1)/4), 5*cos(-2*Pi*(4-1)*(4-1)/4)

=F . x

which when multiplied is equal to:

2, 3, 1, 5
2, 0, -1, 0
2, -3, 1, -5
2, 0, -1, 0

Then take row sums and you get a new vector capital “X”:

X=11, 1, -5, 1

We then say that upper case “X” is the Fourier transform of lower case “x”

———————————————————————–

This above is called the matrix formulation of the Discrete Fourier Transform.

The default Fourier (cosine) transform in Mathematica would be:

Re[Fourier[{2, 3, 1, 5}]

Which can be entered into Wolfram Alpha.

But the Mathematica code for the matrix formulation of the
Fourier (cosine) transform I tried to explain in the previous mail, is:

Re[Fourier[{2, 3, 1, 5}, FourierParameters -> {1, -1}]]

where
x = 2, 3, 1, 5

But Wolfram Alpha does not accept “FourierParameters” command
so to get the same result:
X = 11, 1, -5, 1

you have to use the Wolfram Alpha line:

Re[Fourier[{2, 3, 1, 5}]]*Total[{2, 3, 1, 5}]/Re[Fourier[{2, 3, 1, 5}]][[1]]

which gives the answer 11, 1, -5, 1

“Re” stands of course for real part, while “Im” would gives imaginary part.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.