The demo above shows how closed contours can be approximated via sums of complex exponentials. The process involves taking samples, performing a Discrete Fourier Transform on them, and then using the resulting Fourier Coefficients for complex exponentials. This is sometimes referred to as epicycles. This page gets into how the Discrete Fourier Transform Works.

Preliminary rambling notes

1. Take a closed contour $C.$

1. Take $N$ sample points along it, separated evenly by arc length.

1. Calculate the Fourier coefficient $c_n$ at each of the $N$ points. These correspond to the frequencies $n=-[N/2],\dots ,[N/2].$ We're basically measuring how much of each frequency the contour has at each of the $N$ different points.

We calculate the Fourier Coefficient $c_n$ as

$$c_n=\frac{1}{N}\sum _{k=0}^{N-1}{z}_k{e}^{-2\pi ink/N}$$

1. Only about half of these are unique because the frequency is the same as $-m$ (just like moving back 2 hours from 12 on a clock to 10 it the same as moving forward by 10 hours).

1. Each $c_n$ represents a vector in the complex plane with:

• length = $|c_n|$

• phase angle = $\mathrm{Arg}(c_n)$

• rotation speed = $n$

Seems to be measuring how well the sample points move around the unit circle at the same rate as the rotation vector?

Let's take $N=9$ and talk about what happens when our curve is a unit circle.

With frequency $n=0:$ we have no rotations, so, for each sample point, we add the sample point directly to the summation vector. The result is the average of all the sample points, the center of gravity, or DC component. For the unit circle this is $0.$

With frequency $n=-1:$

Starting with $k=0,$ we have $z_0,$ which is at $1.$ Our first rotation doesn't rotate at all, so our summation is now pointing at $1.$

Now at $k=1$, our second sample point $z_1$ is pointing at $\frac{2\pi }{9}.$ The imaginary component of our exponential $e^{-2\pi ink/N}$ gives us

$$-2\pi i(-1)(1)/9=\frac{2\pi }{9}.$$

So, our sample point and our rotation are the same. When we multiply them in exponential form, we add the angles, and get $\frac{4\pi }{9}.$ We take the exponential from our first sample and add it to this exponential, which gives us their average, and we get $\frac{2\pi }{9}$ as our summation vector so far.

Next at $k=2,$ our sample point is at $\frac{4\pi }{9}$ and our rotation vector is too. The resulting angle is $\frac{8\pi }{9}.$ Our summation vector now points at $\frac{5\pi }{9},$ midway between its previous value and the value of this sample.

The demo below shows how each individual Fourier Coefficient calculation works by taking a sample point and rotating it.

Math on the Unit Circle

The $n$th roots of unity. There are $n$ $nth$ roots of 1. So, $z^1=1$ has 1 solution, $1$ itself. $z^2=1$ has 2 solutions, $1$ and $-1.$ Note that $-1$ is on the opposite side of the unit circle from $1.$ $z^3$ has 3 solutions: $1,e^{2\pi /3}$ and $e^{4\pi /3}.$ The general pattern is that the $n$th roots of unity are given by

$$e^{i(2k\pi )/n},k=0,\dots ,n-1.$$

Now, multiplying these roots by each other can be accomplished by adding their exponents, which are just terms in $i\pi /n,$ i.e. the product of $1$ and $-1$ is

$$1\ast -1=e^{0(i2\pi /2)}\ast e^{1(i2\pi /2)}=e^{(0+1)(i2\pi /2)}=e^{i\pi }=-1.$$

Note that the resultant product is a root of unity as well, and in general the $nth$ roots of unit form a @cyclic abelian group under multiplication.

It also turns out that this group is isomorphic to ${\mathbb{Z}}_n$ under addition modulo $n.$ The multiplication we gave above is equivalent to $0+1=1$ on ${\mathbb{Z}}_2,$ and just like $-1\ast -1=1,$ $1+1=0$ on ${\mathbb{Z}}_2.$

One more fact worth noting, now that we've established this isomorphism. On the unit circle, a negative rotation (clockwise) by $\varphi$ is equal to a positive rotation (counterclockwise) by $2\pi -\varphi .$ This is easy to see:

$$-(\varphi )\equiv 2\pi +(-\varphi )(\mathrm{mod}2\pi )=2\pi -\varphi .$$

Thus, the $-k$th $n$th root of unit, $e^{2\pi i(k)}$ equals the $(n-k)$th root of unity (because the $n$th $n$th root of unity corresponds to a full rotation). This corresponds to $-k\equiv n-k(\mathrm{mod}n)$ on ${\mathbb{Z}}_n.$ For example, $-4=9-4=5$ on ${\mathbb{Z}}_9,$ and $e^{2\pi i(5)/9}=e^{2\pi i(-4)/9}$ on ${\mu }_n.$

Coming soon... roots of unity as the elements of basis vectors for ${\mathbb{C}}^n,$ and DFT as computing the inner product (basically, cosine similarity * magnitude) between the sample points and these basis vectors. That is, DFT is a change of basis onto these basis vectors, it is literally projecting onto these.

Sample Points as Vectors in ${\mathbb{C}}^n.$

Let's say we have a contour on the complex plane, and we take $n$ sample points on it, in order, so $z_0,z_1,\dots ,z_n.$ We can view these sample points (which form a sequence) as forming a vector in ${\mathbb{C}}^n:$

$$(z_0,z_1,\dots ,z_n).$$

Now, the standard basis for ${\mathbb{C}}^n$ is the same as that of ${\mathbb{R}}^n,$ which is $\{e_1,e_2,\dots ,e_n\},$ where $e_k$ is a $n$-dimensional vector with a 1 in the $k$th position and 0's in the other position, i.e.

$$e_1=(1,0,\dots ,0),e_2=(0,1,\dots ,0),\dots$$

It's easy to see that these basis vectors are orthogonal (and therefore @linearly-independent); to see that they span ${\mathbb{C}}^n$, suppose $w=(w_1,w_2,\dots ,w_n.).$ Then, $w_1\ast e_1+w_2\ast e_2+\cdots +w_n\ast e_n=w,$ that is, the components of $w$ (which are complex numbers) are exactly the scalar coefficients we need to multiply by our basis vectors to form $w,$ so this basis spans ${\mathbb{C}}^n.$

${\mathbb{C}}^n$ is an Inner Product Space

Now, we can equip this vector space with an inner product

Fourier Basis

We can use complex numbers representing varying degrees of rotation around the unit circle to form a basis vector. Given a sample count $N,$ we can make a basis from the $N$ vectors whose elements are defined as

$${\varphi }_n={\left(e^{2\pi ink/N}\right)}_{k=0}^{N-1},n=0,\dots ,N-1.$$

To work on intuition some, let's take the case $N=3.$

Then for $n=0,$

$${\varphi }_0=(e^{2\pi i(0)(0)/3},e^{2\pi i(0)(1)/3},e^{2\pi i(0)(2)/3})=(1,1,1),$$

$n=1,$

$${\varphi }_1=(e^{2\pi i(1)(0)/3},e^{2\pi i(1)(1)/3},e^{2\pi i(1)(2)/3})=(1,e^{2\pi i/3},e^{-2\pi i/3}),$$

and $n=2,$

$${\varphi }_2=(e^{2\pi i(2)(0)/3},e^{2\pi i(2)(1)/3},e^{2\pi i(2)(2)/3})=(1,e^{-2\pi i/3},e^{2\pi i/3}),$$

If we use our isomorphism ${\mathbb{Z}}_3,$ we have a $${\varphi }_0=(0,0,0),{\varphi }_1=(0,1,2),{\varphi }_2=(0,2,1).$$

Each of these values $n=0,1,2$ represents a different frequency. For $n=0,$ our total angle swept across all points is $2\pi \ast 0=0.$ For $n=1$ the total angle swept is $2\ast \pi \ast 1=2\pi .$ For $n=2$ the total angle swept is $2\ast pi\ast 2=4\pi .$ So, we can say that basis vector ${\varphi }_n$ is associated with (represents?) rotation at frequency $n.$

Now note that ${\varphi }_2={\varphi }_{-1}$ equals the conjugate of ${\varphi }_1.$ It appears that the conjugate of the basis vector representing rotation at frequency $n$ represents rotation at frequency $-n.$

For odd $N,$ one basis vector represents no rotation - no frequency - aka DC - this is for $n=0.$ Then, for each $n$ up to $(N-1)/2,$ we have a positive $n$ frequency vector and a matching $-n$ frequency vector. The vectors representing each pair of frequencies are made up of sample points which are conjugates of each other (reflections of each other across the $x$-axis, or alternatively, rotations by the same increments in opposite directions.) That is, the $k$th point in the vector for $-n$ is the conjugate of the $k$th point in the vector for $n.$

For even $N,$ we have a similar situation, except there is an additional frequency at $N/2$ that is sometimes called the Nyquist frequency. This frequency has only real components and is therefore its own conjugate. The $k$th element of this vector is given by

$${\varphi }_{N/2}(k)=e^{\pi ik}=(-1{)}^k.$$

Now we're ready to see the DFT as a change of basis from the standard basis for ${\mathbb{C}}^N$ to the DFT (Fourier) Basis for ${\mathbb{C}}^N.$ The DFT is given as

$$\mathbf{X}[n]=⟨\mathbf{x}[k],{\varphi }_n⟩=\sum _{k=0}^{N-1}\mathbf{x}[k]e^{-2\pi ink/N},$$

and the IDFT is given as

$$\mathbf{x}[k]=\frac{1}{N}\sum _{n=0}^{N-1}X[n]e^{2\pi ink/N}.$$

If we collect the conjugates of the ${\varphi }_k$ vectors as rows in a matrix we get

Then, given a vector $\mathbf{x}$ in ${\mathbb{C}}^N,$ we can compute its DFT via matrix vector multiplication as

$$\mathbf{X}=F\mathbf{x},$$

and we can invert it via IDFT using the conjugate rows of $F$ as

$$\mathbf{x}=\frac{1}{N}{F}^{\ast }\mathbf{X}.$$

The demo below allows drawing a contour and then editing the Fourier coefficients. Playing with this helps gives some intuition for what the coefficients represent, and it also shows one of the applications of DFT - filtering and amplifying components of a signal. Try drawing a closed contour that wraps around the origin three times counter-clockwise. What's the biggest component? Try drawing a similar shape, but go clockwise, maybe go clockwise 4 times.