Recall that complex harmonic sinusoids have the form:
$s_k[n]=\frac{e^{j \frac{2\pi}{N}kn}}{\sqrt{N}}$
In the context of finite-length discrete-time signals and systems, complex harmonic sinusoids are special, for several reasons. First, the collection of them $\{s_k\}_{k=0}^{N-1}$ form a basis for $C^N$, meaning that any signal in $C^N$ can be represented as a linear combination of that set of $N$ vectors. Not only this, but they are an orthonormal basis, which means that the weights of the linear combination can be found simply through the inner product of the signal with the harmonic sinusoid in question. And finally, these signals $\{s_k\}_{k=0}^{N-1}$ are important because they are eigenvectors of finite-length discrete-time LTI systems. This means that whenever a complex harmonic sinusoid is given as an input to any LTI system, the output is simply a scaled version of that input.
The discrete fourier transform
In the early 19th century, Jean Baptiste Joseph Fourier showed that any function (later mathematics would more rigorously qualify this statement) could be composed as a (possibly infinite) sum of harmonic sinusoids. This work resulted in what would be an entire branch of mathematics, Fourier analysis. Fourier analysis extends to many different kinds of signals, including discrete-time finite-length signals. For those, the analysis produces the
discrete Fourier transform (DFT) . For signals $x[n]\in C^N$, the normalized DFT and inverse DFT are:$\begin{align*}
X[k]&= \sum_{n=0}^{N-1} x[n] \frac{e^{-j \frac{2\pi}{N}kn}}{\sqrt N}\\x[n]&=\sum_{k=0}^{N-1} X[k] \, \frac{e^{j \frac{2\pi}{N}kn}}{\sqrt N}\end{align*}$
We see that taking the inner product of $x[n]$ with harmonic sinusoids of different frequencies $k$ (which is what the first sum represents) produces a series of frequency coefficients $X{k]$. That is the DFT. We can also say that it is the
analysis aspect of the Fourier transform, for it gives us a frequency analysis/breakdown of the signal $x[n]$. The frequency coefficients can be used to reconstruct $x[n]$ using the second sum, which is the inverse DFT. It is known as
synthesis , for it shows how $x[n]$ can be built up as a linear combination of harmonic complex sinusoids, with the coefficients $X[k]$ telling us how much of each are needed.
A discrete-time finite length signal $x[n]$.$|X[k]|$, the magnitude of the DFT of $x[n]$.A discrete-time finite length signal and its DFT.
We can express the above signal analysis and synthesis in matrix notation. First we stack up the complex harmonic sinusoids $\{s_k\}_{k=0}^{N-1}$ as columns in a matrix $S$:
${\bf S} = \begin{bmatrix} s_0 | s_1 | \cdots | s_{N-1} \end{bmatrix}$With these vectors in a matrix, then the signal $x$ is composed of the linear combination of the sinusoids (the synthesis operation), with the weights in a vector $X$, through the matrix multiplication:
$x=SX$ (synthesis; inverse DFT)Finding the weights $X$, given $x$, requires the inverse of the basis matrix $S$. However, since $S$ is unitary, the inverse is simply the Hermitian transpose:
$X=S^H x$ (analysis; DFT)
Normalized and un-normalized dft
To this point, we have been working with the normalized expression of the DFT and its inverse:
$DFT: X[k]= \sum_{n=0}^{N-1} x[n]\, \frac{e^{-j \frac{2\pi}{N}kn}}{\sqrt N} \\Inverse DFT: x[n] = \sum_{k=0}^{N-1} X[k]\, \frac{e^{j \frac{2\pi}{N}kn}}{\sqrt N}$
This form of the DFT has a certain symmetric elegance to it, the only difference in the DFT and its inverse being the negation of the exponent in the complex harmonic sinusoid.
However, it is far more common to use an un-normalized definition of the DFT, one which puts a $\frac{1}{N}$ scaling factor on the inverse, rather than the normalized version splitting this with a $\frac{1}{\sqrt{N}}$ in each formula. In practice, the DFT is virtually always understood in terms of the following un-normalized definition:
$DFT: X[k]= \sum_{n=0}^{N-1} x[n]\, e^{-j \frac{2\pi}{N}kn} \\Inverse DFT: x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X_u[k]\, e^{j \frac{2\pi}{N}kn}$
Interpretations
So what exactly does the DFT MEAN? There are a variety of interpretations for what the DFT does. We have already explained things in terms of ANALYSIS and SYNTHESIS. With the inverse DFT, We can build up any signal $x[n]$ as a weighted sum (also known as a linear combination) of complex harmonic sinusoids; this is known as synthesis, which is in accordance with the Merriam-Webster dictionary definition of synthesis as being "the composition or combination of parts or elements so as to form a whole" (http://www.merriam-webster.com/dictionary/synthesis). But how are we to know how MUCH of each sinusoid goes in to the synthesis? The DFT tells us the coefficient values, one for each of the $N$ sinousids. This is the analysis aspect of the DFT, for it "analyzes" the signal in terms of the frequencies in it, how much there is of every possible frequency within the signal. To use a cooking metaphor, the analysis tells us the amount of each ingredient that goes into the dish that is our signal, and the cooking process is the synthesis which takes the ingredients and creates the finished product.
There is another way of looking at the DFT and inverse DFT. We note that there is a one-to-one correspondence between any signal $x[n]$ and its DFT $X[k]$; a signal $x[n]$ has only one DFT, and any $X[k]$ has only one inverse. So $x[n]$ and $X[k]$ are really referring to the same one thing--some signal--but only in different ways. $x[n]$ describes the signal in terms of its value at every given time location $n$, while $X[k]$ describes the signal in terms of how much of each frequency contributes to it. So there is a time-domain description of the signal, which is $x[n]$, and a frequency-domain description of it as well, which is $X[k]$. We could think of the time-domain and frequency-domain like two different languages, like English and Spanish. For some kind of language idea or expression, it can be represented in either one language or another, and given the expression in one language, it can be translated to the other. Of course, this is not a perfect metaphor; spoken languages are not always one-to-one (and some words in one language do not have an adequate word in another language). What this interpretation does convey is that time and frequency are two different, and yet also equivalent, ways of expressing a signal entity.
