# Thread: 2D discrete Fourier transform

1. ## 2D discrete Fourier transform

Hi guys

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.

2. Originally Posted by Niles_M
Hi guys

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.
Let me preface this post by saying that I have absolutely no experience with Fourier transforms, but I saw your other post describing your urgency, etc., so I decided to post this in the event that it turns out to be useful.

This link on Wikipedia is for the section entitled Expressing the inverse DFT in terms of the DFT as part of the article Discrete Fourier transform. Without experience, I cannot determine whether or not this applies to your situation, but it seemed there was a chance.

Good luck.

3. Thanks, I'll take a look at it to see if it helps. I feel bad asking this, but do you know of the best way of directing attention to this post?

By the way, I am doing this numerically. Is it because I need to look at large systems in order to see only the k=0 contribution?

4. Originally Posted by Niles_M
Thanks, I'll take a look at it to see if it helps. I feel bad asking this, but do you know of the best way of directing attention to this post?
Sorry, I don't know. Maybe a moderator will be able to give some useful info in that regard. From what I gather, you are very considerate when it comes to rules and such, and are merely in an unusual situation and don't know what to do, so I would expect a friendly response from moderators.

Originally Posted by Niles_M
By the way, I am doing this numerically. Is it because I need to look at large systems in order to see only the k=0 contribution?
I hope this wasn't directed towards me, because again I cite my lack of knowledge/experience. I'm writing this additional note just so you know I didn't ignore it.

5. Thanks, it is very kind of you. I contacted a moderator.

6. One last note, which may or may not be useful; I noticed the Wikipedia article is written in terms of complex numbers, and in case there was an issue with this, complex numbers can be treated in the same way ordered pairs are treated, in many ways. a + bi could be a way of expressing the ordered pair (a, b), similar to how in nonnegative integers $2^a3^b$ can encode (a, b) as a nonnegative integer. Of course there are things like complex conjugates which may or may not change things. Just an idea.

7. Originally Posted by Niles_M
Hi guys

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?
It is not really a paradox, because all the entries in the original matrix g(R) are the same (they are all equal to 1). So the single piece of information given by the k=0 term is sufficient to re-create the matrix.

If g(R) had contained two or more distinct entries then the FT would have contained more than one nonzero term.

8. "So the single piece of information given by the k=0 term is sufficient to re-create the matrix."

I agree with that, but when I carry out the sum

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

then all k-terms are there, so f(k) also has k!=0 terms (which is should not, since it is homogeneous). That is what I call the paradox.