What's new - EU-Vietnam Business Network (EVBN)

Let ${M_{n \times m}({\bf Z})}$ denote the space of ${n \times m}$ matrices with integer entries, and let ${GL_n({\bf Z})}$ be the group of invertible ${n \times n}$ matrices with integer entries. The Smith normal form takes an arbitrary matrix ${A \in M_{n \times m}({\bf Z})}$ and factorises it as ${A = UDV}$ , where ${U \in GL_n({\bf Z})}$ , ${V \in GL_m({\bf Z})}$ , and ${D}$ is a rectangular diagonal matrix, by which we mean that the principal ${\min(n,m) \times \min(n,m)}$ minor is diagonal, with all other entries zero. Furthermore the diagonal entries of ${D}$ are ${\alpha_1,\dots,\alpha_k,0,\dots,0}$ for some ${0 \leq k \leq \min(n,m)}$ (which is also the rank of ${A}$ ) with the numbers ${\alpha_1,\dots,\alpha_k}$ (known as the invariant factors) principal divisors with ${\alpha_1 | \dots | \alpha_k}$ . The invariant factors are uniquely determined; but there can be some freedom to modify the invertible matrices ${U,V}$ . The Smith normal form can be computed easily; for instance, in SAGE, it can be computed calling the ${{\tt smith\_form()}}$ function from the matrix class. The Smith normal form is also available for other principal ideal domains than the integers, but we will only be focused on the integer case here. For the purposes of this post, we will view the Smith normal form as a primitive operation on matrices that can be invoked as a “black box”.

In this post I would like to record how to use the Smith normal form to computationally manipulate two closely related classes of objects:

Subgroups ${\Gamma \leq {\bf Z}^d}$ of a standard lattice ${{\bf Z}^d}$ (or lattice subgroups for short);
Closed subgroups ${H \leq ({\bf R}/{\bf Z})^d}$ of a standard torus ${({\bf R}/{\bf Z})^d}$ (or closed torus subgroups for short).

(This arose for me due to the need to actually perform (with a collaborator) some numerical calculations with a number of lattice subgroups and closed torus subgroups.) It’s possible that all of these operations are already encoded in some existing object classes in a computational algebra package; I would be interested to know of such packages and classes for lattice subgroups or closed torus subgroups in the comments.

The above two classes of objects are isomorphic to each other by Pontryagin duality: if ${\Gamma \leq {\bf Z}^d}$ is a lattice subgroup, then the orthogonal complement

$\displaystyle \Gamma^\perp := \{ x \in ({\bf R}/{\bf Z})^d: \langle x, \xi \rangle = 0 \forall \xi \in \Gamma \}$

is a closed torus subgroup (with ${\langle,\rangle: ({\bf R}/{\bf Z})^d \times {\bf Z}^d \rightarrow {\bf R}/{\bf Z}}$ the usual Fourier pairing); conversely, if ${H \leq ({\bf R}/{\bf Z})^d}$ is a closed torus subgroup, then

is a closed torus subgroup (withthe usual Fourier pairing); conversely, ifis a closed torus subgroup, then

$\displaystyle H^\perp := \{ \xi \in {\bf Z}^d: \langle x, \xi \rangle = 0 \forall x \in H \}$

is a lattice subgroup. These two operations invert each other: ${(\Gamma^\perp)^\perp = \Gamma}$ and ${(H^\perp)^\perp = H}$ .

is a lattice subgroup. These two operations invert each other:and

Example 1 The orthogonal complement of the lattice subgroup

$\displaystyle 2{\bf Z} \times \{0\} = \{ (2n,0): n \in {\bf Z}\} \leq {\bf Z}^2$

is the closed torus subgroup

$\displaystyle (\frac{1}{2}{\bf Z}/{\bf Z}) \times ({\bf R}/{\bf Z}) = \{ (x,y) \in ({\bf R}/{\bf Z})^2: 2x=0\} \leq ({\bf R}/{\bf Z})^2$

and conversely.

Let us focus first on lattice subgroups ${\Gamma \leq {\bf Z}^d}$ . As all such subgroups are finitely generated abelian groups, one way to describe a lattice subgroup is to specify a set ${v_1,\dots,v_n \in \Gamma}$ of generators of ${\Gamma}$ . Equivalently, we have

$\displaystyle \Gamma = A {\bf Z}^n$

where ${A \in M_{d \times n}({\bf Z})}$ is the matrix whose columns are ${v_1,\dots,v_n}$ . Applying the Smith normal form ${A = UDV}$ , we conclude that

whereis the matrix whose columns are. Applying the Smith normal form, we conclude that

$\displaystyle \Gamma = UDV{\bf Z}^n = UD{\bf Z}^n$

so in particular ${\Gamma}$ is isomorphic (with respect to the automorphism group ${GL_d({\bf Z})}$ of ${{\bf Z}^d}$ ) to ${D{\bf Z}^n}$ . In particular, we see that ${\Gamma}$ is a free abelian group of rank ${k}$ , where ${k}$ is the rank of ${D}$ (or ${A}$ ). This representation also allows one to trim the representation ${A {\bf Z}^n}$ down to ${U D'{\bf Z}^k}$ , where ${D' \in M_{d \times k}}$ is the matrix formed from the ${k}$ left columns of ${D}$ ; the columns of ${UD'}$ then give a basis for ${\Gamma}$ . Let us call this a trimmed representation of ${A{\bf Z}^n}$ .

so in particularis isomorphic (with respect to the automorphism groupof) to. In particular, we see thatis a free abelian group of rank, whereis the rank of(or). This representation also allows one to trim the representationdown to, whereis the matrix formed from theleft columns of; the columns ofthen give a basis for. Let us call this a trimmed representation of

Example 2 Let ${\Gamma \leq {\bf Z}^3}$ be the lattice subgroup generated by ${(1,3,1)}$ , ${(2,-2,2)}$ , ${(3,1,3)}$ , thus ${\Gamma = A {\bf Z}^3}$ with ${A = \begin{pmatrix} 1 & 2 & 3 \\ 3 & -2 & 1 \\ 1 & 2 & 3 \end{pmatrix}}$ . A Smith normal form for ${A}$ is given by

$\displaystyle A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 0 & 0 \\ 3 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 8 & 0 \\ 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 3 & -2 & 1 \\ -1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$

so ${A{\bf Z}^3}$ is a rank two lattice with a basis of ${(3,1,3) \times 1 = (3,1,3)}$ and ${(1,0,1) \times 8 = (8,0,8)}$ (and the invariant factors are ${1}$ and ${8}$ ). The trimmed representation is

$\displaystyle A {\bf Z}^3 = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 0 & 0 \\ 3 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 8 \\ 0 & 0 \end{pmatrix} {\bf Z}^2 = \begin{pmatrix} 3 & 8 \\ 1 & 0 \\ 3 & 8 \end{pmatrix} {\bf Z}^2.$

There are other Smith normal forms for ${A}$ , giving slightly different representations here, but the rank and invariant factors will always be the same.

By the above discussion we can represent a lattice subgroup ${\Gamma \leq {\bf Z}^d}$ by a matrix ${A \in M_{d \times n}({\bf Z})}$ for some ${n}$ ; this representation is not unique, but we will address this issue shortly. For now, we focus on the question of how to use such data representations of subgroups to perform basic operations on lattice subgroups. There are some operations that are very easy to perform using this data representation:

(Applying a linear transformation) if ${T \in M_{d' \times d}({\bf Z})}$ , so that ${T}$ is also a linear transformation from ${{\bf Z}^d}$ to ${{\bf Z}^{d'}}$ , then ${T}$ maps lattice subgroups to lattice subgroups, and clearly maps the lattice subgroup ${A{\bf Z}^n}$ to ${(TA){\bf Z}^n}$ for any ${A \in M_{d \times n}({\bf Z})}$ .
(Sum) Given two lattice subgroups ${A_1 {\bf Z}^{n_1}, A_2 {\bf Z}^{n_2} \leq {\bf Z}^d}$ for some ${A_1 \in M_{d \times n_1}({\bf Z})}$ , ${A_2 \in M_{d \times n_2}({\bf Z})}$ , the sum ${A_1 {\bf Z}^{n_1} + A_2 {\bf Z}^{n_2}}$ is equal to the lattice subgroup ${A {\bf Z}^{n_1+n_2}}$ , where ${A = (A_1 A_2) \in M_{d \times n_1 + n_2}({\bf Z})}$ is the matrix formed by concatenating the columns of ${A_1}$ with the columns of ${A_2}$ .
(Direct sum) Given two lattice subgroups ${A_1 {\bf Z}^{n_1} \leq {\bf Z}^{d_1}}$ , ${A_2 {\bf Z}^{n_2} \leq {\bf Z}^{d_2}}$ , the direct sum ${A_1 {\bf Z}^{n_1} \times A_2 {\bf Z}^{n_2}}$ is equal to the lattice subgroup ${A {\bf Z}^{n_1+n_2}}$ , where ${A = \begin{pmatrix} A_1 & 0 \\ 0 & A_2 \end{pmatrix} \in M_{d_1+d_2 \times n_1 + n_2}({\bf Z})}$ is the block matrix formed by taking the direct sum of ${A_1}$ and ${A_2}$ .

One can also use Smith normal form to detect when one lattice subgroup ${B {\bf Z}^m \leq {\bf Z}^d}$ is a subgroup of another lattice subgroup ${A {\bf Z}^n \leq {\bf Z}^d}$ . Using Smith normal form factorization ${A = U D V}$ , with invariant factors ${\alpha_1|\dots|\alpha_k}$ , the relation ${B {\bf Z}^m \leq A {\bf Z}^n}$ is equivalent after some manipulation to

$\displaystyle U^{-1} B {\bf Z}^m \leq D {\bf Z}^n.$

The group ${U^{-1} B {\bf Z}^m}$ is generated by the columns of ${U^{-1} B}$ , so this gives a test to determine whether ${B {\bf Z}^{m} \leq A {\bf Z}^{n}}$ : the ${i^{th}}$ row of ${U^{-1} B}$ must be divisible by ${\alpha_i}$ for ${i=1,\dots,k}$ , and all other rows must vanish.

The groupis generated by the columns of, so this gives a test to determine whether: therow ofmust be divisible byfor, and all other rows must vanish.

Example 3 To test whether the lattice subgroup ${\Gamma'}$ generated by ${(1,1,1)}$ and ${(0,2,0)}$ is contained in the lattice subgroup ${\Gamma = A{\bf Z}^3}$ from Example 2, we write ${\Gamma'}$ as ${B {\bf Z}^2}$ with ${B = \begin{pmatrix} 1 & 0 \\ 1 & 2 \\ 1 & 0\end{pmatrix}}$ , and observe that

$\displaystyle U^{-1} B = \begin{pmatrix} 1 & 2 \\ -2 & -6 \\ 0 & 0 \end{pmatrix}.$

The first row is of course divisible by ${1}$ , and the last row vanishes as required, but the second row is not divisible by ${8}$ , so ${\Gamma'}$ is not contained in ${\Gamma}$ (but ${4\Gamma'}$ is); also a similar computation verifies that ${\Gamma}$ is conversely contained in ${\Gamma'}$ .

One can now test whether ${B{\bf Z}^m = A{\bf Z}^n}$ by testing whether ${B{\bf Z}^m \leq A{\bf Z}^n}$ and ${A{\bf Z}^n \leq B{\bf Z}^m}$ simultaneously hold (there may be more efficient ways to do this, but this is already computationally manageable in many applications). This in principle addresses the issue of non-uniqueness of representation of a subgroup ${\Gamma}$ in the form ${A{\bf Z}^n}$ .

Next, we consider the question of representing the intersection ${A{\bf Z}^n \cap B{\bf Z}^m}$ of two subgroups ${A{\bf Z}^n, B{\bf Z}^m \leq {\bf Z}^d}$ in the form ${C{\bf Z}^p}$ for some ${p}$ and ${C \in M_{d \times p}({\bf Z})}$ . We can write

$\displaystyle A{\bf Z}^n \cap B{\bf Z}^m = \{ Ax: Ax = By \hbox{ for some } x \in {\bf Z}^n, y \in {\bf Z}^m \}$

$\displaystyle = (A 0) \{ z \in {\bf Z}^{n+m}: (A B) z = 0 \}$

where ${(A B) \in M_{d \times n+m}({\bf Z})}$ is the matrix formed by concatenating ${A}$ and ${B}$ , and similarly for ${(A 0) \in M_{d \times n+m}({\bf Z})}$ (here we use the change of variable ${z = \begin{pmatrix} x \\ -y \end{pmatrix}}$ ). We apply the Smith normal form to ${(A B)}$ to write

whereis the matrix formed by concatenatingand, and similarly for(here we use the change of variable). We apply the Smith normal form toto write

$\displaystyle (A B) = U D V$

where ${U \in GL_d({\bf Z})}$ , ${D \in M_{d \times n+m}({\bf Z})}$ , ${V \in GL_{n+m}({\bf Z})}$ with ${D}$ of rank ${k}$ . We can then write

wherewithof rank. We can then write

$\displaystyle \{ z \in {\bf Z}^{n+m}: (A B) z = 0 \} = V^{-1} \{ w \in {\bf Z}^{n+m}: Dw = 0 \}$

$\displaystyle = V^{-1} (\{0\}^k \times {\bf Z}^{n+m-k})$

(making the change of variables ${w = Vz}$ ). Thus we can write ${A{\bf Z}^n \cap B{\bf Z}^m = C {\bf Z}^{n+m-k}}$ where ${C \in M_{d \times n+m-k}({\bf Z})}$ consists of the right ${n+m-k}$ columns of ${(A 0) V^{-1} \in M_{d \times n+m}({\bf Z})}$ .

(making the change of variables). Thus we can writewhereconsists of the rightcolumns of

Example 4 With the lattice ${A{\bf Z}^3}$ from Example 2, we shall compute the intersection of ${A{\bf Z}^3}$ with the subgroup ${{\bf Z}^2 \times \{0\}}$ , which one can also write as ${B{\bf Z}^2}$ with ${B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix}}$ . We obtain a Smith normal form

$\displaystyle (A B) = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} 3 & -2 & 1 & 0 & 1 \\ 1 & 2 & 3 & 1 & 0 \\ 1 & 2 & 3 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{pmatrix}$

so ${k=3}$ . We have

$\displaystyle (A 0) V^{-1} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 3 & 0 & -8 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}$

and so we can write ${A{\bf Z}^3 \cap B{\bf Z}^2 = C{\bf Z}^2}$ where

$\displaystyle C = \begin{pmatrix} 0 & 0 \\ 0 & -8 \\ 0 & 0 \end{pmatrix}.$

One can trim this representation if desired, for instance by deleting the first column of ${C}$ (and replacing ${{\bf Z}^2}$ with ${{\bf Z}}$ ). Thus the intersection of ${A{\bf Z}^3}$ with ${{\bf Z}^2 \times \{0\}}$ is the rank one subgroup generated by ${(0,-8,0)}$ .

A similar calculation allows one to represent the pullback ${T^{-1} (A {\bf Z}^n) \leq {\bf Z}^{d'}}$ of a subgroup ${A{\bf Z}^n \leq {\bf Z}^d}$ via a linear transformation ${T \in M_{d \times d'}({\bf Z})}$ , since

$\displaystyle T^{-1} (A {\bf Z}^n) = \{ x \in {\bf Z}^{d'}: Tx = Ay \hbox{ for some } y \in {\bf Z}^m \}$

$\displaystyle = (I 0) \{ z \in {\bf Z}^{d'+m}: (T A) z = 0 \}$

where ${(I 0) \in M_{d' \times d'+m}({\bf Z})}$ is the concatenation of the ${d' \times d'}$ identity matrix ${I}$ and the ${d' \times m}$ zero matrix. Applying the Smith normal form to write ${(T A) = UDV}$ with ${D}$ of rank ${k}$ , the same argument as before allows us to write ${T^{-1}(A{\bf Z}^n) = C {\bf Z}^{d'+m-k}}$ where ${C \in M_{d' \times d'+m-k}}$ consists of the right ${d'+m-k}$ columns of ${(I 0) V^{-1} \in M_{d' \times d'+m}({\bf Z})}$ .

whereis the concatenation of theidentity matrixand thezero matrix. Applying the Smith normal form to writewithof rank, the same argument as before allows us to writewhereconsists of the rightcolumns of

Among other things, this allows one to describe lattices given by systems of linear equations and congruences in the ${A{\bf Z}^n}$ format. Indeed, the set of lattice vectors ${x \in {\bf Z}^d}$ that solve the system of congruences

$\displaystyle \alpha_i | x \cdot v_i \ \ \ \ \ (1)$

for ${i=1,\dots,k}$ , some natural numbers ${\alpha_i}$ , and some lattice vectors ${v_i \in {\bf Z}^d}$ , together with an additional system of equations ${j=1,\dots,l}$ and some lattice vectors ${w_j \in {\bf Z}^d}$ , can be written as ${T^{-1}(A {\bf Z}^k)}$ where ${T \in M_{k+l \times d}({\bf Z})}$ is the matrix with rows ${v_1,\dots,v_k,w_1,\dots,w_l}$ , and ${A \in M_{k+l \times k}({\bf Z})}$ is the diagonal matrix with diagonal entries ${\alpha_1,\dots,\alpha_k}$ . Conversely, any subgroup ${A{\bf Z}^n}$ can be described in this form by first using the trimmed representation ${A{\bf Z}^n = UD'{\bf Z}^k}$ , at which point membership of a lattice vector ${x \in {\bf Z}^d}$ in ${A{\bf Z}^n}$ is seen to be equivalent to the congruences
for, some natural numbers, and some lattice vectors, together with an additional system of equations

$\displaystyle x \cdot w_j = 0 \ \ \ \ \ (2)$

forand some lattice vectors, can be written aswhereis the matrix with rows, andis the diagonal matrix with diagonal entries. Conversely, any subgroupcan be described in this form by first using the trimmed representation, at which point membership of a lattice vectorinis seen to be equivalent to the congruences

$\displaystyle \alpha_i | U^{-1} x \cdot e_i$

for ${i=1,\dots,k}$ (where ${k}$ is the rank, ${\alpha_1,\dots,\alpha_k}$ are the invariant factors, and ${e_1,\dots,e_d}$ is the standard basis of ${{\bf Z}^d}$ ) together with the equations

for(whereis the rank,are the invariant factors, andis the standard basis of) together with the equations

$\displaystyle U^{-1} x \cdot e_j = 0$

for ${j=k+1,\dots,d}$ . Thus one can obtain a representation in the form ${l=d-k}$ , and ${v_1,\dots,v_k,w_1,\dots,w_{d-k}}$ to be the rows of ${U^{-1}}$ in order.

for. Thus one can obtain a representation in the form (1) (2) with, andto be the rows ofin order.

Example 5 With the lattice subgroup ${A{\bf Z}^3}$ from Example 2, we have ${U^{-1} = \begin{pmatrix} 0 & 1 & 0 \\ 0 & -3 & 1 \\ 1 & 0 & -1 \end{pmatrix}}$ , and so ${A{\bf Z}^3}$ consists of those triples ${(x_1,x_2,x_3)}$ which obey the (redundant) congruence

$\displaystyle 1 | x_2,$

the congruence

$\displaystyle 8 | -3x_2 + x_3$

and the identity

$\displaystyle x_1 - x_3 = 0.$

Conversely, one can use the above procedure to convert the above system of congruences and identities back into a form ${A' {\bf Z}^{n'}}$ (though depending on which Smith normal form one chooses, the end result may be a different representation of the same lattice group ${A{\bf Z}^3}$ ).

Now we apply Pontryagin duality. We claim the identity

$\displaystyle (A{\bf Z}^n)^\perp = \{ x \in ({\bf R}/{\bf Z})^d: A^Tx = 0 \}$

for any ${A \in M_{d \times n}({\bf Z})}$ (where ${A^T \in M_{n \times d}({\bf Z})}$ induces a homomorphism from ${({\bf R}/{\bf Z})^d}$ to ${({\bf R}/{\bf Z})^n}$ in the obvious fashion). This can be verified by direct computation when ${A}$ is a (rectangular) diagonal matrix, and the general case then easily follows from a Smith normal form computation (one can presumably also derive it from the category-theoretic properties of Pontryagin duality, although I will not do so here). So closed torus subgroups that are defined by a system of linear equations (over ${{\bf R}/{\bf Z}}$ , with integer coefficients) are represented in the form ${(A{\bf Z}^n)^\perp}$ of an orthogonal complement of a lattice subgroup. Using the trimmed form ${A{\bf Z}^n = U D' {\bf Z}^k}$ , we see that

for any(whereinduces a homomorphism fromtoin the obvious fashion). This can be verified by direct computation whenis a (rectangular) diagonal matrix, and the general case then easily follows from a Smith normal form computation (one can presumably also derive it from the category-theoretic properties of Pontryagin duality, although I will not do so here). So closed torus subgroups that are defined by a system of linear equations (over, with integer coefficients) are represented in the formof an orthogonal complement of a lattice subgroup. Using the trimmed form, we see that

$\displaystyle (A{\bf Z}^n)^\perp = \{ x \in ({\bf R}/{\bf Z})^d: (UD')^T x = 0 \}$

$\displaystyle = (U^{-1})^T \{ y \in ({\bf R}/{\bf Z})^d: (D')^T x = 0 \}$

$\displaystyle = (U^{-1})^T (\frac{1}{\alpha_1} {\bf Z}/{\bf Z} \times \dots \times \frac{1}{\alpha_k} {\bf Z}/{\bf Z} \times ({\bf R}/{\bf Z})^{d-k}),$

giving an explicit representation “in coordinates” of such a closed torus subgroup. In particular we can read off the isomorphism class of a closed torus subgroup as the product of a finite number of cyclic groups and a torus:

$\displaystyle (A{\bf Z}^n)^\perp \equiv ({\bf Z}/\alpha_1 {\bf Z}) \times \dots \times ({\bf Z}/\alpha_k{\bf Z}) \times ({\bf R}/{\bf Z})^{d-k}.$

Example 6 The orthogonal complement of the lattice subgroup ${A{\bf Z}^3}$ from Example 2 is the closed torus subgroup

$\displaystyle (A{\bf Z}^3)^\perp = \{ (x_1,x_2,x_3) \in ({\bf R}/{\bf Z})^3: x_1 + 3x_2 + x_3$

$\displaystyle = 2x_1 - 2x_2 + 2x_3 = 3x_1 + x_2 + 3x_3 = 0 \};$

using the trimmed representation of ${(A{\bf Z}^3)^\perp}$ , one can simplify this a little to

$\displaystyle (A{\bf Z}^3)^\perp = \{ (x_1,x_2,x_3) \in ({\bf R}/{\bf Z})^3: 3x_1 + x_2 + 3x_3$

$\displaystyle = 8 x_1 + 8x_3 = 0 \}$

and one can also write this as the image of the group ${\{ 0\} \times (\frac{1}{8}{\bf Z}/{\bf Z}) \times ({\bf R}/{\bf Z})}$ under the torus isomorphism

$\displaystyle (y_1,y_2,y_3) \mapsto (y_3, y_1 - 3y_2, y_2 - y_3).$

In other words, one can write

$\displaystyle (A{\bf Z}^3)^\perp = \{ (y,0,-y) + (0,-\frac{3a}{8},\frac{a}{8}): y \in {\bf R}/{\bf Z}; a \in {\bf Z}/8{\bf Z} \}$

so that ${(A{\bf Z}^3)^\perp}$ is isomorphic to ${{\bf R}/{\bf Z} \times {\bf Z}/8{\bf Z}}$ .

We can now dualize all of the previous computable operations on subgroups of ${{\bf Z}^d}$ to produce computable operations on closed subgroups of ${({\bf R}/{\bf Z})^d}$ . For instance:

To form the intersection or sum of two closed torus subgroups ${(A_1 {\bf Z}^{n_1})^\perp, (A_2 {\bf Z}^{n_2})^\perp \leq ({\bf R}/{\bf Z})^d}$ , use the identities
$\displaystyle (A_1 {\bf Z}^{n_1})^\perp \cap (A_2 {\bf Z}^{n_2})^\perp = (A_1 {\bf Z}^{n_1} + A_2 {\bf Z}^{n_2})^\perp$

and

$\displaystyle (A_1 {\bf Z}^{n_1})^\perp + (A_2 {\bf Z}^{n_2})^\perp = (A_1 {\bf Z}^{n_1} \cap A_2 {\bf Z}^{n_2})^\perp$

and then calculate the sum or intersection of the lattice subgroups ${A_1 {\bf Z}^{n_1}, A_2 {\bf Z}^{n_2}}$ by the previous methods. Similarly, the operation of direct sum of two closed torus subgroups dualises to the operation of direct sum of two lattice subgroups.
To determine whether one closed torus subgroup ${(A_1 {\bf Z}^{n_1})^\perp \leq ({\bf R}/{\bf Z})^d}$ is contained in (or equal to) another closed torus subgroup ${(A_2 {\bf Z}^{n_2})^\perp \leq ({\bf R}/{\bf Z})^d}$ , simply use the preceding methods to check whether the lattice subgroup ${A_2 {\bf Z}^{n_2}}$ is contained in (or equal to) the lattice subgroup ${A_1 {\bf Z}^{n_1}}$ .
To compute the pull back ${T^{-1}( (A{\bf Z}^n)^\perp )}$ of a closed torus subgroup ${(A{\bf Z}^n)^\perp \leq ({\bf R}/{\bf Z})^d}$ via a linear transformation ${T \in M_{d' \times d}({\bf Z})}$ , use the identity
$\displaystyle T^{-1}( (A{\bf Z}^n)^\perp ) = (T^T A {\bf Z}^n)^\perp.$

Similarly, to compute the image ${T( (B {\bf Z}^m)^\perp )}$ of a closed torus subgroup ${(B {\bf Z}^m)^\perp \leq ({\bf R}/{\bf Z})^{d'}}$ , use the identity

$\displaystyle T( (B{\bf Z}^m)^\perp ) = ((T^T)^{-1} B {\bf Z}^m)^\perp.$

Example 7 Suppose one wants to compute the sum of the closed torus subgroup ${(A{\bf Z}^3)^\perp}$ from Example 6 with the closed torus subgroup ${\{0\}^2 \times {\bf R}/{\bf Z}}$ . This latter group is the orthogonal complement of the lattice subgroup ${{\bf Z}^2 \times \{0\}}$ considered in Example 4. Thus we have ${(A{\bf Z}^3)^\perp + (\{0\}^2 \times {\bf R}/{\bf Z}) = (C{\bf Z}^2)^\perp}$ where ${C}$ is the matrix from Example 6; discarding the zero column, we thus have

$\displaystyle (A{\bf Z}^3)^\perp + (\{0\}^2 \times {\bf R}/{\bf Z}) = \{ (x_1,x_2,x_3): -8x_2 = 0 \}.$