Evaluating DFT Of $f(n)=e^{an}$

Question

Evaluate DFT of $f(n)=e^{an}$ when $n=0,1...99$

So we have a vector $(1,e^a,e^{2a},...,e^{99a})$ now the formula for DFT is:

$$X_K=\sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i }{N}kn}$$

I just need to plug in the elements of the vector?

Answer 1

HINT

We have that $X_k$ is the dot product between the $k^{th}$ row of Fourier matrix times vector $x_n$ that is

$$X_k=\sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i }{N}kn}=\sum_{n=0}^{N-1}e^{an}e^{-\frac{2\pi i }{N}kn}=\sum_{n=0}^{N-1}e^{-\left(\frac{2\pi i k}{N}+a\right)n}$$

then recall that by geometric series

$$\sum_0^{N-1} r^n=\frac{1-r^N}{1-r}$$

Answer 2

If you insist on vector notation, write it as \begin{equation} X = \begin{bmatrix} X_1 \\ \vdots \\ X_k \\ \vdots\\ X_N \end{bmatrix} = Fx \end{equation} where $X_k$ is the $k^{th}$ entry of $X$ and $F$ is defined as follows \begin{equation} F = \begin{bmatrix} 1 & 1 &\ldots & 1 \\ 1 & w & \ldots & w^{N-1} \\ \vdots & \ddots & \vdots & \vdots \\ 1 & w^{N-1} & \ldots & w^{(N-1)(N-1)} \end{bmatrix} \end{equation} \begin{equation} w = e^{- i \frac{2 \pi}{N}} \end{equation} and \begin{equation} x = \begin{bmatrix} 1 \\ e^a \\ e^{2a} \\ \vdots \\ e^{(N-1)a} \end{bmatrix} \end{equation} Also, you've got $N = 100$ data points. Multiplying $F$ with $x$ gives \begin{equation} X = Fx = \begin{bmatrix} 1 & 1 &\ldots & 1 \\ 1 & w & \ldots & w^{N-1} \\ \vdots & \ddots & \vdots & \vdots \\ 1 & w^{N-1} & \ldots & w^{(N-1)(N-1)} \end{bmatrix} \begin{bmatrix} 1 \\ e^a \\ e^{2a} \\ \vdots \\ e^{(N-1)a} \end{bmatrix} = \begin{bmatrix} \sum\limits_{k=0}^{N-1} (e^{a})^k \\ \sum\limits_{k=0}^{N-1} (we^{a})^k \\ \sum\limits_{k=0}^{N-1} (w^2e^{a})^k \\ \vdots\\ \sum\limits_{k=0}^{N-1} (w^{N-1}e^{a})^k \\ \end{bmatrix} \end{equation} Each of the elements are geometric series that sum up to $\frac{1 - r^N}{1-r}$, hence \begin{equation} X = Fx = \begin{bmatrix} \frac{1 - (e^{a})^N}{1-e^{a}} \\ \frac{1 - (we^{a})^N}{1-we^{a}} \\ \frac{1 - (w^2e^{a})^N}{1-w^2e^{a}}\\ \vdots\\ \frac{1 - (w^{N-1}e^{a})^N}{1-w^{N-1}e^{a}} \\ \end{bmatrix} \end{equation} Plug in $N = 100$ and $w$, then you're done.