Homework Help: Lattice discrete Fourier transforms

1. May 12, 2010

Niles

1. The problem statement, all variables and given/known data
Hi

Say I have a 5x5 lattice, where each entry (or we can call it site) contains the number 1. Now, on the lattice we have a function g(R), which is equal to the number on the site. In this case g(R)=1 for all sites (here R is a vector from the point (3,3), which denotes the site we are talking about).

Now I wish to Fourier transform the function g, and I use the lattice discrete FT

$$f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R})$$

where k is a vector. Now, since each site contains the number 1, the system is homogeneous, and from the inverse Fourier transform,

$$g(\mathbf R) = \sum_{\mathbf k} e^{-i\mathbf k\mathbf R} f(\mathbf k),$$

we see that only the k=0-term can survive, since g(R) is constant. But by performing the sum

$$f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R}),$$

it is quite obvious that all terms are there, i.e. it is not only the k=0 term that survives. That is a paradox I cannot explain. Can you guys shed some light on this?

Best,
Niles.

Last edited: May 12, 2010
2. May 12, 2010

jbunniii

Your exponents are missing some factors. Instead of

$$e^{-ik\cdot R}$$

it should be

$$e^{-2\pi i k \cdot R / N}$$

where in your case $N = 5$.

Then for $k \neq 0$ you will be summing evenly spaced samples around the unit circle, so the result will be zero.

Last edited: May 12, 2010
3. May 12, 2010

jbunniii

P.S. Since your function is constant, the 2d DFT is equivalent to two iterated 1d DFT's. If I write $k = (k_1, k_2)$ and $R = (R_1, R_2)$, then

$$f(k) = \sum_R e^{2\pi i (k_1 R_1 + k_2 R_2) / N} = \sum_{R_1} e^{2\pi i k_1 R_1 / N} \sum_{R_2} e^{2\pi i k_2 R_2 / N}$$

4. May 12, 2010

Niles

Thanks for helping. I just tried doing it again (with the correct factor in the exponential) for a 3x3 system, but still other terms show up (I tried writing it up manually).

5. May 13, 2010

Niles

I'm sorry to bump the thread, but it is extremely important that this issue gets solved (I potentially have to redo 6 months of course work), and I am all out of good ideas.

Last edited: May 13, 2010
6. May 13, 2010

jbunniii

I'm not sure what is going wrong for you. Maybe I am misinterpreting what you want to do. I wrote the following segment of Matlab code (actually Octave, but it should work for Matlab as well) to calculate your sum:

Code (Text):

fid = fopen('out.txt','w');

for a = -2:2
for b = -2:2
k = [a b];
f_k = 0;
for m = -2:2
for n = -2:2
r = [m n];
f_k = f_k + exp(i*2*pi * (k * r') / 5);
end
end
fprintf(fid, 'f([%d %d]) = %f + i*%f\n', a, b, real(f_k), imag(f_k));
end
end

fclose(fid);

Here is the result I got:

f([-2 -2]) = 0.000000 + i*0.000000
f([-2 -1]) = -0.000000 + i*0.000000
f([-2 0]) = -0.000000 + i*0.000000
f([-2 1]) = -0.000000 + i*-0.000000
f([-2 2]) = 0.000000 + i*0.000000
f([-1 -2]) = -0.000000 + i*0.000000
f([-1 -1]) = -0.000000 + i*0.000000
f([-1 0]) = 0.000000 + i*-0.000000
f([-1 1]) = -0.000000 + i*-0.000000
f([-1 2]) = 0.000000 + i*0.000000
f([0 -2]) = -0.000000 + i*0.000000
f([0 -1]) = 0.000000 + i*0.000000
f([0 0]) = 25.000000 + i*0.000000
f([0 1]) = 0.000000 + i*0.000000
f([0 2]) = -0.000000 + i*0.000000
f([1 -2]) = 0.000000 + i*0.000000
f([1 -1]) = -0.000000 + i*0.000000
f([1 0]) = 0.000000 + i*0.000000
f([1 1]) = -0.000000 + i*-0.000000
f([1 2]) = -0.000000 + i*0.000000
f([2 -2]) = 0.000000 + i*0.000000
f([2 -1]) = -0.000000 + i*0.000000
f([2 0]) = -0.000000 + i*0.000000
f([2 1]) = -0.000000 + i*0.000000
f([2 2]) = 0.000000 + i*0.000000

7. May 13, 2010

Niles

No no, you got it. What I want to do is to find f(k). But you change the value of the k-vector? Why is it that you do that, instead of leaving it just as (kx,ky)?

8. May 13, 2010

Niles

Wait, ignore my post #7. I will try out your example, and return when I get a result.

9. May 13, 2010

Niles

Ok, now I get the same table as you. But the problem comes when we choose e.g. k=(0, 1.5)T - there f(k) blows up (I get f(k)=6.18 in that case).

10. May 13, 2010

jbunniii

Yes, if you look at points that do not have integer coordinates, you will not get zero. In fact, if you evaluate f at all points (instead of just integers), you will obtain a 2-dimensional "sinc" function.

The reason for this is that you only use finitely many terms in the sum. You are in effect calculating the Fourier transform of a 2-dimensional "rectangle" function.

If you use more terms, you will more closely approximate an "impulse."

See here for a visualization: