Discrete Fourier transform

by Marco Taboga, PhD

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:

1. they are orthogonal;

2. their entries are samples of the same periodic function taken at different frequencies.

Definition

Here is a definition.

Zero-based indexing

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.

Periodicity

Remember that

Since the sine and the cosine are periodic functions with period , the function is a periodic function of with period

Inverse transform

The DFT is easily invertible.

Fourier matrix

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.

Inverse Fourier matrix

The inverse transform can be written as

The entries of the inverse Fourier matrix have already been derived above:

Frequency-domain representation

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 .

Orthogonality

The columns of the Fourier matrix and of its inverse are orthogonal to each other.

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 .

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.

Learn more about the DFT

More details about the DFT can be found in the following lectures:

• DFT of a real vector;

• amplitude, power and frequency spectra;

• DFT of sine and cosine functions;

• frequencies of the DFT.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Prove that the columns of the inverse Fourier matrix are orthogonal to each other.

How to cite

Please cite as:

Taboga, Marco (2021). "Discrete Fourier transform", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform.