# Discrete Fourier transform of shifted N-periodic sequence

I'm trying to show that if f[n] is an N-periodic sequence then the Discrete Fourier Transform of the shifted sequence f[n-m] for some constant $m\in\mathbb{Z}$ is

$e^{\frac{-2\pi i mk}{N}} F[k]$

where $F[k]$ is the DFT of f[n].

I've started out with expanding the definition of a DFT, giving the DFT of f[n-m] to be

$G[k] = \sum_{n_1=0}^{N-1} f[n_1] e^{\frac{-2\pi i nk}{N}} e^{\frac{2\pi imk}{N}}$

for some dummy variable of summation $n_1$. I am really stuck as to how to continue though - can someone point me in the right direction?

With many thanks,

Froskoy.

-

This is not the quickest or easiest proof, but I think it shows conceptually what's really going on here. You can also just do a direct calculation, which you may prefer to what follows.

Perhaps the most basic reason the discrete Fourier basis is important is that it is an eigenbasis for the shift operator $S:\mathbb{C}^N \to \mathbb{C}^N$ which maps $\begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{N-1} \end{bmatrix}$ to $\begin{bmatrix} x_{N-1} \\ x_0 \\ x_1 \\ \vdots \\ x_{N-2} \end{bmatrix}$.

For example, one of the (unnormalized) discrete Fourier basis vectors is $v_1 = \begin{bmatrix} 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-1} \end{bmatrix}$, where $\omega = e^{\frac{2 \pi i}{N}}$ is an $N$th root of unity. What happens when you apply $S$ to $v_1$? You get \begin{align*} S v_1 &= \begin{bmatrix} \omega^{N-1} \\ 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{N-2} \end{bmatrix} \\ &= \frac{1}{\omega} v_1 \\ &=\bar{\omega} \,v_1. \end{align*} This shows that $v_1$ is an eigenvector of $S$, with eigenvalue $\frac{1}{\omega} = \bar{\omega}$. You can show similarly that the other discrete Fourier basis vectors are also eigenvectors of $S$, and you will find that the eigenvalue of the $k$th discrete Fourier basis vector is \begin{align*} \lambda_k &= \frac{1}{\omega^k} \\ &= \bar{\omega}^k \\ &= e^{\frac{- 2 \pi i k }{N}}. \end{align*}

It follows that the discrete Fourier basis vectors are also eigenvectors of $S^m$, and the $k$th eigenvalue is $\lambda_k^m = e^{\frac{- 2 \pi i m k }{N}}$.

Suppose the discrete Fourier transform of $x \in \mathbb{C}^N$ is $c$, so that $$x = \sum_{k=0}^{N-1} c_k v_k.$$ ($v_k$ is the $k$th discrete Fourier basis vector.) Then \begin{align*} S^m x &= \sum_{k=0}^{N-1} S^m c_k v_k \\ &= \sum_{k=0}^{N-1} c_k S^m v_k \\ &= \sum_{k=0}^{N-1} c_k \lambda_k^m v_k \\ \end{align*} which shows that the $k$th Fourier coefficient of $Sx$ is \begin{align*} \lambda_k^m c_k &=e^{\frac{-2\pi i m k}{N}} c_k. \end{align*} This is what we wanted to show.

-
Wow! Thank you so much for your help. This really helped me to understand what was going on. –  Froskoy Oct 30 '12 at 14:12

Hint: For fixed $m\in\mathbb Z$, define $g[n]=f[n-m]$ as another $N$-periodic sequence. Then, \begin{align*}G[k] &=\sum_{n=0}^{N-1}g[n]e^{-i2\pi nk/N}\\&=\sum_{n=0}^{N-1}f[n-m]e^{-i2\pi nk/N}\\&=\sum_{\ell=-m}^{N-1-m}f[\ell]e^{-i2\pi (m+\ell)k/N}\\&=e^{-i 2\pi mk/N}\sum_{\ell=-m}^{N-1-m}f[\ell]e^{-i2\pi \ell k/N}\end{align*} Can you now use periodicity of $f$ and $e^{-i2\pi \ell k/N}$ to prove that that last sum is $F[k]$?

-