Quote Originally Posted by DavidP View Post
Agreed. I need to study the concept of roots of unity more. When I took an algorithms class about 2 years ago, we discussed the complex roots of unity, and after lots of studying I had a basic, but useable, understanding of them. Now I've lost much of my understanding of the roots of unity...so I need to go back over them.
It might be easier to imagine them as phasors, little stopwatches where the second hand rotates around some integral number of revolutions -- the value of k dictates how quickly the phasor hand rotates. Essentially, what it's doing is correlating your signal with a harmonic basis vector, and the number of revolutions of the phasor goes up by integral amounts for each basis -- the first one makes one full revolution over the transform period, the second makes two revolutions, etc.