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: