The last few months, I have been blogging about F#. While I am a big fan of F#, I would like to part from that discussion to talk about yet another topic that interests me. I have been trying for a while to understand the Fourier Transform; unfortunately, I often feel like a deer staring into headlights when I look at the standard Fourier Transform summation formula. I suppose the only way for me to really get this is to take it a step at a time and start with something *relatively* basic such as M-Roots.

When you were young, your teacher probably told you that the square root of a number M was some number N that when multiplied by itself equaled M. Your teacher may not have used those words, but may have said something like “The square root of sixteen is four because four times four equals sixteen and the square root of nine is three because three times three equals nine."

Hopefully, your teacher drove home the fact that this wasn’t the whole story. You probably know that in addition to the above, -3 * -3 = 9 and -4 * -4 = 16. So 9 doesn’t just have the square root of 3. It also has a square root of -3 and 16 doesn’t just have a square root of 4, it also has the square root of -4. In fact, for any Complex Number, there are exactly two square roots [1].

Okay, so what is a Complex Number? You probably already know this also, but a Complex Number contains a both a real and Imaginary Number. So what is an Imaginary Number? An Imaginary Number is basically what you get when you try to take the square root of a negative number. The square root of 100 is obviously 10 since 10 * 10 = 100, but what is the square root of -100? Uuuh, I-Dough-Know…

If you are new to Complex Numbers, you might try to guess that the square root of -100 is -10, but that doesn’t work since -10 * -10 = 100. So what is the square root of -100? Well, to solve that problem you might want to break it down. -100 can be expressed as -1 * 100 or better yet 100 * -1. Now, we can take the square root of (100 * -1) which is the same as $\sqrt{100}*\sqrt{-1}$

So what is $\sqrt{-1}$? To be honest,
I have no clue. I just know that most folks call that *i*.
What's *i*? Well that's the $\sqrt{-1}$
of course! Don't you know that :-) ? If you don't believe me
you can solve the equation in [2] on your own
time...

So then, from the above we have that the square root of -100 is $\sqrt{-1}*\sqrt{100}$ or $\sqrt{100}*\sqrt{-1}$ which is $\mathrm{10}*\sqrt{-1}$ which is simply: 10i.

So in this case, the Imaginary Number 10i can be represented as the Complex Number 0+10i because there is no real component and there are 10 units of the imaginary component [3].

So what is the point in mentioning Complex Numbers? Well, it has
to do with how many roots we can get for a number. Remember when
I said that for any Complex Number there are exactly two square
roots [1]? As it turns out, we can generalize
that statement and say that for any Complex Number there are exactly
M number of M^{th} roots. In [4], Dr. Smith says
“...the M^{th} root of a, which is written as a^{1/M}, is not
unique--there are M of them.” So with the help of Dr. Smith
(and others), we know that there are exactly two square roots for
any number, three cube roots, four fourth roots and so on. In
order to find all of these roots, we usually need Complex Numbers.

So it’s pretty obvious how to get the square root of a number.
In most cases, an intelligent person can just guess and get a
correct answer, but it gets harder when you have to calculate the
cube roots or maybe even the 4^{th} roots or the
128^{th} roots.
Fortunately, Dr. Smith presents a formula in his text that we can
use. So let's see if we can figure out how Dr. Smith derives that
presented formula...

At the beginning of his discussion, Dr. Smith says that any
Complex Number can be expressed as follows:
$z={re}^{\mathrm{j\theta}}$.

[Dr. Smith uses j to represent the square root of -1 instead of i.
This is fairly common practice. Both j and i generally mean the
same thing; however, I personally prefer to use the letter i and
will try to use i whenever possible from here out.]

When Dr. Smith says this, he basically means that any Complex
Number can be translated into polar cordinates where r is a
magnitude and iθ is a phase. If you want an example of how
this is so, you can follow [5] to see that a
Complex Number x + y*i* = r(cos θ + *i* sin θ). You can
then use Euler's Identity *mentioned* by Mr. Roelandts in [6] to substitute
e^{iθ} for (cos θ + *i* sin θ) and get the
final answer that z = x + y*i* = r*e^{iθ}
just like Dr. Smith said.

[In case you don't have time to read *all* of Mr. Roelandts' article,
you can look to the derivation section where you will find the
useful formula

e^{iθ}=cos θ + *i* sin θ

but please note that Mr. Roelandts uses x in his formula instead of
θ]

Now, with the formula
$z={re}^{\mathrm{i\theta}}$, goofy me thinks I can just take the root of both sides of the
equation to get the M roots, but that doesn't work because the
result will not have "k" which is an iteration constant you will
need to find all *M* of the M-Roots. Instead, Dr. Smith uses
Euler's Identity again to introduce "k" with a trick. Dr. Smith
says that since
e^{iθ}=cos θ + *i* sin θ that
e^{i2πk}=cos(2πk) + *i* sin(2πk).
Now, if you think for a minute, you will see that the new adjusted
equation always equals 1. No joke!!! I'm not about to prove it,
but try evaluating cos(2πk) + *i* sin(2πk) for numerous
integer values of k. You *should* get 1 every time.

So since e^{i2πk} always equals one, there isn't any harm
in multiplying it by any side or *both* sides of an equation. Dr.
Smith takes this step and comes up with:
z = *r**e*^{iθ}*e*^{i2πk}.

I you are intersted, you can then go to Dr. Smith's book
[4] to see finally how he takes the m^{th}
root of both sides to come up with the final equation.

Now, if you are like me. You *may* be starring at the equation
Dr. Smith presented wondering what in the world he just said.
In particular, I'm a bit rusty with Euler's Identity and polar
coordinates. What don't we
*try* and use Euler's Identity to get rid of that ugly *e*
constant. If you want to learn more about *e* you are welcome
to go to [7], but personally, I would just
prefer to send *e* on its way right now...

So in my usual style, I’m going to make a Huge Ugly Guess (HUG) and
hope that I am mathematically allowed to assign
$\frac{\theta +2\mathrm{\pi k}}{M}$
to the variable x. Then, I'm going to use Euler's Identity as
mentioned by Mr. Roelandts in [6] to try and
come up with a simplified version of the equation Dr. Smith
demonstrated. So anyway, if I apply Euler's Identity to the equation
Dr. Smith showed previously, then I *think* I get something like
this:

${z}^{\frac{1}{M}}={r}^{\frac{1}{M}}(\mathrm{cos}\frac{\theta +2\mathrm{\pi k}}{M}+i\mathrm{cos}\frac{\theta +2\mathrm{\pi k}}{M})$

Walla!!! *e* is gone. Now, M is the root "level" I am taking
which is 2 for square root, 3 for cube root and so on; therefore,
the value "M" is known. I know what 2π is - that's just some constant. Also,
k is all numbers between 0 and M-1. So I guess, I need to figure
out what *r* and θ are. Well, I *think* *r* is just
the magnitude of the Complex Number and θ is just the phase,
so I should be good to go. I *think* I have everything I need to
solve the equation now. So to drive this home, I think I should
try an example. People such as me like examples...

Let's try to find the four fourth roots of the number 16+0i (which
is also simply known as the real number 16). Before we even start,
we can already find two on them in our head. Two of the
4^{th} roots are 2 and -2 since 2*2*2*2 = 16 and
-2*-2*-2*-2=16. But Dr. Smith told us earlier that there should be
four fourth roots of any Complex Number. Since 16 is a special
case of the Complex Number 16+0i, we are missing two roots. How
would we find them? With the equation that Dr. Smith demonstrated
of course!!!

In that equation, we know that M is 4 and k is all integers from
0 to 3 inclusive. So we just need to find θ and *r* and
we will be set. In our particular case, we are lucky and θ
is 0 because we are dealing with a real number 16. You can look
back at Bourne's article [5] to verify this.
Also, because 16 is a real number we are in luck again and the
magnitude of *r* is simply 16. Again, you can review
[5] to see how to compute the magnitude of a
Complex Number. Lastly, we know that *i* is just the square root of
-1. So we finally have everything we need, so we just go a
pluggin...

For k=0 we get:

${z}^{\frac{1}{4}}={r}^{\frac{1}{4}}(\mathrm{cos}\frac{0+2\pi 0}{4}+i\mathrm{sin}\frac{0+2\pi 0}{4})$

For k=1 we get:

${z}^{\frac{1}{4}}={r}^{\frac{1}{4}}(\mathrm{cos}\frac{0+2\pi 1}{4}+i\mathrm{sin}\frac{0+2\pi 1}{4})$

For k=2 we get:

${z}^{\frac{1}{4}}={r}^{\frac{1}{4}}(\mathrm{cos}\frac{0+2\pi 2}{4}+i\mathrm{sin}\frac{0+2\pi 2}{4})$

And finally for k=3 we get...:

${z}^{\frac{1}{4}}={r}^{\frac{1}{4}}(\mathrm{cos}\frac{0+2\pi 3}{4}+i\mathrm{sin}\frac{0+2\pi 3}{4})$

For k=0 we obviously get 2 since the sine term automatically
cancels out and the cos term evaluates to one. This leaves us
with nothing more than the 4^{th} root of the real number 16 which
was obviously 2.

For k=2 we have a similar situation since the sin term cancels out
and the cos term evaluates to -1. So when the magnitude *r* is
raised the the
$\frac{1}{4}$
power, we get 2 which is then multipled by -1 to get the
final *real* result of -2.

Now, if we simplify the k=1 case above we get:

${z}^{\frac{1}{4}}={16}^{\frac{1}{4}}(\mathrm{cos}\frac{2\pi}{4}+i\mathrm{sin}\frac{2\pi}{4})$

which is also:

${z}^{\frac{1}{4}}=2(\mathrm{cos}\frac{\pi}{2}+i\mathrm{sin}\frac{\pi}{2})$

which leads to:
${z}^{\frac{1}{4}}=2(0+1i)$

or finally:

0 + 2*i*

I leave it as an exercise for the reader to show that the k=3 case
yields 0 - 2*i*, but you should intiutively know that this
happens because the sin(2π3/4) imaginary term will evaluate
to -1 and the cos(2π3/4) real term will evaluate to zero.

So we finally have determined the four 4^{th} roots of
16 which is also known as 16+0*i*. Those roots are as follows:
2+0i, -2+0i, 0+2i, and 0-2i. A plot of these roots appears
below in Figure#1:

The interesting part of these M^{th} roots is that they
will always be evenly spaced around a circle with radius equal to
the value of the magnitude of the Complex Number raised to the
power of 1/M. You can see that by watching the
[8] demo at MathWorld. The M^{th}
roots of unity are simply a special case of the M^{th}
roots that are covered here, so the Rowland and Weisstein article
would be a great suplimentary article if you don't quite get
what I am saying here or you don't quite follow Dr. Smith's
approach [4].

With all of this said, we have given a basic overview of the
concent of M^{th} roots. In fact, you are welcome to
take the 5^{th} or 6^{th} roots of 16+0*i*
on your own time. Or you might even try taking taking roots of
Complex Numbers. It's up to you, but one thing remains. We should
show that when each of the 4^{th} roots we determined is
multiplied by itself four times, we get 16+0*i* or simply 16.
I'm not sure I have the time to do all four of the examples but I
will try the easiest ones.

We said the fourth roots of 16 was 2+0i, -2+0i, 0+2i, and 0-2i.
Well, we can easly see that 2*2*2*2=16 and that -2*-2*-2*-2=16, so
lets see what happens when we multiply (0-2i) by itself four times.
For starters we get:

(0-2i)*(0-2i)*(0-2i)*(0-2i)

this becomes

(-2i)*(-2i)*(-2i)*(-2i)

which is

(4i^{2})*(-2i)*(-2i)

Now, because the square of i is -1, we have

(4*(-1))*(-2i)*(-2i)

which is

-4*(-2i)*(-2i)

which is

-4*(4i^{2})

which is

-4*(4*(-1))

which is

-4*-4 which is obviously 16.

I leave it as an exercise to the reader to prove that
(0+2i)^{4} = 16. Now, I will mention the caveat. I
had it easy. I was lucky because all of my 4^{th} roots
were purely real or purely imaginary. That made the multiplication
of my roots by themselves quite easy. In many cases, you will
have a complex m^{th} root that has both real *and*
imaginary components. In that case, if you want to multiply the
root by itself you will have to use the FOIL method. Most likely,
you are already familiar with FOIL, but there is a good example of
it at [9] if you need help.

That's about all I'm going to say on M^{th} roots. So
why would someone want to know this? Well, if you want to evenly
space a bunch of points around a circle, it might be useful. It
seems to me that such a technique *might* be useful in drawing
3D cylindrical based meshes, but I hope to get into that at some
future date. The main reason I think someone would want to know
about M^{th} roots is that it makes it easier to
understand what's going on in the Fourier Transform. I don't know
the exact details at this moment, but I *think* I read somewhere
that if you have the M^{th} roots of unity
[10], then it
becomes easier to evaluate the Fourier Transform. Hopefully, I
will be able to get to that in the next few months without frying
my brain...

## Bibliography

1. Weisstein, Eric W."Square Root." From MathWorld--A Wolfram Web Resource.

[Cited: JUN 30, 2013.]

http://mathworld.wolfram.com/SquareRoot.html

2. Various.

Imaginary Unit.

Wikipedia. [Online: JUN 19, 2013]

[Cited: JUN 30, 2013.]

http://en.wikipedia.org/wiki/Imaginary_unit

3. Weisstein, Eric W.

"Complex Number." From MathWorld--A Wolfram Web Resource.

[Cited: JUN 30, 2013.]

http://mathworld.wolfram.com/ComplexNumber.html

4. Smith, Julis Orion III

MATHEMATICS OF THE DISCRETE FOURIER TRANSFORM (DFT) WITH AUDIO APPLICATIONS SECOND EDITION.

Stanford. [Online: MAY 06, 2013]

[Cited: JUN 29, 2013.]

https://ccrma.stanford.edu/~jos/mdft/Back_Mth_Roots.html

[Also available in print - Check Amazon.com]

5. Bourne, Murray

Polar Form of a Complex Number

Interactive Mathematics. [Online: MAY 25, 2013]

[Cited: JUN 29, 2013.]

http://www.intmath.com/complex-numbers/4-polar-form.php

6. Roelandts, Tom

Euler's Identity

TomRoelandts.com. [Online: MAR 11, 2012]

[Cited: JUN 29, 2013.]

http://tomroelandts.com/articles/eulers-identity

7. Various

What is e?

Non Destructive Testing (NDT) Resource Center. [Online: Unknown]

[Cited: JUN 29, 2013.]

http://www.ndt-ed.org/EducationResources/Math/Math-e.htm

8. Rowland, Todd and Wisstein, Eric W.

"Root of Unity." From MathWorld--A Wolfram Web Resource.

[Cited: JUN 30, 2013.]

http://mathworld.wolfram.com/RootofUnity.html

9. Unknown

Foil Method to Multiply Binomials

Math Warehouse. [Online: Unknown]

[Cited: JUN 30, 2013.]

http://www.mathwarehouse.com/algebra/polynomial/foil-method-binomials.php

10. Various.

Root of Unity.

Wikipedia. [Online: MAY 8, 2013]

[Cited: MAY 8, 2013.]

http://en.wikipedia.org/wiki/Root_of_unity

©2013 - Shawn Eary

This post is released under the Free Christian Document License (FCDL)