> < ^ From:

> < ^ Subject:

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]