Duality between subdivision and decimation of period lattices

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, pp. 46-47 | 1 | 2 |

Section 1.3.2.7.2. Duality between subdivision and decimation of period lattices

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.2. Duality between subdivision and decimation of period lattices

| top | pdf |

1.3.2.7.2.1. Geometric description of sublattices

| top | pdf |

Let $[\Lambda_{\bf A}]$ be a period lattice in $[{\bb R}^{n}]$ with matrix A, and let $[\Lambda_{\bf A}^{*}]$ be the lattice reciprocal to $[\Lambda_{\bf A}]$ , with period matrix $[(A^{-1})^{T}]$ . Let $[\Lambda_{\bf B}, {\bf B}, \Lambda_{\bf B}^{*}]$ be defined similarly, and let us suppose that $[\Lambda_{\bf A}]$ is a sublattice of $[\Lambda_{\bf B}]$ , i.e. that $[\Lambda_{\bf B} \supset \Lambda_{\bf A}]$ as a set.

The relation between $[\Lambda_{\bf A}]$ and $[\Lambda_{\bf B}]$ may be described in two different fashions: (i) multiplicatively, and (ii) additively.

(i) We may write $[{\bf A} = {\bf BN}]$ for some non-singular matrix N with integer entries. N may be viewed as the period matrix of the coarser lattice $[\Lambda_{\bf A}]$ with respect to the period basis of the finer lattice $[\Lambda_{\bf B}]$ . It will be more convenient to write $[{\bf A} = {\bf DB}]$ , where $[{\bf D} = {\bf BNB}^{-1}]$ is a rational matrix (with integer determinant since det $[{\bf D} = \det {\bf N}]$ ) in terms of which the two lattices are related by $[\Lambda_{\bf A} = {\bf D} \Lambda_{\bf B}.]$
(ii) Call two vectors in $[\Lambda_{\bf B}]$ congruent modulo $[\Lambda_{\bf A}]$ if their difference lies in $[\Lambda_{\bf A}]$ . Denote the set of congruence classes (or `cosets') by $[\Lambda_{\bf B} / \Lambda_{\bf A}]$ , and the number of these classes by $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ . The `coset decomposition' $[\Lambda_{\bf B} = \bigcup_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}} ({\boldell} + \Lambda_{\bf A})]$ represents $[\Lambda_{\bf B}]$ as the disjoint union of $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ translates of $[\Lambda_{\bf A} .\; \Lambda_{\bf B} / \Lambda_{\bf A}]$ is a finite lattice with $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ elements, called the residual lattice of $[\Lambda_{\bf B}]$ modulo $[\Lambda_{\bf A}]$ .

The two descriptions are connected by the relation $[[\Lambda_{\bf B} : \Lambda_{\bf A}] = \det {\bf D} = \det {\bf N}]$ , which follows from a volume calculation. We may also combine (i) and (ii) into
$[\displaylines{\quad({\rm iii})\hfill \Lambda_{\bf B} = \bigcup_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}} ({\boldell} + {\bf D} \Lambda_{\bf B})\hfill}]$ which may be viewed as the n-dimensional equivalent of the Euclidean algorithm for integer division: $[\boldell]$ is the `remainder' of the division by $[\Lambda_{\bf A}]$ of a vector in $[\Lambda_{\bf B}]$ , the quotient being the matrix D.

1.3.2.7.2.2. Sublattice relations for reciprocal lattices

| top | pdf |

Let us now consider the two reciprocal lattices $[\Lambda_{\bf A}^{*}]$ and $[\Lambda_{\bf B}^{*}]$ . Their period matrices $[({\bf A}^{-1})^{T}]$ and $[({\bf B}^{-1})^{T}]$ are related by: $[({\bf B}^{-1})^{T} = ({\bf A}^{-1})^{T} {\bf N}^{T}]$ , where $[{\bf N}^{T}]$ is an integer matrix; or equivalently by $[({\bf B}^{-1})^{T} = {\bf D}^{T} ({\bf A}^{-1})^{T}]$ . This shows that the roles are reversed in that $[\Lambda_{\bf B}^{*}]$ is a sublattice of $[\Lambda_{\bf A}^{*}]$ , which we may write:

$[\displaylines{\quad({\rm i})^*\hfill \Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}\hfill}]$
$[\displaylines{\quad({\rm ii})^*\hfill\Lambda_{\bf A}^{*} = \bigcup_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}} ({\boldell}^{*} + \Lambda_{\bf B}^{*}).\hfill}]$ The residual lattice $[\Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}]$ is finite, with $[[\Lambda_{\bf A}^{*}: \Lambda_{\bf B}^{*}] =]$ $[ \det {\bf D} = \det {\bf N} = [\Lambda_{\bf B}: \Lambda_{\bf A}]]$ , and we may again combine $[(\hbox{i})^{*}]$ and $[(\hbox{ii})^{*}]$ into
$[\displaylines{\quad({\rm iii})^*\hfill\Lambda_{\bf A}^{*} = \bigcup_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}} ({\boldell}^{*} + {\bf D}^{T} \Lambda_{\bf A}^{*}).\hfill}]$

1.3.2.7.2.3. Relation between lattice distributions

| top | pdf |

The above relations between lattices may be rewritten in terms of the corresponding lattice distributions as follows: $[\displaylines{\quad (\hbox{i}) \hfill R_{\bf A} = {1 \over |\det {\bf D}|} {\bf D}^{\#} R_{\bf B}^{*} \;\hfill\cr \quad (\hbox{ii}) \hfill R_{\bf B} = T_{{\bf B} / {\bf A}} * R_{\bf A}\qquad \hfill\cr \quad (\hbox{i})^{*} \hfill \;\;R_{\bf B}^{*} = {1 \over |\det {\bf D}|} ({\bf D}^{T})^{\#} R_{\bf A}^{*} \hfill\cr \quad (\hbox{ii})^{*} \hfill R_{\bf A}^{*} =T_{{\bf A} / {\bf B}}^{*} * R_{\bf B}^{*} \qquad\;\;\hfill}]$ where $[T_{{\bf B} / {\bf A}} = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}}} \delta_{({\boldell})}]$ and $[T_{{\bf A}/{\bf B}}^{*} = {\textstyle\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}}} \delta_{({\boldell}^{*})}]$ are (finite) residual-lattice distributions. We may incorporate the factor $[1/|\det {\bf D}|]$ in (i) and $[(\hbox{i})^{*}]$ into these distributions and define $[S_{{\bf B}/{\bf A}} = {1 \over |\det {\bf D}|} T_{{\bf B}/{\bf A}},\quad S_{{\bf A}/{\bf B}}^{*} = {1 \over |\det {\bf D}|} T_{{\bf A}/{\bf B}}^{*}.]$

Since $[|\det {\bf D}| = [\Lambda_{\bf B}: \Lambda_{\bf A}] = [\Lambda_{\bf A}^{*}: \Lambda_{\bf B}^{*}]]$ , convolution with $[S_{{\bf B}/{\bf A}}]$ and $[S_{{\bf A}/{\bf B}}^{*}]$ has the effect of averaging the translates of a distribution under the elements (or `cosets') of the residual lattices $[\Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , respectively. This process will be called `coset averaging'. Eliminating $[R_{\bf A}]$ and $[R_{\bf B}]$ between (i) and (ii), and $[R_{\bf A}^{*}]$ and $[R_{\bf B}^{*}]$ between $[(\hbox{i})^{*}]$ and $[(\hbox{ii})^{*}]$ , we may write: $[\displaylines{\quad (\hbox{i}')\hfill \! R_{\bf A} = {\bf D}^{\#} (S_{{\bf B}/{\bf A}} * R_{\bf A})\;\;\;\hfill\cr \quad (\hbox{ii}')\hfill \! R_{\bf B} = S_{{\bf B}/{\bf A}} * ({\bf D}^{\#} R_{\bf B})\;\;\;\;\hfill\cr \quad (\hbox{i}')^{*}\hfill R_{\bf B}^{*} = ({\bf D}^{T})^{\#} (S_{{\bf A}/{\bf B}}^{*} * R_{\bf B}^{*}) \hfill\cr \quad (\hbox{ii}')^{*}\hfill R_{\bf A}^{*} = S_{{\bf A}/{\bf B}}^{*} * [({\bf D}^{T})^{\#} R_{\bf A}^{*}]. \;\hfill}]$ These identities show that period subdivision by convolution with $[S_{{\bf B}/{\bf A}}]$ (respectively $[S_{{\bf A}/{\bf B}}^{*}]$ ) on the one hand, and period decimation by `dilation' by $[{\bf D}^{\#}]$ on the other hand, are mutually inverse operations on $[R_{\bf A}]$ and $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ and $[R_{\bf B}^{*}]$ ).

1.3.2.7.2.4. Relation between Fourier transforms

| top | pdf |

Finally, let us consider the relations between the Fourier transforms of these lattice distributions. Recalling the basic relation of Section 1.3.2.6.5, $[\eqalign{{\scr F}[R_{\bf A}] &= {1 \over |\det {\bf A}|} R_{\bf A}^{*}\cr &= {1 \over |\det {\bf DB}|} T_{{\bf A}/{\bf B}}^{*} * R_{\bf B}^{*} \quad \quad \quad \quad \quad \quad \hbox{by (ii)}^{*}\cr &= \left({1 \over |\det {\bf D}|} T_{{\bf A}/{\bf B}}^{*}\right) * \left({1 \over |\det {\bf B}|} R_{\bf B}^{*}\right)}]$ i.e. $[\displaylines{\quad (\hbox{iv})\hfill {\scr F}[R_{\bf A}] = S_{{\bf A}/{\bf B}}^{*} * {\scr F}[R_{\bf B}]\hfill}]$ and similarly: $[\displaylines{\quad (\hbox{v})\hfill {\scr F}[R_{\bf B}^{*}] = S_{{\bf B}/{\bf A}} * {\scr F}[R_{\bf A}^{*}].\hfill}]$

Thus $[R_{\bf A}]$ (respectively $[R_{\bf B}^{*}]$ ), a decimated version of $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ ), is transformed by $[{\scr F}]$ into a subdivided version of $[{\scr F}[R_{\bf B}]]$ (respectively $[{\scr F}[R_{\bf A}^{*}]]$ ).

The converse is also true: $[\eqalign{{\scr F}[R_{\bf B}] &= {1 \over |\det {\bf B}|} R_{\bf B}^{*}\cr &= {1 \over |\det {\bf B}|} {1 \over |\det {\bf D}|} ({\bf D}^{T})^{\#} R_{\bf A}^{*}\quad \quad \quad \quad \hbox{by (i)}^{*}\cr &= ({\bf D}^{T})^{\#} \left({1 \over |\det {\bf A}|} R_{\bf A}^{*}\right)}]$ i.e. $[\displaylines{\quad (\hbox{iv}')\hfill {\scr F}[R_{\bf B}] = ({\bf D}^{T})^{\#} {\scr F}[R_{\bf A}]\hfill}]$ and similarly $[\displaylines{\quad (\hbox{v}')\hfill {\scr F}[R_{\bf A}^{*}] = {\bf D}^{\#} {\scr F}[R_{\bf B}^{*}].\hfill}]$

Thus $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ ), a subdivided version of $[R_{\bf A}]$ (respectively $[R_{\bf B}^{*}]$ ) is transformed by $[{\scr F}]$ into a decimated version of $[{\scr F}[R_{\bf A}]]$ (respectively $[{\scr F}[R_{\bf B}^{*}]]$ ). Therefore, the Fourier transform exchanges subdivision and decimation of period lattices for lattice distributions.

Further insight into this phenomenon is provided by applying $[\bar{\scr F}]$ to both sides of (iv) and (v) and invoking the convolution theorem: $[\displaylines{\quad (\hbox{iv}'')\hfill \!\! R_{\bf A} = \bar{\scr F}[S_{{\bf A}/{\bf B}}^{*}] \times R_{\bf B} \;\hfill\cr \quad (\hbox{v}'')\hfill R_{\bf B}^{*} = \bar{\scr F}[S_{{\bf B}/{\bf A}}] \times R_{\bf A}^{*}. \hfill}]$ These identities show that multiplication by the transform of the period-subdividing distribution $[S_{{\bf A}/{\bf B}}^{*}]$ (respectively $[S_{{\bf B}/{\bf A}}]$ ) has the effect of decimating $[R_{\bf B}]$ to $[R_{\bf A}]$ (respectively $[R_{\bf A}^{*}]$ to $[R_{\bf B}^{*}]$ ). They clearly imply that, if $[\boldell \in \Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[\boldell^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , then $[\eqalign{\bar{\scr F}[S_{{\bf A}/{\bf B}}^{*}] ({\boldell}) &= 1 \hbox{ if } {\boldell} = {\bf 0} \;\;\quad (i.e. \hbox{ if } {\boldell} \hbox{ belongs}\cr &{\hbox to 66pt{}}\hbox{to the class of } \Lambda_{\bf A}),\cr &= 0 \hbox{ if } {\boldell} \neq {\bf 0}\hbox{;}\cr \bar{\scr F}[S_{{\bf B}/{\bf A}}] ({\boldell}^{*}) &= 1 \hbox{ if } {\boldell}^{*} = {\bf 0} \quad (i.e. \hbox{ if } {\boldell}^{*} \hbox{ belongs}\cr &{\hbox to 60pt{}} \hbox{ to the class of } \Lambda_{\bf B}^{*}),\cr &= 0 \hbox{ if } {\boldell}^{*} \neq {\bf 0}.}]$ Therefore, the duality between subdivision and decimation may be viewed as another aspect of that between convolution and multiplication.

There is clearly a strong analogy between the sampling/periodization duality of Section 1.3.2.6.6 and the decimation/subdivision duality, which is viewed most naturally in terms of subgroup relationships: both sampling and decimation involve restricting a function to a discrete additive subgroup of the domain over which it is initially given.

1.3.2.7.2.5. Sublattice relations in terms of periodic distributions

| top | pdf |

The usual presentation of this duality is not in terms of lattice distributions, but of periodic distributions obtained by convolving them with a motif.

Given $[T^{0} \in {\scr E}\,' ({\bb R}^{n})]$ , let us form $[R_{\bf A} * T^{0}]$ , then decimate its transform $[(1/|\det {\bf A}|) R_{\bf A}^{*} \times \bar{\scr F}[T^{0}]]$ by keeping only its values at the points of the coarser lattice $[\Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}]$ ; as a result, $[R_{\bf A}^{*}]$ is replaced by $[(1/|\det {\bf D}|) R_{\bf B}^{*}]$ , and the reverse transform then yields $[\displaylines{\hfill{1 \over |\det {\bf D}|} R_{\bf B} * T^{0} = S_{{\bf B}/{\bf A}} * (R_{\bf A} * T^{0})\hfill \hbox{by (ii)},}]$ which is the coset-averaged version of the original $[R_{\bf A} * T^{0}]$ . The converse situation is analogous to that of Shannon's sampling theorem. Let a function $[\varphi \in {\scr E}({\bb R}^{n})]$ whose transform $[\Phi = {\scr F}[\varphi]]$ has compact support be sampled as $[R_{\bf B} \times \varphi]$ at the nodes of $[\Lambda_{\bf B}]$ . Then $[{\scr F}[R_{\bf B} \times \varphi] = {1 \over |\det {\bf B}|} (R_{\bf B}^{*} * \Phi)]$ is periodic with period lattice $[\Lambda_{\bf B}^{*}]$ . If the sampling lattice $[\Lambda_{\bf B}]$ is decimated to $[\Lambda_{\bf A} = {\bf D} \Lambda_{\bf B}]$ , the inverse transform becomes $[\eqalign{{\hbox to 48pt{}}{\scr F}[R_{\bf A} \times \varphi] &= {1 \over |\det {\bf D}|} (R_{\bf A}^{*} * \Phi)\cr &= S_{{\bf A}/{\bf B}}^{*} * (R_{\bf B}^{*} * \Phi){\hbox to 58pt{}}\hbox{by (ii)}^{*},}]$ hence becomes periodized more finely by averaging over the cosets of $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ . With this finer periodization, the various copies of Supp Φ may start to overlap (a phenomenon called `aliasing'), indicating that decimation has produced too coarse a sampling of φ.