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 + yi = 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 + yi = 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 = re^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}}(\cos \frac{\theta +2\mathrm{\pi k}}{M}+i\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}}(\cos \frac{0+2\pi 0}{4}+i\sin \frac{0+2\pi 0}{4})$

For k=1 we get:
$z^{\frac{1}{4}}=r^{\frac{1}{4}}(\cos \frac{0+2\pi 1}{4}+i\sin \frac{0+2\pi 1}{4})$

For k=2 we get:
$z^{\frac{1}{4}}=r^{\frac{1}{4}}(\cos \frac{0+2\pi 2}{4}+i\sin \frac{0+2\pi 2}{4})$

And finally for k=3 we get...:
$z^{\frac{1}{4}}=r^{\frac{1}{4}}(\cos \frac{0+2\pi 3}{4}+i\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}}(\cos \frac{2\pi }{4}+i\sin \frac{2\pi }{4})$
which is also:
$z^{\frac{1}{4}}=2(\cos \frac{\pi }{2}+i\sin \frac{\pi }{2})$

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

or finally:
0 + 2i

I leave it as an exercise for the reader to show that the k=3 case yields 0 - 2i, 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+0i. 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+0i 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+0i 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²)*(-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²)
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)⁴ = 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

©2013 - Shawn Eary
This post is released under the Free Christian Document License (FCDL)