REVIEW:  Complex numbers and Roots of Unity  

This material is in preparation for the lectures on the FFT next week. 
See also Wikipedia page  "Root of Unity"

Complex Plane
==============

Draw the complex plane on the board, label real and imaginary axes.
(See cmplxNumberReview.pdf for one slide from the lecture notes.
I will refer loosely to this slide below.)

Consider a complex number:
   z = x + i y  (plot it, indicate x and y).

Magnitude and Phase (Polar Coordinates)
=======================================

Alternative polar coordinate representation:
   z = rho e^{i theta}, rho = sqrt(x^2 + y^2), theta = atan2(y, x).
   rho is a non-negative real, and theta is real.
   rho is the magnitude and theta is the angle of z (measured
   from the positive real (x) axis counterclockwise).
   (indicate rho and theta on drawing)
  
Euler's formula:  e^{i theta} = cos(theta) + i sin(theta).

So
   z = rho e^{i theta} = rho cos(theta) + i rho  sin(theta) = x + i y

Draw this on the complex plane indicating all three components for some
rho > 1.


Roots of Unity:  
===============

For some integer n >= 1, the n^{th} roots of unity
are the solutions z of 
          z^n  = 1

Easy to solve in polar coords:  
   z = rho e^{i theta},  
   1 = e^{2k pi}, any integer k  (see Euler's formula)

So z^n = rho^n [e^{i theta}]^n = rho^n e^{i n theta}
       = 1   (we are looking for roots of unity)
       = e^{2k pi}, any integer k  (see Euler's formula)
   
So the magnitude rho^n = 1, rho a non-negative real number, so rho=1.
Also, matching the angle, we have
  e^{i n theta} = 1 = e^{2 k pi}
So 
  theta = 2 k pi / n

Note there are exactly n distinct n-th roots of unity, k = 0, 1, ... , n-1.

   e^{i 2(k+n) pi /n} = e^{{i 2k pi/n} + {i 2n pi/n}} 
                      = e^{i 2k pi/n} e^{i2pi}
                      = e^{i 2k pi/n} 

Draw on the complex plane picture, the roots for n = 8 
(see cmplxNumberReview.pdf).

Principal n-th Root:  
====================

We define the PRINCIPAL root of unity at k = 1,  namely
  omega = e^{i 2pi/n} 

Pick it out on the plot.  First root counter-clockwise from z = 1.
    
Note all the n-th roots, namely  e^{i 2k pi/n}, satisfy
 e^{i 2k pi/n} = omega^k, that is they are simple powers of
the principal root.
            

A Key Property of the n-th Roots of Unity.
==================================

Define omega = e^{i 2pi/n} (principal n-th root)

Property 1:  Let z = omega^j for some integer j, i.e. one of the n^{th}
roots of unity.  Then
  Sum_{k=0}^{n-1} z^k  = n delta_{j mod n, 0 }
Here delta_{m,n} equals one for m = n and zero otherwise.

That is, the sum of the n distinct powers of omega^j is equal to either
n or 0.  Morover, it equals n only when j mod n = 0.

Examples
========

Discuss this for j = 1, n=8 in terms of the picture. That is, 
if we divide the above sum by n, the "average" of the n n^th 
roots of unity is zero.

Discuss this for j = n or 0.  (All z's are 1).

Discuss this for j=3 in terms of the picture...indicate the points
omega^{jk}, k = 0, 1,  2.  The reason the sum for j=3 is zero is not so
obvious.

Proof of Property 1
==========

Pf: Multiply the sum above by (z-1) = (omega^j - 1) to get:
  (omega^j - 1) (Sum_{k=0}^{n-1} omega^{jk}) = omega^{jn} - 1 = 1 - 1 = 0.
This proves that, so long as omega^j - 1 is not zero, the sum must be zero.

For the remaining case, with omega^j = 1,  the sum is 
 Sum_{k=0}^{n-1} omega^{jk} = Sum_{k=0}^{n-1} 1^{k} = n.
In this case we must have 1 = omega^j = e^{i j 2pi/n} = e^{i m 2pi} for some
integer m.  So j = mn.  That is, j mod n = 0.  
This completes the proof of property 1.