Generate all elements of a point group from generating set

Question

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?

Answer 1

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.