# Linear Systems and Fourier Transforms

Aug-Nov 2020

## Recap

• Vector space $V$ over a scalar field $F$
• $F$: real field $\mathbb{R}$ or complex field $\mathbb{C}$ in this course
• $m\times n$ matrix A represents a linear map $T:F^n\to F^m$
• dim null $T$ + dim range $T$ = dim $V$
• Linear equation: $Ax=b$
• Solution (if it exists): $u+$ null$(A)$
• Four fundamental subspaces of a matrix
• Column space, row space, null space, left null space
• Eigenvalue $\lambda$ and Eigenvector $v$: $Tv=\lambda v$
• Distinct eigenvalues have independent eigenvectors
• Basis of eigenvectors results in a diagonal matrix for $T$
• Every linear map has an upper triangular matrix representation

## Linear systems

• In engineering, systems process an input and produce an output.

• Electrical systems working in discrete time

• Input signal: $x=(x_0,x_1,\ldots,x_{K-1})$

• Output signal: $y=(y_0,y_1,\ldots,y_{K-1})$

• $x_n,y_n$: real or complex

Linear, time-invariant (LTI) systems

$y_n=h_0x_n+h_1x_{n-1}+\cdots+h_Lx_{n-L}$

• $n=0,1,\ldots,K-1$; assume $x_i=0$ for $i<0$

• $h=(h_0,\ldots,h_L)$: called impulse response

• almost all electrical systems use this model

## Linear systems and linear convolution

Linear convolution map: $y\ =\ H_{\text{lin}}\ x$

$\begin{bmatrix} y_0\\y_1\\y_2\\\vdots\\y_L\\y_{L+1}\\y_{L+2}\\\vdots\\\vdots\\y_{K-1} \end{bmatrix}=\begin{bmatrix} h_0&0&0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ h_1&h_0&0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ h_2&h_1&h_0&0&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots&\vdots&\vdots&\vdots\\ h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0\\ 0&h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&0\\ \vdots&0&h_L&\cdots&\cdots&h_1&h_0&0&\vdots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&0\\ \cdots&\cdots&\cdots&\cdots&0&h_L&\cdots&\cdots&h_1&h_0 \end{bmatrix}\begin{bmatrix} x_0\\x_1\\x_2\\\vdots\\x_L\\x_{L+1}\\x_{L+2}\\\vdots\\\vdots\\x_{K-1} \end{bmatrix}$

## Linear systems and circular convolution

Circular convolution map: $y\ =\ H_{\text{circ}}\ x$

$\begin{bmatrix} y_0\\y_1\\\vdots\\y_{L-1}\\y_L\\y_{L+1}\\y_{L+2}\\\vdots\\y_{K-2}\\y_{K-1} \end{bmatrix}=\begin{bmatrix} h_0&0&\cdots&\cdots&\cdots&0&h_L&\cdots&h_2&h_1\\ h_1&h_0&0&\cdots&\cdots&\cdots&0&h_L&\cdots&h_2\\ \vdots&\ddots&\ddots&\ddots&\vdots&\vdots&\vdots&\ddots&\ddots&\vdots\\ h_{L-1}&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0&h_L\\ h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&\cdots&0\\ 0&h_L&\cdots&\cdots&h_1&h_0&0&\cdots&\cdots&0\\ \vdots&0&h_L&\cdots&\cdots&h_1&h_0&0&\vdots&\vdots\\ \vdots&\vdots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \vdots&\vdots&\vdots&0&h_L&\cdots&\cdots&h_1&h_0&0\\ 0&\cdots&\cdots&\cdots&0&h_L&\cdots&\cdots&h_1&h_0 \end{bmatrix}\begin{bmatrix} x_0\\x_1\\\vdots\\x_{L-1}\\x_L\\x_{L+1}\\x_{L+2}\\\vdots\\x_{K-2}\\x_{K-1} \end{bmatrix}$

• zero-pad input to convert linear into circular convolution

## Linear maps represented by circulant matrices

LTI systems are represented by the circulant matrix with first column equal to impulse response

• What are eigenvectors and eigenvalues of $H_{\text{circ}}$?

• Let $\omega=e^{i2\pi/K}=\cos(2\pi/K)+i\sin(2\pi/K)$

Eigenvectors and eigenvalues of $H_{\text{circ}}$ for $\{h_0,\ldots,h_L\}$

$v_k = (\omega^{0},\omega^{k},\omega^{2k},\cdots,\omega^{(K-1)k})$ for $k=0,\ldots,K-1$

$\lambda_k = h_0w^0+h_1w^{-k}+h_2w^{-2k}+\cdots+h_Lw^{-Lk}$

## Fourier transforms

Time domain: standard basis

• signals $x=(x_0,\ldots,x_{K-1})$, $y=(y_0,\ldots,y_{K-1})$

Frequency domain: eigenvector basis of circulant matrices

• Matrix to convert from Fourier basis to standard basis

$\text{IDFT}_K=\frac{1}{\sqrt{K}}\begin{bmatrix} 1&1&1&\cdots&1\\ 1&\omega&\omega^2&\cdots&w^{K-1}\\ 1&\omega^2&(\omega^2)^2&\cdots&(w^{K-1})^2\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega^{K-1}&(\omega^{K-1})^2&\cdots&(w^{K-1})^{K-1}\\ \end{bmatrix}$

• Discrete Fourier transform of $x$, $y$: $x$, $y$ in Fourier basis

• Denoted $\hat{x}=(\hat{x}_0,\hat{x}_1,\ldots,\hat{x}_{K-1})$, $\hat{y}=(\hat{y}_0,\hat{y}_1,\ldots,\hat{y}_{K-1})$

## LTI systems in Fourier domain

• Matrix to convert from standard basis to Fourier basis

$\text{DFT}_K=\frac{1}{\sqrt{K}}\begin{bmatrix} 1&1&1&\cdots&1\\ 1&\omega^{-1}&\omega^{-2}&\cdots&w^{-(K-1)}\\ 1&\omega^{-2}&(\omega^{-2})^2&\cdots&(w^{-(K-1)})^2\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&\omega^{-(K-1)}&(\omega^{-(K-1)})^2&\cdots&(w^{-(K-1)})^{K-1}\\ \end{bmatrix}$

• Input, output, impulse response: $x$, $y$, $h$ in time domain or standard basis

• Frequency domain or Fourier basis: $\hat{x}=\text{DFT}_K\ x$, $\hat{y}=\text{DFT}_K\ y$, $\hat{h}=\text{DFT}_K\ h$

$\hat{y}_k\ =\ \hat{x}_k\ \hat{h}_k$

• $H_{\text{circ}}$ becomes a diagonal matrix in Fourier basis