Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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 \begin{equation} x = \sum_{k=0}^{N-1} c_k v_k. \end{equation} ($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.

share|improve this answer
1  
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]$?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.