The Discrete Fourier Transform (DFT) is a linear operator used to perform a particularly useful change of basis.
It transforms a vector into a set of coordinates with respect to a basis whose vectors have two important characteristics:
they are orthogonal;
their entries are samples of the same periodic function taken at different frequencies.
Here is a definition.
Definition Let be an vector. The discrete Fourier transform of is an vector whose entries satisfywhere is the imaginary unit.
Zero-based indexing is often used to denote the entries of the vectors and , as follows:
In other words, the indices of the entries start from (not from , as it is customary for vectors) and are enclosed in square brackets.
Remember that
Since the sine and the cosine are periodic functions with period , the function is a periodic function of with period
The DFT is easily invertible.
Proposition Let and be an vector and its discrete Fourier transform respectively. Then,
We can writeIf , thenIf , we can use the geometric series formulato writewhere in step we use the fact that is a function of that has period . By putting together the equations above, we get
We can use a matrix to gather the values of the periodic functions used in the discrete Fourier transform.
Defineso that
Then, we can define the Fourier matrix
We can use to write the DFT in matrix form
By using the definition of matrix multiplication, you can easily check that this equation is equivalent to the equations we have used above to define the DFT.
The equation makes clear that the DFT is a linear operator with matrix .
Note that is a symmetric matrix.
The inverse transform can be written as
The entries of the inverse Fourier matrix have already been derived above:
Denote by the the -th column of .
Remember that post-multiplying a matrix by a column vector is the same as taking a linear combination of the columns of the matrix.
Therefore, we can write the inverse transform as
This is called frequency-domain representation of .
In other words, can be written as a linear combination of (samples of) periodic functions that have different frequencies.
The coefficients of the linear combination are .
The columns of the Fourier matrix and of its inverse are orthogonal to each other.
Consider two columns of the Fourier matrix and , with . Their inner product is where denotes conjugate transposition. The fact that the sum in the penultimate line is equal to zero was proved previously (see the the formula for the inverse transform). We leave as an exercise (see below) the proof that the columns of the inverse Fourier matrix are orthogonal.
However, the Fourier matrix, as defined above, is not unitary because its columns do not have unit norm.
Actually, all the columns have norm equal to .
Consider a column of the Fourier matrix . Its norm is:
To make the Fourier matrix unitary some authors define the Discrete Fourier Transform asin which case the inverse transform is
This is sometimes called the Unitary DFT.
The Fourier matrix of the Unitary DFT is
Its inverse iswhere denotes conjugate transposition.
More details about the DFT can be found in the following lectures:
Below you can find some exercises with explained solutions.
Prove that the columns of the inverse Fourier matrix are orthogonal to each other.
Consider two columns of the inverse Fourier matrix and , with . Their inner product is
Please cite as:
Taboga, Marco (2021). "Discrete Fourier transform", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform.
Most of the learning materials found on this website are now available in a traditional textbook format.