# Generate all elements of a point group from generating set

Some notes in the beginning:

1. I am a chemist so please excuse my not-so-rigorous knowledge of group theory.
2. My question is explicitly only about 3-dimensional point groups. So I am happy with answers, which only apply in this special case.
3. It is an applied case, where each element has a matrix representation. In the end it should be possible to map e.g. equivalent atoms in molecules onto each other.

Let's assume, that I have a (not necessarily minimal) generating set of a point group. How do I generate efficiently all other symmetry operations?

I denote:

1. $a$ the number of elements in the generating set
2. $o$ the order of the group
3. $S_i$ the i-th symmetry operation.
4. $N_i$ the idempotence number of $S_i$
5. $n_i$ the power of $S_i$
6. $n'_i$ is defined as $N_i - n_i$

## Abelian groups

For abelian groups this is then straighforward. The set of all symmetry operations is the following set:

$\{\prod\limits_{i=1}^a S_i ^ {n_i} | 0 \leq n_i \leq N_i - 2\}$

Which gives: $$o = \prod\limits_{i=1}^a (N_i - 1)$$

## Non abelian groups

If not all elements commute, I have to take the order into account. This gives an upper bound for $o$ with:

$$o = a! \prod\limits_{i=1}^a (N_i - 1)$$

This is already under the assumption, that all elements can be grouped together using "pseudo commutation" (is this the right word?) rules. e.g.: $$C_2 C_3 = C_3^2 C_2$$

Is there a similar general and efficient way in the case of non-abelian-groups?

There is a simple yet efficient algorithm devised by Dimino in the early 70's. It was never published but it's part of the folklore since then. You can find a discussion in [1, chap. 3]. I did write the algorithm in Python many years ago. It was reasonably well tested but my recollections are fuzzy, so please double-check!

# e: identity operator
# G: list of generators
# L: list of all the elements of the group
# N: maximum order of the group we deem acceptable
g = g1 = G[0]
L = [e]
while g != e:
L.append(g)
assert len(L) <= N
g = g*g1
for i in xrange(1,len(G)):
C = [e]
L1 = list(L)
more = True
while more:
assert len(L) <= N
more = False
for g in list(C):
for s in G[:i+1]:
sg = s*g
if sg not in L:
C.append(sg)
L.extend([ sg*t for t in L1 ])
more = True


The cleverness of the algorithm is to use cosets to drastically reduce the number of operations. Indeed, and I should perhaps have started with that, there is of course the brute force algorithm:

L = [e]
L.extend(S)
while True:
new_ones = []
for g in L:
for h in G:
gh = g*h
if gh not in L:
new_ones.append(gh)
if new_ones:
L.extend(new_ones)
else:
break


For a group of order $n$ with $p$ generators, the brute force algorithm scales as $np$ whereas Dimino algorithm scales as $n$ at worst (being rather sloppy here, see [1, chap. 3] for a rigorous analysis).

In any case, Dimino's algorithm superiority over the brute force is only worth it for cubic groups in practice. Note for example that the well-established CCTBX uses a brute force algorithm to compute space groups elements from generators, and that it is fast enough, as stated in the last paragraph before section 4 in [2].

[1] Gregory Butler. Fundamental Algorithms for Permutation Groups. Lecture Notes in Computer Science (Book 559). Springer, 1991.

[2] Ralf W. Grosse-Kunstleve. Algorithms for deriving crystallographic space-group information. Acta Crystallographica Section A, 55:383–395, 1999.

• Thank you very much. Due to your comment I got myself the book from the library and already implemented it similarly. The only problem which still remains, is that the test gh not in L is quite expensive for matrix operations, because I have to account for numerical noise and use something like any([np.allclose(g @ h, x) for x in L]). Do you know of a good speedup for this test? My thoughts up to now are: If infinite rotation axes are excluded, the distance between the matrices under a suitable metric will be larger 0. – mcocdawc Aug 11 '17 at 15:03
• And perhaps a hash function may be defined, that gives same values for numerically similar matrices. Then it would be a test of get_hash(g @ h) in L.keys() and L is a dictionary of hashes to matrices. Perhaps this should be a question on its own in StackOverflow or Mathematics – mcocdawc Aug 11 '17 at 15:04
• You should be able to use integer matrices, no? Or at least matrices of the form $\frac{1}{n}A$ where $A$ is an integer matrix and $n=2,3,6, \cdots$. You can then test for exact equality. Still the same numbers of test but more robust. The CCTBX does exactly that and it's fast enough. But it's written in C++. – user154997 Aug 11 '17 at 15:16
• is it a typo in the line G = list(L)? – marcin Oct 4 '17 at 17:35
• That difference of speed is what I would have expected: for groups with few enough elements, the book keeping of the Dimino algorithm makes it slower but it shines for large groups where the scaling law can express its full power. And yes, this is all so fast anyway that it does not matter much for the usual crystallography groups. It is a bit more useful for the incommensurate groups, not because they have more elements but because there are 100 times more of them! – user154997 Oct 5 '17 at 18:16