### DISCRETE FOURIER TRANSFORMATION:

This is a great reference.

We are dealing with $$N=6$$ points, corresponding to integers from $$0$$ to $$N-1=5$$, and the sinusoids are truncated at length $$N$$. There are $$N$$ basis functions of amplitude $$1$$: $$N/2$$ sine, and $$N/2$$ cosine according to The Scientist and Engineerâ€™s Guide to Digital Signal Processing by Steven W. Smith, and Iâ€™m trying to get the explanation for it here.

The fundamental angular frequency is given by $$\frac{2\pi}{N}$$, which can be thought of as slicing the $$2\pi$$ circle into $$N$$ equal slices.

The frequency of each sinusoid is determined by the parameter $$k$$. The frequency parameter, $$k$$, is equal to the number of complete cycles that occur over the $$N$$ points of the signal.

Each point on the left column of the plot below is calculated as $$\sin\left(\frac{2\pi}{N}kn\right)$$ with $$n\in\{0,\dots,5\}$$. The first plot is for $$k=0$$; the second, $$k=1$$; $$k=2$$ and, finally, $$k=3$$. The column on the right is calculated as $$\cos\left(\frac{2\pi}{N}kn\right)$$.

The dots in the plots above were simply defined as $$(x,f(x))=(0,f(0)), (1,f(1)), (2,f(2)),(3,f(3)),(4,f(4)),(5,f(5))$$ with $$f(x)=\exp\{\frac{2\pi}{N}kn\}=\exp\{\frac{2\pi}{6}kx\}$$. The amplitude is $$1$$. $$k$$ was advanced from $$0$$ to $$N/2=3$$ for both sine and cosine basis functions.

The DFT is defined as:

$X(k)\equiv \sum_{n=0}^{N-1}\underset{\text{time sequence}}{\underbrace{ x(n)}}\; \underset{\text{basis funcs.}}{\underbrace{\exp\left(\color{red}{\mathbf-}i\frac{2\pi}{N}kn\right)}}, \quad k=0,1,\dots,N-1$

although also found with a normalizing $$1/N$$ in front:

$X(k)\equiv \frac{1}{N}\sum_{n=0}^{N-1}\underset{\text{time sequence}}{\underbrace{ x(n)}}\; \underset{\text{basis funcs.}}{\underbrace{\exp\left(\color{red}{\mathbf-}i\frac{2\pi}{N}kn\right)}}, \quad k=0,1,\dots,N-1$

The minus sign is just a convention so that the inverse (IDFT) ends up expressed as the sum of positive frequencies:

$x[n]= \sum_k X(k) \exp\left(i\,\frac{2\pi}{N} kn\right)$

which is a sum of sines and cosines if we use the Eulerâ€™s formula:

$e^{ix}=\cos x + i \sin x$

There is another explanation of this convention here. The only important part is that the direct and inverse DFT have opposite signs.

We definine $$w_N$$ - the twiddle factor:

$\large w_N \equiv e^{-i\,\frac{2\pi}{N}}$

which has periodic properties. The $$N$$ power of the twiddle factor is:

$w_N^N=e^{-i\,\frac{2\pi}{N}N}=e^{-i2\pi}=1$

thanks to Eulerâ€™s identity, $$e^{i\pi}+1 = 0$$, and $$e^{-i2\pi}=1$$.

And $$w_N^{k+N}=w_N^k$$ because $$w_N^{k+N}=w_N^k\,w_N^N$$.

The exponents are $$w_N^{kn}=\left(e^{-i\,\frac{2\pi}{N}}\right)^{kn}$$.

It makes sense then to express the DFT as a matrix. The $$N=4$$ (four-point) DFT is especially cool, because splitting the circle into quadrant result in pure sine and cosine waves - in the complex plane, we are either along the $$x$$-axis (real / cosine), or along the $$y$$-axis (imaginary /sine). The matrix (really well explained by Professor Stang) then simplifies nicely as:

$W = \begin{bmatrix} \omega^0 & \omega^0 &\omega^0 &\omega^0 \\ \omega^0 & \omega^1 &\omega^2 &\omega^3 \\ \omega^0 & \omega^2 &\omega^4 &\omega^6 \\ \omega^0 & \omega^3 &\omega^6 &\omega^9 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i\\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i\end{bmatrix}$

where $$\omega = e^{-\frac{\pi i}{2}} = -i.$$

The DFT would therefore be calculated as:

$\begin{bmatrix} X[0]\\X[1]\\X[2]\\X[3] \end{bmatrix}= \begin{bmatrix} \omega^0 & \omega^0 &\omega^0 &\omega^0 \\ \omega^0 & \omega^1 &\omega^2 &\omega^3 \\ \omega^0 & \omega^2 &\omega^4 &\omega^6 \\ \omega^0 & \omega^3 &\omega^6 &\omega^9 \\ \end{bmatrix} \begin{bmatrix} x[0]\\x[1]\\x[2]\\x[3] \end{bmatrix}$

leading to the Fast Fourier (FFT) expedited method.

There is a great insight found here:

Defining $$s_k(n)\equiv e^{i\,\frac{2\pi}{N}kn}$$.

Finally, we need to understand what the summation over $$n$$ is doing in the definition of the DFT. Weâ€™ll learn that it should be seen as the computation of the inner product of the signals $$x$$ and $$s_k$$ defined above, so that we may write the DFT, using inner-product notation, as

$X(k) \equiv \langle x,s_k\rangle$

where $$s_k(n) \equiv e^{j{2\pi n k/N}}$$ is the sampled complex sinusoid at (normalized) radian frequency $$\omega_k T=2\pi k/N$$, where $$T$$ is the sampling interval or sampling period, and the inner product operation $$\left<\,\cdot\,,\,\cdot\,\right>$$ is defined by $$\left<x,y\right> \equiv \displaystyle\sum_{n=0}^{N-1}x(n) \overline{y(n)}$$.

This idea of DFT as a measure of similarity between the sampled signal and the sinusoids is very well explained on this video, containing a great example: