Dear Gap-Forum,

Christopher Bates asked (some weeks ago -- collecting the answer took some
time...):

I am currently doing some calculations with the larger sporadic groups (matrix
representations) and need to be able to compute centralizers. This proves
impossible in a variety of cases.

However, I am not utilising the fact that I know the centralizer sizes
from the ATLAS. I believe it may be advantageous for me to find an element
which commutes with my given one, find the order of the subgroups they
generate,and keep doing this ... until the subgroup reaches the desired
size.

Without knowing what your group (and class of elements) is, and whether you
have a few or frequent centralizer computations, it is hard to give a
general rule. However here are some hints that might help (I should add that
most of this is not my idea but uses methods I learned from other
people, mainly Klaus Lux, Steve Linton and Robert Wilson):

o I suppose you are aware of Robert Wilson's Birmingham electronic ATLAS
repository that holds a lot of representations and also in some cases words
for centralizer generators &c. Your problem might have been solved already
there. (If you want to centralize another element than the representative
given there, it might be worth trying to conjugate the element to the given
class representative).

o When you work in GAP with a matrix group, GAP actually computes a
permutation representation (action on vectors) and then calculates with
permutation group methods in this representation. This representation is not
necessarily the one of smallest degree. In most cases you will be better off
by working in the permutation representation of smallest degree and to use a
homomorphism (for example a `GroupHomomorphismByImages'; based on standard
generators to go from permutation to matrix. Note that a homomorphism from
a matrix group will implicitloy again go through the permutation action on
vectors, since there is no algorithm implemented to decompose a matrix
into generators directly) to translate between matrices and permutations.

o The centralizer algorithm for permutation groups uses a backtrack search,
I am not aware of a general method to find random centralizing elements,
that works faster. However there are two tricks, that might reduce the
problem to a size that makes it feasible on your machine:

- Generate (random) subgroups containing your element to be centralized,
and compute first the centralizer in the subgroup. Iterate this and
collect all the centralizer generators.
To get a subgroup, construct random elements,or conjugate by random
elements (using `PseudoRandom' -- `Random' guarantees equal distribution
and therefore has to go via a permutation representation) and check (using
the Meataxe) whether an irreducible representation becomes reducible for
the group generated by these elements. Repeat until it does, then you
have found a proper subgroup. (This method is rather crude, but the test
often works reasonably quickly and permits many checks).
- There is a method to find elements that centralize an involution (and
thus can be used for centralizers of elements of even order) which
usually goes under the name of `dihedral group trick': Let a and b be
two elements of order 2 (one of them (a power of) the element you want
to centralize), then a and b generate a dihedral group whose center
centralizes. See

@inproceedings{linton92a,
  author =	 "S.~A. Linton",
  title =	 "The Art and Science of Computing in Large Groups",
  pages =	 "91--109",
  title =	 "Proceedings of CANT '92",
  editor =	 "Wieb Bosma and Alf~J. van der Poorten",
  publisher =	 "Kluwer",
  year =	 1995
}

and

@phdthesis{brayphd,
  author =	 "John Bray",
  title =	 "Symmetric Presentations of Sporadic Groups and
                  Related Topics",
  school =	 "The University of Birmingham",
  year =	 1997
}

(The latter also is in a published paper in ArchMath I think, but I don't
have the reference at hand at the moment) for details.

o If you want to centralize an element of high order, it might be worth
trying to find first the centralizer of a power (which has lower order):
This centralizer is often larger, and thus you have a better chance to fidn
random elements therein.

o If you search for random elements it might be worth to look at the
centralizer structure: If you know that the centralizer must contain
elements from a given (smallish) class, get a representative from this class
first, and then conjugate it with random elements until you find something
centralizing.

I hope this is of help,

Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, Fort Collins, CO 80523, USA
email: hulpke@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke