Linearity

Theorem: For any $x,y\in\mathbb{C}^N$ and $\alpha, \beta\in\mathbb{C}$ , the DFT satisfies

$$\zbox {\alpha x + \beta y \;\longleftrightarrow\;\alpha X + \beta Y}$$

where $X\isdeftext \hbox{\sc DFT}(x)$ and $Y\isdeftext \hbox{\sc DFT}(y)$ , as always in this book. Thus, the DFT is a linear operator.

Proof:

$$\begin{eqnarray*} \hbox{\sc DFT}_k(\alpha x + \beta y) &\isdef & \sum_{n=0}^{N-1}[\alpha x(n) + \beta y(n)]e^{-j 2\pi nk/N}\\ &=& \sum_{n=0}^{N-1}\alpha x(n)e^{-j 2\pi nk/N} + \sum_{n=0}^{N-1}\beta y(n) e^{-j 2\pi nk/N} \\ &=& \alpha \sum_{n=0}^{N-1}x(n)e^{-j 2\pi nk/N} + \beta \sum_{n=0}^{N-1}y(n) e^{-j 2\pi nk/N} \\ &\isdef & \alpha X + \beta Y \end{eqnarray*}$$