2. Discrete Time Fourier Transform

Recall that if x(n) is absolutlely summable, that is, $\sum_{-\infty}^{+\infty} |x(n)| < \infty$ than its Discrete-Time Fourier Transform is given by:
\[
X(e^{j \omega})=\sum_{n=- \infty}^{+ \infty} x(n) \cdot e^{-j \cdot \omega \cdot n} \tag{3.1}
\]
This function transforms a discrete signal $x(n)$ into a complex-valued continuous function $X(e^{j \omega})$.

${\bf Matrix Implementation}$
If $x(n)$ is a finite duration sequence, we can use MATLAB to compute the Discrete Time Fourier Transform (DTFT) $X(e^{j\omega})$ numerically at any frequency $\omega$.

Let assume that the sequence x(n) has N samples between $n_1 \leq n \leq n_N$ we can define:
\[\omega_k =\frac{\pi}{M}k, \qquad k=0,1,....,M\]
which are (M+1) frequencies between $[0, \pi]$. Then (1) can be written as:

\[
X(e^{j\omega_k})=\sum_{r=1}^{N} x(n_r) \cdot e^{-j \cdot \omega_k \cdot n_r}  = \sum_{r=1}^{N} x(n_r) \cdot e^{-j \cdot \frac{\pi}{M} k \cdot n_r}, \qquad k=0,...,M \tag{3.2}
\]

Let's define the vector $\mathbf{X} = \begin{bmatrix} X(e^{j\omega_0}) \\ \vdots \\ X(e^{j\omega_M}) \end{bmatrix}$ where the k-th element $X(e^{j\omega_k})$ has the below expression:

\[X(e^{j\omega_k})= [ x(n_1) \cdot e^{-j \cdot \frac{\pi}{M}\cdot k \cdot n_1} + \ldots + x(n_N) \cdot  e^{-j \cdot \frac{\pi}{M}\cdot k \cdot n_N} ] \]

if we define the matrix $\mathbf{W}=\begin{bmatrix} W_0\\ \vdots \\W_M \end{bmatrix}$ where the k-th row $W_k$ has the below expression:

\[ W_k = \begin{bmatrix} e^{-j \cdot \frac{\pi}{M}\cdot k \cdot n_1}, \ldots, e^{-j \cdot \frac{\pi}{M}\cdot k \cdot n_N} \end{bmatrix} \]

and $\mathbf{x(n)} = \begin{bmatrix} x(n_1) \\ \vdots  \\ x(n_N) \end{bmatrix}$, we can write (3.2) as follow:

\[\mathbf{X} = \mathbf{W} \cdot \mathbf{x}\]

Let's consider the row vectors ${\bf k}$ and ${\bf n}$ that represent, respectively, the index of the frequency and for the time.
\[ \begin{matrix}
\mathbf{k}= \begin{bmatrix} 0, 1, \ldots, M\end{bmatrix}\\
\mathbf{n}= \begin{bmatrix} n_1, n_2, \ldots, n_N\end{bmatrix}
\end{matrix} \]
the product $\mathbf{k^T \cdot n}$ is equal to:
\[ \begin{bmatrix} 0 \\1 \\ \vdots \\M\end{bmatrix} \cdot \begin{bmatrix} n_1 & n_2 & \ldots & n_N\end{bmatrix} = \begin{bmatrix} 0 & 0 & \ldots & 0 \\ n_1 & n_2 & \ldots & n_N \\ \vdots & \vdots & \ddots & \vdots \\ M \cdot n_1 & M \cdot n_2 & \ldots & M \cdot n_N \end{bmatrix} \]
so we can rewrite $\mathbf{W}$

\[ \mathbf{W} = \begin{bmatrix} W_0 \\ W_1 \\ \vdots \\ W_M \end{bmatrix} = \begin{bmatrix} e^{-j \cdot \frac{\pi}{M}\cdot 0 \cdot n_1} \ldots e^{-j \cdot \frac{\pi}{M}\cdot 0 \cdot n_N} \\ \vdots \\ e^{-j \cdot \frac{\pi}{M}\cdot M \cdot n_1} \ldots e^{-j \cdot \frac{\pi}{M}\cdot M \cdot n_N} \end{bmatrix} =
 exp[-j \cdot \frac{\pi}{M} \cdot \mathbf{k^T \cdot n}] \]

finally the complete matrix form for DTFT is
\[\mathbf{X} = exp[-j \cdot \frac{\pi}{M} \cdot \mathbf{k^T \cdot n}] \cdot \mathbf{x} \tag{3.3} \]