International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, p. 51   | 1 | 2 |

Section 1.3.2.7.4. Matrix representation of the discrete Fourier transform (DFT)

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.2.7.4. Matrix representation of the discrete Fourier transform (DFT)

| top | pdf |

By virtue of definitions (i) and (ii),[\eqalign{{\scr F}({\bf N}) {\bf v}_{{\bf \scr k}^{*}} &= {1 \over |\!\det {\bf N}|} {\sum\limits_{{\bf \scr k}}} \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] {\bf u}_{{\bf \scr k}} \cr \bar{\scr F}({\bf N}) {\bf u}_{{\bf \scr k}} &= {\sum\limits_{{\bf \scr k}^{*}}} \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] {\bf v}_{{\bf \scr k}^{*}}}]so that [{\scr F}({\bf N})] and [\bar{\scr F}({\bf N})] may be represented, in the canonical bases of [W_{\bf N}] and [W_{\bf N}^{*}], by the following matrices:[\eqalign{[{\scr F}({\bf N})]_{{\bf {\bf \scr k}{\bf \scr k}}^{*}} &= {1 \over |\!\det {\bf N}|} \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] \cr [\bar{\scr F}({\bf N})]_{{\bf \scr k}^{*} {\bf \scr k}} &= \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})].}]

When N is symmetric, [{\bb Z}^{n}/{\bf N} {\bb Z}^{n}] and [{\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}] may be identified in a natural manner, and the above matrices are symmetric.

When N is diagonal, say [{\bf N} = \hbox{diag} (\nu_{1}, \nu_{2}, \ldots, \nu_{n})], then the tensor product structure of the full multidimensional Fourier transform (Section 1.3.2.4.2.4[link])[{\scr F}_{\bf x} = {\scr F}_{x_{1}} \otimes {\scr F}_{x_{2}} \otimes \ldots \otimes {\scr F}_{x_{n}}]gives rise to a tensor product structure for the DFT matrices. The tensor product of matrices is defined as follows:[{\bf A} \otimes {\bf B} = \pmatrix{a_{11} {\bf B} &\ldots &a_{1n} {\bf B}\cr \vdots & &\vdots\cr a_{n1} {\bf B} &\ldots &a_{nn} {\bf B}\cr}.]Let the index vectors [{\scr k}] and [{\scr k}^{*}] be ordered in the same way as the elements in a Fortran array, e.g. for [{\scr k}] with [{\scr k}_{1}] increasing fastest, [{\scr k}_{2}] next fastest, [\ldots, {\scr k}_{n}] slowest; then[{\scr F}({\bf N}) = {\scr F}(\nu_{1}) \otimes {\scr F}(\nu_{2}) \otimes \ldots \otimes {\scr F}(\nu_{n}),]where[[{\scr F}(\nu_{j})]_{{\scr k}_{j}, \, {\scr k}_{j}^{*}} = {1 \over \nu_{j}} \exp \left(-2 \pi i {{\scr k}_{j}^{*} {\scr k}_{j} \over \nu_{j}}\right),]and[\bar{\scr F}({\bf N}) = \bar{\scr F}(\nu_{1}) \otimes \bar{\scr F}(\nu_{2}) \otimes \ldots \otimes \bar{\scr F}(\nu_{n}),]where[[\bar{\scr F}_{\nu_{j}}]_{{\scr k}_{j}^{*}, \, {\scr k}_{j}} = \exp \left(+2 \pi i {{\scr k}_{j}^{*} {\scr k}_{j} \over \nu_{j}}\right).]








































to end of page
to top of page