Received 29 May 2012
An algorithm for the arithmetic classification of multilattices
A procedure for the construction and the classification of monoatomic multilattices in arbitrary dimension is developed. The algorithm allows one to determine the location of the points of all monoatomic multilattices with a given symmetry, or to determine whether two assigned multilattices are arithmetically equivalent. This approach is based on ideas from integral matrix theory, in particular the reduction to the Smith normal form, and can be coded to provide a classification software package.
A monoatomic (N+1)-lattice is a set of points in that is the union of N+1 identical Bravais lattices, and can be described by a reference (or skeletal) Bravais lattice and N shift vectors , which represent the translations of the additional lattices with respect to the reference one. Equivalently, a monoatomic (N+1)-lattice can be described as a Bravais lattice with N additional identical points per unit cell (cf. e.g. Pitteri & Zanzotto, 2003).
The symmetry of a multilattice is determined by those point-group operations of the skeletal lattice that leave the multilattice invariant, i.e. that interchange the additional points modulo lattice translations (Pitteri & Zanzotto, 1998, 2000; Fadda & Zanzotto, 2000, 2001a). A symmetry operation of an (N+1)-lattice can be identified to a triple , , such that
with a point-group symmetry of the skeletal lattice, an integral matrix that corresponds to the permutation action of on the points of the multilattice, and are lattice vectors. Working in components in a skeletal lattice basis, we can equivalently rewrite equation (1) as
with M = (Mji) a unimodular integral matrix in the lattice group of the skeletal lattice, , a matrix of integers representing a set of lattice translations, and the matrix whose columns are the components of the shift vectors.
To each triple (M,A,T) an (N+n) ×(N+n) matrix of the form
can be associated, and it turns out that the set of all triples that satisfy equation (2) for a given set of shift vectors is a group under matrix multiplication, which is isomorphic to the space group of the multilattice, and which we refer to as the lattice group of the multilattice (Pitteri & Zanzotto, 1998).
We denote by the group of all matrices of the form (3) for arbitrary unimodular integral M, a linear representation of a permutation A, and an integral matrix T: two (N+1)-lattices are arithmetically equivalent if their lattice groups are conjugated in . This notion of equivalence generalizes to multilattices the usual arithmetic classification of simple lattices in Bravais types (Schwarzenberger, 1972; Miller, 1972; Engel, 1986; Pitteri & Zanzotto, 1998).
We refer to (1) as the master equation of the multilattice. It can be used either to compute the shift vectors , given the lattice group, or to compute the lattice group given the skeletal lattice and the shift vectors.
In this work we describe a procedure to solve the master equation for any given skeletal lattice. The procedure is based on ideas from integral matrix diagonalization (Smith, 1861; Newman, 1972; Gohberg et al., 1982; Havas & Majewski, 1997; Dumas et al., 2001; Jäger, 2005) and automatically yields a single representative for each arithmetical equivalence class of multilattices. The idea is as follows: rewriting equation (2) as a linear system of the form
with L an integral matrix and a suitable unknown vector, it is a well known result that L can be written in a canonical form D whose only nonzero entries are integers, are along the diagonal and are arranged in a sequence such that each element divides the next one. Using the canonical form of L, the system (2) decouples into a finite number of elementary equations with integral coefficients and unknowns Xi:
whose solutions have the form
where are integers and tj are real numbers in [0,1) [cf. (14)]. Hence, the transformation to Smith canonical form allows all solutions of equation (2) to be constructed at the sole cost of computing the canonical form itself.
Further, as a side result, this approach yields a simple criterion for the arithmetic equivalence of two given monoatomic multilattices whose underlying skeletal lattices are arithmetically equivalent.
In conclusion, the procedure described in this paper provides a basis for an algorithm for the classification of multilattices with an arbitrary number of points, but also yields a simple method to determine regular sets of points in arbitrary dimensions. This sort of calculation is useful for instance when high-dimensional crystallography is used, via a projection approach, to study quasicrystals or sets of points with noncrystallographic symmetry (Indelicato, Cermelli et al., 2012).
Also, arithmetic equivalence, which yields a finer classification than the classical classification according to affine equivalence classes of space groups, is an essential tool in characterizing and studying reconstructive phase transitions based on the notion of Bain strain, in which there is no symmetry reduction between the parent and product phases (for instance simple cubic and body- or face-centered cubic), but their lattice groups are not arithmetically equivalent (Indelicato, Cermelli et al., 2012; Indelicato, Keef et al., 2012).
In order to improve readability, we have collected all the proofs in Appendix A, and we have devoted the last section to a detailed discussion of two specific examples in three dimensions: the derivation of all inequivalent hexagonal 2-lattices (Fadda & Zanzotto, 2001b) and all inequivalent cubic 3-lattices (Hosoya, 1987). Such results could also be obtained using the Wyckoff positions of the relevant space groups, which can, in turn, be determined in any dimension (Fuksa & Engel, 1994; Eick & Souvignier, 2006), but our approach has the advantage of not requiring the computation of high-dimensional space groups, and taking into account arithmetical equivalence and site symmetry by design.
O(n) is the orthogonal group of , is the group of integral n ×n unimodular matrices, and are the linear space and -module of n ×N real and integral matrices, respectively.
A simple (Bravais) lattice with basis and origin is the set of points in defined by
The point group of is the group of orthogonal transformations that leave the lattice invariant:
The lattice group of is the group of integral unimodular matrices M defined by (4). It follows from this definition that the lattice group is the matrix representation of the point group in the lattice basis.
Two lattices and are arithmetically equivalent if the associated lattice groups and are conjugated in , i.e. there exists such that
Consider now a simple lattice and N points not belonging to and not pairwise equivalent modulo .
An (N+1)-lattice with basis is the union of N+1 simple lattices :
The position of the points with respect to the origin of the lattice , called the skeletal lattice, is given by the shift vectors
Notice that .
The description (5) is one of many possible for a given (N+1)-lattice : in fact, in addition to changing the lattice basis, any relabeling of the points of the form , with a permutation of , yields an equivalent description of the same point set. The shift vectors measured with respect to the new reference lattice have the form
and are related to the original shift vectors by
The lattice vectors
define a translation group that leaves the multilattice invariant, but this is not necessarily the maximal group of translational symmetries of (5). Consider a multilattice as defined in (5), with lattice vectors : we say that the description (5) is essential if all translational symmetries of belong to , i.e. if
This criterion implies that, for instance, a 2-lattice with shift is a simple lattice if and only if the shift is half a lattice vector of the skeletal lattice, as in the case of body-centered lattices.
Loosely speaking, the symmetry of a multilattice is described by those point-group operations of the skeletal lattice that interchange the additional points modulo lattice translations. In order to make this notion precise, we need to characterize how to express permutations of the points of a multilattice in terms of the shift vectors.
The symmetric group SN+1, acting as a group of permutations on the (N+1) points , also acts linearly on the -module generated by the shift vectors as follows:
We denote by the group of matrices corresponding to this action,
which is isomorphic to the symmetric group SN+1 [cf. pp. 309-310 of Pitteri & Zanzotto (2003), and p. 366 of Pitteri & Zanzotto (1998)]. In general, given a finite group , we refer to a group morphism as a permutation representation (permrep) of , and to the associated map as a linear permutation representation.
The symmetry of a multilattice is described by the set of triples
with a point-group symmetry of the skeletal lattice, and for , such that the action of the point-group operation on the shift vectors corresponds to a permutation of the points modulo translations of the lattice or, equivalently, to a change of descriptors of the multilattice. In short, is a symmetry operation of ,
i.e. with M = (Mji), , , ,
Given an (N+1)-lattice with shifts , let be the subset of of matrices M such that there exist and that satisfy the master equation (9). Then
We denote by the set of matrices in defined by
The group is isomorphic to the space group of the multilattice, as discussed in Pitteri & Zanzotto (1998).
Two (N+1)-lattices with lattice groups and are arithmetically equivalent if and are conjugated in , i.e. if there exists a matrix such that
Further, since and are finite, they admit a finite set of generators and , with
Proposition 2 allows one to conclude that if the master equation holds for each generator, then it holds for all elements of the group . Hence equation (9), which holds for every element of , can be replaced by
We discuss here a two-dimensional example to show that the master equation (7) embodies the symmetries of a multilattice. Consider the monoatomic planar 3-lattice with space group p4mm (Fig. 1) and square skeletal lattice: one description of this point set is obtained by letting Q0 = (0,0), Q1 = (1/2,0), Q2 = (0,1/2), and choosing the shift vectors as
A different description arises by choosing , , , with shift vectors
with the transposition of 0 and 1 that fixes 2.
| || Figure 1 |
Different choices of descriptors for the same multilattice.
The point group of the planar square lattice is 4mm, and we choose as generators of the lattice group the integral matrices
The generator M(1) fixes Q0 and permutes Q1 and Q2 modulo the lattice, while the action of M(2) on the points Q0, Q1, Q2 is lattice invariant:
where and are the basis vectors of the square lattice. Hence, the action of the point group of the skeletal lattice on the shifts can be written in the form (7), in terms of the matrices
Alternatively, using the description of the multilattice in terms of the shift vectors , we have
which now involves the matrices
It turns out that these matrices are conjugated to A(1) and A(2) by the element of associated with the permutation : the two descriptions lead to different, but equivalent, forms of the master equation.
The master equation is both a relation that uniquely characterizes the lattice group of a multilattice, given the shift vectors , and an equation in the unknowns , that allows all the multilattices with a given lattice group to be determined. In this section we take the latter point of view, and assume that , or rather , is given. Specifically, the problem we want to solve is:
where the vectors , have components obtained by ordering lexicographically the columns of P and T(k), and L is an integral matrix in , whose explicit form in terms of the generators of is given in Appendix A2.
Consider first a diagonal system of linear equations with integral coefficients
with () and DJi = 0 for , and , i.e.
with1 r = rank D and Dii are integers. The set of the m-tuples of the form
The solutions X of equation (13) have the form X = K+Y, with and , and, conversely, all vectors of this form are solutions.
Consider now the full system of linear equations (12): instead of solving it for a fixed value of the right-hand side, we look for solutions for some integral vector , and rewrite equation (12) in the form
Recall that L is a matrix with integral entries: it is a classical result that every such matrix can be reduced to a diagonal canonical form, the Smith canonical form (Newman, 1972; Gohberg et al., 1982). Precisely, for every matrix there exist matrices and such that
with DIa = 0 for , and Dii divides Di+1i+1 if . The Smith canonical form D is unique, whereas the matrices U and V are not.
where is defined as in (14) with m = nN, V is defined in (16) and, for , is the vector whose components are the integer parts of the components of W. In other words, is the inverse image of by V, translated into the unit cell of the skeletal lattice. Notice that since is a set of solutions of (13), then trivially is a set of solutions of (15). It can be proved that the definition of is independent of the choice of the diagonalizing matrices U,V.
Let , and D its Smith normal form, with r = rank(D): then all solutions of equation (15) belong to . More precisely, the system (15) admits () solutions modulo , each depending on nN-r real parameters, and these are given by
with V such that L = UDV [with and ] and
By construction, the matrix L only depends on the group and its permutation representation . Every solution of the master equation (15) defines a (possibly non-essential) (N+1)-lattice with lattice group , as defined in equation (10), where the translation matrix is computed from .
The question arises naturally as to whether two solutions of the same master equation correspond to arithmetically equivalent multilattices. We shall discuss this topic in the following section.
The main result in this section shows that two equivalent multilattices have the same Smith normal form, and provides a criterion to establish when two multilattices are equivalent.
Consider two equivalent (N+1)-lattices. By definition, their lattice groups and are conjugated by some
In particular, the associated subgroups and of the lattice group of the skeletal lattice, as well as their permutation representations in , are conjugated by H and B, respectively. To simplify, we choose the generators
of and to be pairwise conjugate, which implies in turn that
for every .
with Smith canonical form
Finally, for a given square matrix , we denote by the square matrix of the form
For two equivalent (N+1)-lattices, L and satisfy the relation
where is the integral matrix associated with the conjugating matrices H and B in (19) through the relation (36) in Appendix A. As a consequence, the matrices L and in equation (20) have the same Smith normal form
with are such that L = UDV and , and is a vector of integers.
Conversely, given two non-necessarily equivalent (N+1)-lattices, assume that the groups and defined in Proposition 2, as well as their permutation representations in , are conjugated, i.e. there exists and such that equation (19) holds for some set of generators, and therefore (22) holds. If there exists an integral vector such that (23) holds, then the two multilattices are equivalent.
The above result allows one, among other things, to classify the inequivalent solutions of the master equation, as shown by the following corollary. Consider to this purpose a group with generators , and a permutation representation , and write for the images of the generators of . Let L be the integral nNK ×nN matrix associated with these generators, and let D = U-1 L V-1 be its Smith normal form.
Under the above hypotheses, consider two solutions X and of the master equation in diagonal form , and let S = DX, . Then the corresponding multilattices are arithmetically equivalent if and only if there exists an integral vector such that
for every .
The above criterion for arithmetic equivalence could also be formulated in terms of the integral matrices T and , but we find it easier to use it in this form, as the subsequent examples show.
The procedure discussed in the previous sections can help to solve a classical problem of the arithmetic classification of multilattices, namely how to generate all arithmetic equivalence classes of (N+1)-lattices with a given point group. Notice that the algorithm in §3 involves the lattice group of the skeletal lattice, instead of its point group: this is necessarily so since two skeletal lattices with the same point group could be arithmetically inequivalent, and have therefore lattice groups that are not conjugated in , as is the case for the three cubic lattices in three-dimensions (primitive, face centered and body centered).
We show how to obtain all inequivalent 2-lattices with hexagonal point group 6/mmm and space groups P63/mmc and P6/mmm (Nos. 194 and 191 in International Tables for Crystallography Volume A). These structures are listed as 6, 27 and 28 in Fadda & Zanzotto (2001b).
In this case n = 3, N = 1 and K = 3. The hexagonal Bravais lattice has the point group : there is only a single arithmetic class in this case, and the corresponding lattice group is the matrix representation of the point group in the lattice basis. Using the conventional choices for the lattice basis given in International Tables for Crystallography Volume A (Hahn, 2005), we choose as generators of the integral matrices (Fadda & Zanzotto, 2001b)
together with the inversion, denoted here as M(3). In this case, all possible representations of 6/mmm as a permutation group on 2 elements result by associating to each generator M(i) either the identity permutation or the transposition, corresponding to A(i) = 1 or A(i) = -1, respectively.
We describe below only the two cases that yield non-trivial results.
We discuss here an application to 3-lattices, showing how to obtain the structures with three identical atoms per unit cell and cubic symmetry listed by Hosoya (1987), p. 16, corresponding to the space groups , and (Nos. 221, 225 and 229, respectively, in International Tables for Crystallography Volume A). According to the classification of Hosoya, such structures belong to genus A3 (three identical atoms per unit cell).
The work can be organized following the steps listed in §3, with n = 3 and N = 2: fix one of the three cubic lattices in , consider its lattice group, which is conjugate to the cubic point group Oh, determine all its permutation representations, write the master equation and solve it with the techniques described in the paper.
Since we are interested in permutation representations on sets of three objects, we only need to consider subgroups of Oh of index less or equal to three, namely D4h (index 3), Td (index 2), Th (index 2) and O (index 2).
We use here a presentation of Oh in terms of five generators (K = 5):
The permutation representations corresponding to the maximal subgroups of Oh are
Monoatomic multilattices are periodic structures that generalize simple lattices in any dimension. Their study is important not only for materials science, but also to provide a general description of those quasiperiodic structures that can be obtained by projection of regular sets of points from high- to low-dimensional spaces, via, for instance, the well known cut-and-project scheme for quasicrystals.
A first fundamental problem is to establish whether two multilattices are equivalent in some sense, as well as to determine all multilattices that belong to a given equivalence class. In this context, it has been proved that, in analogy to simple lattices, arithmetic equivalence is strictly finer than affine equivalence (Pitteri & Zanzotto, 1998). Hence, we focus here on arithmetic equivalence.
We approach the problem via the so-called master equation (1), that either characterizes all monoatomic multilattices with a given symmetry or can be used to establish the symmetry group of a given multilattice. By reducing the master equation to a suitable normal form, i.e. the Smith normal form, it is possible to enumerate all solutions, and determine easily which of these solutions are arithmetically equivalent using the criterion in Proposition 1, which only involves the characterization of the centralizer of a finite crystallographic group. Since the centralizers of the crystallographic groups in any dimension are finite or finitely generated, this procedure yields an algorithm which, in principle, can be coded and yields a solution to the arithmetic classification problem for multilattices.
In order to elucidate the basic features of our method, we discuss two examples from the literature, recovering in a few steps some relevant cubic and hexagonal 2- and 3-lattices in three dimensions.
By hypothesis, if , there exist and TM,TH integral matrices such that
Further, by multiplying MP = PAM+TM to the left by M-1 and to the right by AM-1, we find
Hence, since TMAH +MTH and M-1TMAM-1 are matrices of integers, MH and M-1 satisfy the master equation, and is a group. Further, the mapping is single-valued. In fact, noting first that it is implicit in the hypothesis that the shift vectors P provide an essential description of the multilattice, assume that there exists such that P = PA+T, i.e. , where In and IN are the identity in and , respectively. Explicitly, this means that
with the permutation corresponding to A, and this, by Proposition 1, implies that the description is non-essential, which is a contradiction. Hence, the map is a group morphism, and AMH = AMAH. Finally, the above argument shows that the map
is also a group morphism, so that is also a group.
can be rewritten as a conventional system of linear equations. To do so, given and , define
so that a takes values in . Conversely, let and define and i through the identities
where [·] denotes the integer part of its argument. As a varies in , then and i take values in and , respectively, and the relation between a and the pair is bijective. Let
with In the identity matrix in , and
with and Kronecker deltas. The nN-dimensional vector has components that are obtained by ordering the vectors .
with given by
Given , then for all there exist and such that
Then DiiXi = DiiKi + Ci and, as a consequence, Xi = Ki + Yi with Yi = Ci/Di, for , and the statement is proved.
with ti real parameters.
The relation between the master equation and the matrix L can be rewritten in more compact form as follows. For and , consider the fourth-order tensor
For , , let
then the rule
defines a map between , with product *, and which is a group morphism.
Notice first that if M and A are invertible, then W is invertible, with inverse W-1 associated with the tensor , with A-T = (A-1)T. Now let : then
which proves the assertion.
with IN and In the N-dimensional and n-dimensional identity matrices, respectively.
Consider two mutually conjugated generators of and ,
which in turn means that
We first need an auxiliary result.
Given two (N+1)-lattices as above, assume that and , subgroups of the lattice group of the skeletal lattices, as well as their permutation representations in , are conjugated, i.e. there exist and such that writing
for the generators of and , respectively, then
for each . If there exists an integral vector such that
In order to prove Corollary 1, it is enough to apply Proposition 7, with and . In this case, the conjugants H and B are just operations that fix and , respectively, i.e., elements of the centralizers.
The author acknowledges valuable discussions with P. Cermelli and G. Zanzotto. This work was supported by The Leverhulme Trust Research Leadership Award F/00224 AE, the Marie Curie IEF-FP7 project MATVIR, the MATHMAT Project of the University of Padova and the PRIN project 2009 `Mathematics and Mechanics of Biological Assemblies and Soft Tissues'.
Aschbacher, M. (2000). Finite Group Theory, 2nd ed. Cambridge University Press.
Dumas, J., Saunders, B. & Villard, G. (2001). J. Symb. Comp. 32, 71-99.
Eick, B. & Souvignier, B. (2006). Int. J. Quantum Chem. 106, 316-343.
Engel, P. (1986). Geometric Crystallography: An Axiomatic Introduction to Crystallography. Dordrecht: Kluwer Academic Publishers.
Fadda, G. & Zanzotto, G. (2000). Acta Cryst. A56, 36-48.
Fadda, G. & Zanzotto, G. (2001a). Acta Cryst. A57, 492-506.
Fadda, G. & Zanzotto, G. (2001b). Int. J. Non-Linear Mech. 36, 527-547.
Fuksa, J. & Engel, P. (1994). Acta Cryst. A50, 778-792.
Gohberg, I., Lancaster, P. & Rodman, L. (1982). Matrix Polynomials. New York: Academic Press.
Hahn, Th. (2005). International Tables for Crystallography, Vol. A, 5th ed. Heidelberg: Springer.
Havas, G. & Majewski, B. S. (1997). J. Symb. Comp. 24, 399-408.
Hosoya, M. (1987). Bull. College Sci. Univ. Ryukyus, 44, 11-74.
Indelicato, G., Cermelli, P., Salthouse, D. G., Racca, S., Zanzotto, G. & Twarock, R. (2012). J. Math. Biol. 64, 745-773.
Indelicato, G., Keef, T., Cermelli, P., Salthouse, D., Twarock, R. & Zanzotto, G. (2012). Proc. R. Soc. London Ser. A, 468, 1452-1471.
Jäger, G. (2005). Computing, 74, 377-388.
Miller, W. (1972). Symmetry Groups and their Applications. New York: Academic Press.
Newman, M. (1972). Integral Matrices. New York: Academic Press.
Parry, G. P. (2004). Math. Mech. Solids, 9, 411-418.
Pitteri, M. & Zanzotto, G. (1998). Acta Cryst. A54, 359-373.
Pitteri, M. & Zanzotto, G. (2000). Symmetry of Crystalline Structures; a New Look at it, Motivated by the Study of Phase Transformations in Crystals. Proceedings of the International Congress SACAM 2000, edited by S. Adali, E. V. Morozov and V. E. Verijenko, Durban, South Africa.
Pitteri, M. & Zanzotto, G. (2003). Continuum Models for Phase Transitions and Twinning in Crystals. Boca Raton: Chapman and Hall.
Schwarzenberger, R. L. E. (1972). Math. Proc. Camb. Philos. Soc. 72, 325-349.
Smith, H. J. S. (1861). Philos. Trans. R. Soc. London, 151, 293-326.