1.8 Dft as a matrix operation

Matrix review

Recall:

• Vectors in $\mathbb{R}^N$ : $$\forall x_i, x_i\in \mathbb{R}\colon x=\begin{pmatrix}{x}_0\\ x_1\\ \\ x_{N-1}\\ \end{pmatrix}$$
• Vectors in $\mathbb{C}^N$ : $$\forall x_i, x_i\in \mathbb{C}\colon x=\begin{pmatrix}{x}_0\\ x_1\\ \\ x_{N-1}\\ \end{pmatrix}$$
• Transposition:
  • transpose: $$x^T=\begin{pmatrix}{x}_0 & x_1 & & x_{N-1}\\ \end{pmatrix}$$
  • conjugate: $$(x)=\begin{pmatrix}\overline{x_0} & \overline{x_1} & & \overline{x_{N-1}}\\ \end{pmatrix}$$
• Inner product :
  • real: $$x^Ty=\sum_{i=0}^{N-1} x_i{y}_i$$
  • complex: $$(x)y=\sum_{i=0}^{N-1} \overline{x_n}{y}_n$$
• Matrix Multiplication: $$Ax=\begin{pmatrix}{a}_{00} & a_{01} & & a_{0,N-1}\\ a_{10} & a_{11} & & a_{1,N-1}\\ & & & \\ a_{N-1,0} & a_{N-1,1} & & a_{N-1,N-1}\\ \end{pmatrix}\begin{pmatrix}{x}_0\\ x_1\\ \\ x_{N-1}\\ \end{pmatrix}=\begin{pmatrix}{y}_0\\ y_1\\ \\ y_{N-1}\\ \end{pmatrix}$$ $$y_k=\sum_{n=0}^{N-1} a_{kn}{x}_n$$
• Matrix Transposition: $$A^T=\begin{pmatrix}{a}_{00} & a_{10} & & a_{N-1,0}\\ a_{01} & a_{11} & & a_{N-1,1}\\ & & & \\ a_{0,N-1} & a_{1,N-1} & & a_{N-1,N-1}\\ \end{pmatrix}$$ Matrix transposition involved simply swapping the rows with columns. $$(A)=\overline{A^T}$$ The above equation is Hermitian transpose. $$A^T_{k, n}=A_{n, k}$$ $$(A)_{k, n}=\overline{A}_{n, k}$$

Representing dft as matrix operation

Now let's represent the DFT in vector-matrix notation. $$x=\begin{pmatrix}x(0)\\ x(1)\\ \\ x(N-1)\\ \end{pmatrix}$$ $$X=\begin{pmatrix}X(0)\\ X(1)\\ \\ X(N-1)\\ \end{pmatrix}\in \mathbb{C}^N$$ Here $x$ is the vector of time samples and $X$ is the vector of DFT coefficients. How are $x$ and $X$ related: $$X(k)=\sum_{n=0}^{N-1} x(n)e^{-(i\frac{2\pi }{N}kn)}$$ where $$a_{kn}=e^{-(i\frac{2\pi }{N})}^{(kn)}=W_N^{(kn)}$$ so $$X=Wx$$ where $X$ is the DFT vector, $W$ is the matrix and $x$ the time domain vector. $$W_{k, n}=e^{-(i\frac{2\pi }{N})}^{(kn)}$$ $$X=W\left(\begin{array}{c}x(0)\\ x(1)\\ \\ x(N-1)\end{array}\right)$$ IDFT: $$x(n)=\frac{1}{N}\sum_{k=0}^{N-1} X(k)e^{i\frac{2\pi }{N}}^{(nk)}$$ where $$e^{i\frac{2\pi }{N}}^{(nk)}=\overline{W_N^{(nk)}}$$ $\overline{W_N^{(nk)}}$ is the matrix Hermitian transpose. So, $$x=\frac{1}{N}(W)X$$ where $x$ is the time vector, $\frac{1}{N}(W)$ is the inverse DFT matrix, and $X$ is the DFT vector.