I am going to give a quick explanation for DFT (Discrete Fourier Transform) from the viewpoint of DFT computation itself.

# Observation

For example, here we use *numpy.fft.fft* for some random vectors:

Let’s denote the input as

We can observe something about the result from *fft*:

- While most entries are complex numbers, the first entry
is always a real number (i.e., the imaginary part is zero). - Moreover, when the vector length
is even, the is also a real number. and are conjugates of each other, for .

# Understanding

### DFT as Matrix-vector multiplication

Instead of telling a long story of DSP theory, let’s get an intuitive understanding directly from the computation process.

This is how *fft* computes

The matrix *Fourier matrix*.

Essentially, ignoring the acceleration techniques, the *fft* can be viewed as a matrix-vector multiplication, where each

Let’s take a close look on these entries for a given row vector of matrix

### Symmetries

The

Therefore, this vector can be seen as

In other words, the entries of

Now let’s explain the above three observations by analyzing each row’s entries

For the first row, i.e., the frequency

*s=0,*So the first row vector’s entries are free of imaginary parts,

is definitely a real number. Additionally, when

*n*is even, for frequencySo these entries are also real numbers. Then, as a weighted sum of these entries,

is definitely an real number. Moreover, we can observe that, for a

th row’s entry: It means the entries of

th row vector and th row vector are conjugates of each other respectively. Therefore, and are also conjugates of each other, as they are linear combinations of these entries by the same weights. This implies that, given an input vector of

entries, we can only obtain useful output values (see Nyquist sampling theorem). So, from the th output value, negative frequencies, i.e., Hz is used to call these output values. For example, given a vector length of 10, the output values are of frequencies 0 Hz, 1 Hz, 2 Hz, 3 Hz, 4 Hz, 5 Hz/-5 Hz, -4 Hz, -3Hz, -2 Hz, -1 Hz. So, after

*fft*, if you want to shift the lower frequency components into the center, you use*fftshift*method to alter the output values’ positions into an order (-5 Hz) -4 Hz, -3 Hz, -2 Hz, -1 Hz, 0 Hz, 1 Hz, 2 Hz, 3Hz, 4 Hz, (5 Hz).Note that

*numpy.fft.fftshift*regards theth output value as a part of negative frequencies.