Matrix representation of the discrete Fourier transform (DFT)

Bricogne, G.

doi:10.1107/97809553602060000551

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

pdf | chapter contents | chapter index | related articles

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

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

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, 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) $[{\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).]$