76 Elements in finite Coxeter groups

Let (W,S) be a finite Coxeter system as in the previous chapter. For a given element w in W, the length l(w) is defined to be the smallest integer k such that w can be written as a product of k fundamental reflections. Such an expression of shortest possible length will be called a reduced word for w. A user might be interested to think of the elements of W as such words in the generating fundamental reflections. For these programs, we represent a word simply as a list of integers corresponding to the fundamental roots, e.g., [] is the identity element, and [1], [2], etc. represent the reflection along the first, the second etc. fundamental root vector. For computational purposes, it might be better to use the permutation of an element w on the root vectors. The functions CoxeterWord and PermCoxeterWord will do the conversion of one form into the other.

    gap> W := CoxeterGroup( "D", 4 );;
    gap> p := PermCoxeterWord( W, [ 1, 3, 2, 1, 3 ] );
    ( 1,14,13, 2)( 3,17, 8,18)( 4,12)( 5,20, 6,15)( 7,10,11, 9)(16,24)
    (19,22,23,21)
    gap> CoxeterWord( W, p );
    [ 1, 3, 1, 2, 3 ] 

We notice that the word we started with and the one that we ended up with, are not the same. But of course, they represent the same element of W. The reason for this difference is that the function CoxeterWord always computes a reduced word which is the lexicographically smallest among all possible expressions of an element of W as a word in the fundamental reflections! The function ReducedCoxeterWord does the same but with an arbitrary word as input (and not with a permutation). In particular, the element used in the above example has length 5. Sometimes, it is not necessary to compute a reduced word for an element w and one is only interested in the length l(w); this can be computed very effectively from the permutation, since it is also given by the number of positive roots mapped to negative roots by w, i.e., by the number of i in {1,ldots,N} such that i^w > N. This is what does the function CoxeterLength in the following example where we also show how to compute the unique element of maximal length in W.

    gap> LongestCoxeterWord( W );  # the (unique) longest element in W
    [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ]
    gap> w0 := LongestCoxeterElement( W ); # = PermCoxeterWord( W, last )
    ( 1,13)( 2,14)( 3,15)( 4,16)( 5,17)( 6,18)( 7,19)( 8,20)( 9,21)(10,22)
    (11,23)(12,24)
    gap> CoxeterLength( W, w0 );
    12 

There is another way of computing a reduced word which is more canonical for some purposes. For any set I of generators, let w_I be the unique element of maximal length which can be made in the generators I. (Note that this element is an involution.) Now take any w in W and compute the set L(w) of all generators s such that l(sw). In GAP this is done by the function LeftDescentSet. Brieskorn Bri71 has noticed that w_{L(w)} divides w, in the sense that l(w_{L(w)})+l(w_{L(w)}w)=l(w). We can now divide w by w_{L(w)} and continue this process with the quotient. In this way, we obtain a reduced expression w=w_{L_1} cdots w_{L_r} where L_i=L(w_{L_i} cdots w_{L_r}) for all i, which we call the Brieskorn normal form of w (and where we use the lexicographically smallest expression for each w_{L_i}). The CHEVIE package will use this form if you set CHEVIE.BrieskornNormalForm:= true;. When you load CHEVIE this variable is initialized with false (see also CoxeterWord).

We give an example of some other commands:

    gap> List( Reflections( W ), i -> CoxeterWord( W, i ) );  
    [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 1, 3, 1 ], [ 2, 3, 2 ], [ 3, 4, 3 ],
      [ 1, 2, 3, 1, 2 ], [ 1, 3, 4, 3, 1 ], [ 2, 3, 4, 3, 2 ],
      [ 1, 2, 3, 4, 3, 1, 2 ], [ 3, 1, 2, 3, 4, 3, 1, 2, 3 ], [ 1 ],
      [ 2 ], [ 3 ], [ 4 ], [ 1, 3, 1 ], [ 2, 3, 2 ], [ 3, 4, 3 ], 
      [ 1, 2, 3, 1, 2 ], [ 1, 3, 4, 3, 1 ], [ 2, 3, 4, 3, 2 ], 
      [ 1, 2, 3, 4, 3, 1, 2 ], [ 3, 1, 2, 3, 4, 3, 1, 2, 3 ] ]
    gap> l := List( [1 .. W.N+1], x -> CoxeterElementsLength( W, x-1 ) );; 
    gap> List( l, Length );
    [ 1, 4, 9, 16, 23, 28, 30, 28, 23, 16, 9, 4, 1 ] 

The last line tells us that there is 1 element of length 0, there are 4 elements of length 4, etc.

For many basic functions (like CoxeterElementsLength, Reflections, Bruhat, etc.) we have chosen the convention that if the input is an element of a Coxeter group, then this element should by given as a permutation (and similarly for the output). As a rule of thumb one should keep in mind that, if in some application one has to do a lot of computations with Coxeter group elements then using the low level GAP functions for permutations is usually much faster than manipulating lists of reduced expressions. For example, suppose we are given an element w in W and a generator s_i and we want to check if l(s_iw). Then it is more efficient to represent w by a permutation and to check the condition i^wW.N than to work with a reduced expression and check the condition

Length( ReducedCoxeterWord( W, Concatenation( [i], w ) ) )

Subsections

  1. PermCoxeterWord
  2. CoxeterWord
  3. CoxeterLength
  4. ReducedCoxeterWord
  5. LeftDescentSet
  6. RightDescentSet
  7. Reflections
  8. LongestCoxeterElement
  9. LongestCoxeterWord
  10. HighestShortRoot
  11. CoxeterElementsLength
  12. CoxeterWords
  13. CoxeterConjugacyClasses
  14. ChevieClassInfo
  15. Bruhat
  16. MatXPerm
  17. MatYPerm
  18. PermMatX
  19. PermMatY

76.1 PermCoxeterWord

PermCoxeterWord( W , w )

returns the permutation on the root vectors determined by an element which is given as a list w of integers representing the standard generators of the Coxeter group W.

    gap> W := CoxeterGroup( "G", 2 );;
    gap> PermCoxeterWord( W, [1,2,1] );
    ( 1,12)( 2, 4)( 3, 9)( 6, 7)( 8,10) 

See also CoxeterWord.

This function requires the package "chevie" (see RequirePackage).

76.2 CoxeterWord

CoxeterWord( W , w )

returns a reduced word in the standard generators of the Coxeter group W determined by the permutation w on the root vectors.

    gap> W := CoxeterGroup( "A", 3 );;
    gap> w := ( 1,11)( 3,10)( 4, 9)( 5, 7)( 6,12);; 
    gap> w in W;
    true;
    gap> CHEVIE.BrieskornNormalForm := true;;
    gap> CoxeterWord( W, w );
    [ 1, 3, 2, 1, 3 ] 
    gap> CHEVIE.BrieskornNormalForm := false;;
    gap> CoxeterWord( W, w );
    [ 1, 2, 3, 2, 1 ] 

For the definition of the Brieskorn normal form, see the introduction to this chapter. If the global variable CHEVIE.BrieskornNormalForm is set to false (which is automatically the case when you load CHEVIE), the result of CoxeterWord is the lexicographically smallest reduced word for~w.

See also PermCoxeterWord and ReducedCoxeterWord.

This function requires the package "chevie" (see RequirePackage).

76.3 CoxeterLength

CoxeterLength( W , w )

returns the length of the permutation w, which corresponds to an element in the Coxeter group W, as a reduced expression in the standard generators.

    gap> W := CoxeterGroup( "F", 4 );;
    gap> p := PermCoxeterWord( W, [ 1, 2, 3, 4, 2 ] );
    ( 1,44,38,25,20,14)( 2, 5,40,47,48,35)( 3, 7,13,21,19,15)
    ( 4, 6,12,28,30,36)( 8,34,41,32,10,17)( 9,18)(11,26,29,16,23,24)
    (27,31,37,45,43,39)(33,42)
    gap> CoxeterLength( W, p );
    5
    gap> CoxeterWord( W, p );
    [ 1, 2, 3, 2, 4 ] 
This function requires the package "chevie" (see RequirePackage).

76.4 ReducedCoxeterWord

ReducedCoxeterWord( W , w )

returns a reduced expression for an element of the Coxeter group W, which is given as a list w of integers where each entry i in this list represents the i-th standard generator of W.

    gap> W := CoxeterGroup( "E", 6 );;
    gap> ReducedCoxeterWord( W, [ 1, 1, 1, 1, 1, 2, 2, 2, 3 ] );
    [ 1, 2, 3 ] 

This function requires the package "chevie" (see RequirePackage).

76.5 LeftDescentSet

LeftDescentSet( W, w )

The set of generators s such that l(sw), given as a list of integers.

    gap> W := CoxeterGroup( "A", 2 );;
    gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
    gap> LeftDescentSet( W, w );
    [ 1 ] 

See also RightDescentSet.

This function requires the package "chevie" (see RequirePackage).

76.6 RightDescentSet

RightDescentSet( W, w )

The set of generators s such that l(ws)< l(w), given as a list of integers.

    gap> W := CoxeterGroup( "A", 2 );;
    gap> w := PermCoxeterWord( W, [ 1, 2 ] );;
    gap> RightDescentSet( W, w );
    [ 2 ] 

See also LeftDescentSet.

This function requires the package "chevie" (see RequirePackage).

76.7 Reflections

Reflections( W )

returns the set of reflections in the Coxeter group W (as permutations). The i-th entry in this list is the reflection along the i-th root in W.roots.

    gap> W := CoxeterGroup( "B", 2 );; W.roots;
    [ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 2, 1 ], [ -1, 0 ], [ 0, -1 ],
      [ -1, -1 ], [ -2, -1 ] ]
    gap> Reflections( W );
    [ (1,5)(2,4)(6,8), (1,3)(2,6)(5,7), (2,8)(3,7)(4,6), (1,7)(3,5)(4,8), 
      (1,5)(2,4)(6,8), (1,3)(2,6)(5,7), (2,8)(3,7)(4,6), (1,7)(3,5)(4,8) ]

This function requires the package "chevie" (see RequirePackage).

76.8 LongestCoxeterElement

LongestCoxeterElement( W )

returns the unique element of maximal length of the Coxeter group W as a permutation.

    gap> LongestCoxeterElement( CoxeterGroup( "A", 4 ) );
    ( 1,14)( 2,13)( 3,12)( 4,11)( 5,17)( 6,16)( 7,15)( 8,19)( 9,18)(10,20) 

This function requires the package "chevie" (see RequirePackage).

76.9 LongestCoxeterWord

LongestCoxeterWord( W )

returns a reduced expression in the standard generators for the unique element of maximal length of the Coxeter group W.

    gap> LongestCoxeterWord( CoxeterGroup( "A", 4 ) );
    [ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ] 

This function requires the package "chevie" (see RequirePackage).

76.10 HighestShortRoot

HighestShortRoot( W )

Let W be an irreducible Coxeter group. HighestShortRoot computes the unique short root of maximal height of W. Note that if all roots have the same length then this is the unique root of maximal height, which can also be obtained by W.roots[W.N]. An error message is returned for W not irreducible.

    gap> W := CoxeterGroup( "G", 2 );;  W.roots;
    [ [ 1, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 3 ], 
      [ -1, 0 ], [ 0, -1 ], [ -1, -1 ], [ -1, -2 ], [ -1, -3 ], 
      [ -2, -3 ] ]
    gap> HighestShortRoot( W );
    4
    gap> W1 := CoxeterGroup( "A", 1, "B", 3 );;
    gap> HighestShortRoot( W1 );
    Error,  group is not irreducible
     in
    HighestShortRoot( W1 ) called from
    main loop
    brk> 

This function requires the package "chevie" (see RequirePackage).

76.11 CoxeterElementsLength

CoxeterElementsLength( W, l )

returns as a list of permutations the list of all elements of W of length l.

    gap> W := CoxeterGroup( "G", 2 );;
    gap> e := CoxeterElementsLength( W, 6 );
    [ ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12) ]
    gap> e[1] = LongestCoxeterElement( W );
    true 

The result of the computation of elements of a given length is stored in the component elts of the record of W. Thus W.elts[lw+1] contains the list of all elements of length lw in W. There are a number of Kazhdan-Lusztig polynomials and bases) which refer to the ordering of the elements in these lists in W.elts.

This function requires the package "chevie" (see RequirePackage).

76.12 CoxeterWords

CoxeterWords( W )

returns the list of all elements in the Coxeter group W. The ordering is the same as that given by concatenating the lists of elements of length 0,1,ldots obtained by the function CoxeterElementsLength.

    gap> CoxeterWords( CoxeterGroup( "G", 2 ) );
    [ [  ], [ 2 ], [ 1 ], [ 2, 1 ], [ 1, 2 ], [ 2, 1, 2 ], [ 1, 2, 1 ], 
      [ 2, 1, 2, 1 ], [ 1, 2, 1, 2 ], [ 2, 1, 2, 1, 2 ], 
      [ 1, 2, 1, 2, 1 ], [ 1, 2, 1, 2, 1, 2 ] ] 

This function requires the package "chevie" (see RequirePackage).

76.13 CoxeterConjugacyClasses

CoxeterConjugacyClasses( W )

returns a list of representatives of the conjugacy classes of the Coxeter group W. Each element in this list is given as a word in the standard generators, where the generator s_i is represented by the number i in a list. Each representative has the property that it is of minimal length in its conjugacy class.

    gap> CoxeterConjugacyClasses( CoxeterGroup( "F", 4 ) );
    [ [  ], 
      [ 1, 2, 1, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2, 
          3, 4 ], [ 2, 3, 2, 3 ], [ 2, 1 ], 
      [ 2, 3, 2, 3, 4, 3, 2, 1, 3, 4 ], 
      [ 3, 2, 4, 3, 2, 1, 3, 2, 4, 3, 2, 1 ], [ 4, 3 ], 
      [ 1, 2, 1, 4, 3, 2, 1, 3, 2, 3 ], 
      [ 3, 2, 1, 4, 3, 2, 1, 3, 2, 3, 4, 3, 2, 1, 3, 2 ], 
      [ 3, 2, 4, 3, 2, 1, 3, 2 ], [ 4, 3, 2, 1 ], [ 1 ], 
      [ 2, 3, 2, 3, 4, 3, 2, 3, 4 ], [ 1, 4, 3 ], [ 4, 3, 2 ], 
      [ 2, 3, 2, 1, 3 ], [ 3 ], [ 1, 2, 1, 3, 2, 1, 3, 2, 3 ], 
      [ 2, 1, 4 ], [ 3, 2, 1 ], [ 2, 4, 3, 2, 3 ], [ 1, 3 ], [ 3, 2 ], 
      [ 2, 3, 2, 3, 4, 3, 2, 1, 3, 2, 4, 3, 2, 1 ], [ 2, 4, 3, 2, 1, 3 ] ] 
See also ChevieClassInfo.

This function requires the package "chevie" (see RequirePackage).

76.14 ChevieClassInfo

ChevieClassInfo( W )

returns information about the conjugacy classes of the finite Coxeter group W. The result is a record with three components: classtext contains CoxeterConjugacyClass(W), classnames contains corresponding names for the classes, and classparams gives Character tables for Coxeter groups).

    gap> W := CoxeterGroup( "D", 4 );;
    gap> ChevieClassInfo( W );
    rec(
      classtext := 
       [ [  ], [ 1, 2 ], [ 1, 2, 3, 1, 2, 3, 4, 3, 1, 2, 3, 4 ], [ 1 ], 
          [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 4 ], [ 2, 4 ], 
          [ 1, 3, 1, 2, 3, 4 ], [ 1, 3 ], [ 1, 2, 3, 4 ], [ 1, 3, 4 ], 
          [ 2, 3, 4 ] ],
      classparams := 
       [ [ [ [ 1, 1, 1, 1 ], [  ] ] ], [ [ [ 1, 1 ], [ 1, 1 ] ] ], 
          [ [ [  ], [ 1, 1, 1, 1 ] ] ], [ [ [ 2, 1, 1 ], [  ] ] ], 
          [ [ [ 1 ], [ 2, 1 ] ] ], [ [ [ 2 ], [ 1, 1 ] ] ], 
          [ [ [ 2, 2 ], '+' ] ], [ [ [ 2, 2 ], '-' ] ], 
          [ [ [  ], [ 2, 2 ] ] ], [ [ [ 3, 1 ], [  ] ] ], 
          [ [ [  ], [ 3, 1 ] ] ], [ [ [ 4 ], '+' ] ], [ [ [ 4 ], '-' ] ] ]
       ,
      classnames := [ "1111.", "11.11", ".1111", "211.", "1.21", "2.11", 
          "22.+", "22.-", ".22", "31.", ".31", "4.+", "4.-" ] ) 

For a general description of the conjugacy classes in the Weyl groups, see Car72. The relevance of taking representatives of minimal length is explained in GP93.

See also ChevieCharInfo.

This function requires the package "chevie" (see RequirePackage).

76.15 Bruhat

Bruhat( W, y, w[, ly, lw] )

returns true, if the element y is less than or equal to the element w of the Coxeter group W for the Bruhat order, and false otherwise (y is less than w if a reduced expression for y can be extracted from one for w). Both y and w must be given as permutations on the root vectors of W. The optional arguments ly, lw can contain the length of the elements y and w. (In a computation with many calls to Bruhat this may speed up the computation considerably.) See cite[(5.9) and (5.10)]Hum90 for further properties of the Bruhat order.

    gap> W := CoxeterGroup( "H", 3 );;
    gap> w := PermCoxeterWord( W, [ 1, 2, 1, 3 ] );;
    gap> b := Filtered( Elements( W ), i -> Bruhat( W, i, w, 
    >                                 CoxeterLength( W, i ), 4 ) );;
    gap> List( b, x -> CoxeterWord( W, x ) );
    [ [  ], [ 3 ], [ 2 ], [ 2, 1 ], [ 2, 3 ], [ 2, 1, 3 ], [ 1 ], 
      [ 1, 3 ], [ 1, 2 ], [ 1, 2, 1 ], [ 1, 2, 3 ], [ 1, 2, 1, 3 ] ] 

This function requires the package "chevie" (see RequirePackage).

76.16 MatXPerm

MatXPerm( W, w )

Let w be a permutation of the roots of the Coxeter datum W acting on the vector space V. MatXPerm returns the matrix of a linear transformation of V which acts trivially on the orthogonal of the coroots and has same effect as w on the simple roots. Only the image of the simple roots by w is used.

    gap> W := CoxeterGroup( 
    > [ [ 2, 0,-1, 0, 0, 0, 1 ], [ 0, 2, 0,-1, 0, 0, 0 ],
    >   [-1, 0, 2,-1, 0, 0,-1 ], [ 0,-1,-1, 2,-1, 0, 0 ],
    >   [ 0, 0, 0,-1, 2,-1, 0 ], [ 0, 0, 0, 0,-1, 2, 0 ] ],
    > [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ],
    >   [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ],
    >   [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ] ] );;
    gap> w0 := LongestCoxeterElement( W );;
    gap> mx := MatXPerm( W, w0 );
    [ [ 0, 0, 0, 0, 0, -1, 1 ], [ 0, -1, 0, 0, 0, 0, 2 ], 
      [ 0, 0, 0, 0, -1, 0, 3 ], [ 0, 0, 0, -1, 0, 0, 4 ], 
      [ 0, 0, -1, 0, 0, 0, 3 ], [ -1, 0, 0, 0, 0, 0, 1 ], 
      [ 0, 0, 0, 0, 0, 0, 1 ] ] 

This function requires the package "chevie" (see RequirePackage).

76.17 MatYPerm

MatYPerm( W, w )

Let w be a permutation of the roots of the Coxeter datum W acting on the vector space Vdual. MatYPerm returns the matrix of a linear transformation of Vdual which acts trivially on the orthogonal of the roots and has same effect as w on the simple coroots. Only the image of the simple coroots by w is used.

We continue the example from MatXPerm and obtain:

    gap> my := MatYPerm( W, w0 );
    [ [ 0, 0, 0, 0, 0, -1, 0 ], [ 0, -1, 0, 0, 0, 0, 0 ],
      [ 0, 0, 0, 0, -1, 0, 0 ], [ 0, 0, 0, -1, 0, 0, 0 ],
      [ 0, 0, -1, 0, 0, 0, 0 ], [ -1, 0, 0, 0, 0, 0, 0 ],
      [ 1, 2, 3, 4, 3, 1, 1 ] ] 

This function requires the package "chevie" (see RequirePackage).

76.18 PermMatX

PermMatX( W, M )

Let M be a linear transformation of the vector space V on which the Coxeter datum W acts which preserves the set of roots. PermMatX returns the corresponding permutation of the roots; it signals an error if M does not normalize the set of roots.

We continue the example from MatXPerm and obtain:

    gap> PermMatX( W, mx ) = w0;
    true 

This function requires the package "chevie" (see RequirePackage).

76.19 PermMatY

PermMatX( W, M )

Let M be a linear transformation of the vector space Vdual on which the Coxeter datum W acts which preserves the set of coroots. PermMatY returns the corresponding permutation of the coroots; it signals an error if M does not normalize the set of coroots.

We continue the example from MatYPerm and obtain:

    gap> PermMatY( W, my ) = w0;
    true 

This function requires the package "chevie" (see RequirePackage).

Previous Up Next
Index

GAP 3.4.4
April 1997