> < ^ Date: Thu, 07 Jan 1993 16:17:06 +0100
> < ^ From: Thomas Breuer <Thomas.Breuer@Math.RWTH-Aachen.DE >
> < ^ Subject: Re: Character Tables

In his answer to a question of David Sibley concerning some messages
printed by 'TransformingPermutations' Alexander Hulpke did not tell
the whole truth.

Two rows are regarded to be equivalent if 'Sort' makes them equal.
The equivalence classes of rows of a matrix are called its row families.

Clearly if two matrices are permutation equivalent then every row
family of the first matrix must consist of rows that are equivalent to
the rows in a family of the other matrix, and the cardinalities of these
families must be equal. The same of course holds for the columns of
the matrices, but moreover it is also true for the restriction to every
row family of the first matrix and its corresponding family in the second
one; this might yield a finer distribution to column families, and the
program in fact computes this one.

These distributions of rows and columns are not just computed to test
some necessary conditions of permutation equivalence, in order to avoid
starting the algorithm whenever these tests fail. They are an essential
part of the algorithm, namely they provide the translation of the
problem to find transforming permutations into a problem completely
formulated in terms of permutations. This problem is then solved by one
of the backtrack search algorithms for permutation groups (very similar
to the algorithm for the computation of a centralizer in a given
permutation group).

Thomas Breuer

> < [top]