6.1. Linearity

The first major property of the DFT that we’ll cover is linearity. We’ve already seen linearity in the context of LSI systems, where we used it to understand what happens when you convolve a filter $h$ with a mixture of signals.

Here, we’ll use linearity slightly differently, but the basic idea is the same.

Property 6.1 (DFT Linearity)

For any pair of signals $x_1[n]$ and $x_2[n]$ of the same length, and real numbers $c_1,c_2$, the following holds:

$$\text{DFT}(c_1\cdot x_1+c_2\cdot x_2)=c_1\cdot \text{DFT}(x_1)+c_2\cdot \text{DFT}(x_2).$$

We’ll prove this property algebraically, starting from the definition of the DFT (5.12):

$$X[m]=\sum _{n=0}^{N-1}x[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)$$

Proof. Let $0\le m<N$ be any frequency index. Using $x=c_1\cdot x_1+c_2\cdot x_2$ as our input signal, its $m$th DFT component is

$$\begin{array}{rl}\sum _{n=0}^{N-1}(c_1\cdot x_1[n]+c_2\cdot x_2[n])\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)& =\sum _{n=0}^{N-1}(c_1\cdot x_1[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)\\ & +c_2\cdot x_2[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)\phantom{\frac{m}{n}})\\ & =c_1\cdot \sum _{n=0}^{N-1}{x}_1[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)\\ & +c_2\cdot \sum _{n=0}^{N-1}{x}_2[n]\cdot \exp (-\mathrm{j}\cdot 2\pi \cdot \frac{m}{N}\cdot n)\\ & =c_1\cdot X_1[m]+c_2\cdot X_2[m].\end{array}$$

So if we scale and mix two input signals, the resulting DFT component is the same scaling and mixing of their individual DFT components $X_1[m]$ and $X_2[m]$. Since this holds for any $m$ it must hold for all $m$, so the entire DFT sequence of the mixture is the mixture of the DFT sequences. This is what we set out to prove.

What does linearity buy us?

DFT linearity is important because most interesting signals are not just simple sinusoids. What DFT linearity says is that if we can represent an arbitrary signal $x$ as a weighted combination of sinusoids, then we can reason about its DFT in terms of its constituent sinusoids.

As we will see in the next chapter (and as we’ve hinted at earlier), it turns out that all signals can be represented as a weighted combination of sinusoids.

6.1.1. Magnitude is not linear

Note that DFT linearity applies to the complex numbers $X[m]$ which encode both magnitude and phase. There is nothing wrong with adding complex numbers, provided it is done correctly, keeping the real and imaginary parts separate.

However, it is a common mistake to add magnitudes rather than the full complex numbers.

Magnitude is not linear.

If signals $x_1[n]$ and $x_2[n]$ have DFT series $X_1[m]$ and $X_2[m]$, then the sum $y[n]=x_1[n]+x_2[n]$ has DFT series $Y[m]=X_1[m]+X_2[m]$.

But remember,

$$\begin{array}{rl}\left|Y[m]\right|& =\left|X_1[m]+X_2[m]\right|\\ & \ne \left|X_1[m]\right|+\left|X_2[m]\right|.\end{array}$$

Example

For an extreme case, consider $x_2[n]=-x_1[n]$ for some arbitrary, non-empty signal $x_1$. DFT linearity says that $X_2[m]=-1\cdot X_1[m]$, so the spectra $X_1$ and $X_2$ are opposites. However, the spectral magnitudes are identical:

$$X_2[m]=-X_1[m]\Rightarrow |X_2[m]|=|-1\cdot X_1[m]|=|X_1[m]|.$$

If we were to add the magnitude spectra, we’d get

$$|X_1[m]|+|X_2[m]|=|X_1[m]|+|X_1[m]|=2\cdot |X_1[m]|.$$

However, if we mix the two signals in the time domain, we get the empty signal:

$$y[n]=x_1[n]+x_2[n]=x_1[n]-x_1[n]=0.$$

The empty signal has an empty spectrum: $Y[m]=0$ for all $m$, but

$$|Y[m]|=0\ne 2\cdot |X_1[m]|$$

in general.

What this says is that mixing signals does not equate to mixing DFT magnitudes.

Fig. 6.1 Complex numbers $z$ and $w=-z$ have the same magnitude $|z|=|w|$ but different phase. The sum of their magnitudes $|z|+|w|$ is not the same as the magnitude of their sum $|z+w|=0$.