Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

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

Section 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 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[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