Matrix form of the DFT

The forward and inverse DFT can be written as:

$$X[n]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m]e^{-mn j2\pi/N} ... ...0}^{N-1} X[n]e^{mn j2\pi/N} =\sum_{n=0}^{N-1} w_N^{-mn} X[n]$$

$$m,n=0, 1, \cdots, N-1$$

where we have defined

$$w_{mn}\stackrel{\triangle}{=}\frac{1}{\sqrt{N}}(e^{-j2\pi/N})... ... \;\;\;\;\;\;\; w_{mn}^*=\frac{1}{\sqrt{N}}(e^{j2\pi/N})^{mn}$$

and $w_{mn}^*$ is its complex conjugate of $w_{mn}$. We can further define an $N \times N$ square matrix

$${\bf W}=\left[{\bf w}_0,\cdots,{\bf w}_{N-1}\right] =\left... ... . & w_{mn} & . \\ . & . & . \end{array} \right]_{N\times N}$$

where $w_{mn}$ is the element in the mth row and nth column of ${\bf W}$, and ${\bf w}_n=[w_{0n},\cdots,w_{(N-1)n}]^T$ is the nth column vector of ${\bf W}$. As $w_{mn}=w_{nm}$, ${\bf W}$ is symmetric

$${\bf W}^T={\bf W}$$

Also, note that the columns (or rows) of ${\bf W}$ are orthogonal:

$$\langle{\bf w}_m, {\bf w}_n\rangle={\bf w}^T_m {\bf w}^*_n =... ...{\begin{array}{ll}1&\;\;m=n 0&\;\;m\ne n \end{array} \right.$$

as

• If $m=n$, $(e^{j2\pi/N})^{(n-m)k}=1$ and $\langle{\bf w}_m, {\bf w}_n\rangle=1$,
• If $m\ne n$, the summation becomes:
  
  $$\sum_{k=0}^{N-1} (e^{j2\pi(n-m)/N})^k=\frac{1-\left(e^{j2\pi(n-m)/N\right})^N}{1-e^{j2\pi(n-m)/N}}=0$$
  
  

Therefore ${\bf W}$ is a unitary matrix, as well and symmetric:

$${\bf W}^{*T}={\bf W}^*={\bf W}^{-1}$$

We further represent the discrete signal $x[m]$ and its DFT spectrum $X[n]$ as two N-D vectors:

$${\bf X}\stackrel{\triangle}{=} \left[ \begin{array}{c} X[0] ... ...y}{c} x[0] . . x[N-1] \end{array} \right]_{N\times 1}$$

then the DFT can be written more conveniently as a matrix-vector multiplication:

$${\bf X}=\left[ \begin{array}{c} X[0] . . X[N-1] \end{a... ...{c} x[0] . . x[N-1] \end{array} \right] ={\bf W}{\bf x}$$

and

$${\bf x}=\left[ \begin{array}{c} x[0] . . x[N-1] \end{a... ...1] \end{array} \right] ={\bf W}^*{\bf X} ={\bf W}^{-1}{\bf X}$$

It is obvious that the computational complexity of this 1-D DFT takes is $O(N^2)$, which, as we will see later, can be reduced to $O(N\; log_2 N)$ by Fast Fourier Transform (FFT) algorithms.

See additional geometric explanation of unitary/orthogonal transform.