[GAP Forum] length
Frank Luebeck
frank.luebeck at math.rwth-aachen.de
Mon Mar 29 09:05:40 BST 2004
Dear Marcus,
> How can I compute the
> length of an element
> of a group, where by
> "length" I mean the minimum
> number of generators
> needed to write the element,
> assuming that I've fixed
> a generating set for the group.
This is in general very difficult. There is essentially no better method
but a brute force search.
> In particular, I need to do
> this for the symmetric group
> using generating set
> (1,2), (2,3), (3,4), ... (n-1,n)
In this particular case there is an efficient algorithm, based on the
following easy to prove
Lemma: For pi in the symmetric group on {1,2,...,n} let
L(pi) = {(i,j)| 1 <= i < j <= n, pi(i) > pi(j)}.
Let 1 <= k <= n-1. Then |L( (k,k+1) pi )| = |L(pi)| + 1 if pi(k) < pi(k+1)
and |L( (k,k+1) pi )| = |L(pi)| - 1 otherwise.
This shows that the length of pi with respect to your generators is |L(pi)|,
and also that the following function returns a word of minimal length
in your set of generators (there can be many of such words, this gives the
lexicographically smallest):
SnWord := function(pi)
local word, k;
word := [];
while pi <> () do
k := 1;
while k^pi < (k+1)^pi do
k := k + 1;
od;
Add(word, k);
pi := (k,k+1) * pi;
od;
return word;
end;
(This can be generalized to arbitrary Coxeter groups with a given set
of Coxeter generators.)
With best regards,
Frank Luebeck
/// Dr. Frank Lübeck, Lehrstuhl D für Mathematik, Templergraben 64, ///
\\\ 52062 Aachen, Germany \\\
/// E-mail: Frank.Luebeck at Math.RWTH-Aachen.De ///
\\\ WWW: http://www.math.rwth-aachen.de/~Frank.Luebeck/ \\\
More information about the Forum
mailing list