> < ^ Date: Mon, 05 Aug 1996 14:19:10 +0200
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
< ^ Subject: Re: About Class Multiplication Coefficients

Dear GAP-Forum,

Anatolii^ Rukolaine asked about computing class multiplication coefficients.

As Thomas Breuer already pointed out, ususally the easiest and by far
fastest way to get those coefficients is via the character table (even
though the character table for a group in general is computed by the
Dixon-Schneider Algorithm, using class multiplication coefficients).
The reason for this is that the algorithm for 'CharTable' tries to
compute as few coefficients as possible, picking classes for which
the coefficients are computed cheaply.
However the situation might occur that one wants to compute only very few
coefficients of a group for which the computation of the complete
character table is not possible (take for example a group of size a few
100000 with 2000 conjugacy classes or a group too big to compute the full
character table in reasonable time). For this situation I want to describe
shortly how to access functions, 'CharTable' uses. These functions are
somehow internal, therefore one should not use them in any other way than
described here. The function 'ClassMatrixColumn' uses not just a simple
evaluation of all class products, but also orbits of the centralizer of one
element (if c\in C_G(y) then xy and x^c*y are in the same class) and orbits
of the Galois group. (For groups like M12 this usually reduces the number
of tests neccessary by a factor of 10 or more.) They also try to identify
classes quickly. If you are interested in the details: they are described
in my diploma thesis which can be found on my WWW homepage:
http://www.math.rwth-aachen.de/~ahulpke

As an example, lets compute part of the coefficients corresponding to class
6B and 5A in M12. 

# get M12
gap> g:=OnePrimitiveGroup(DegreeOperation,12,i->Size(i)>95000,true);
M(12)
# prepare for usage of the Dixon functions:
# note: This function enforces computation of the conjugacy classes.
gap> d:=DixonInit(g);
DixonRecord(M(12))
# we have to use the classes in the ordering used by the dixon functions.
# * this ordering might be different than the one stored in group or
# character table ! *
gap> d.conjugacyClasses;
[ ConjugacyClass( M(12), () ), ConjugacyClass( M(12), ( 1,10)( 2, 7)( 3,12)
    ( 4, 5)( 6, 9)( 8,11) ), ConjugacyClass( M(12), ( 1,10)( 2,11)( 3,12)
    ( 5, 6) ), ConjugacyClass( M(12), ( 2, 6, 3)( 4, 7, 8)( 5,12,11) ),
  ConjugacyClass( M(12), ( 1, 8, 2)( 3,11,12)( 4, 6, 7)( 5, 9,10) ),
  ConjugacyClass( M(12), ( 2, 4, 5,12)( 3, 7,10, 6) ),
  ConjugacyClass( M(12), ( 1,11, 3, 8)( 2, 6)( 4, 5, 7,12)( 9,10) ),
  ConjugacyClass( M(12), ( 1, 8, 4, 2, 5,11)( 3,12, 9, 6,10, 7) ),
  ConjugacyClass( M(12), ( 1, 4, 9,12,10, 6, 3, 8,11, 2, 5) ),
  ConjugacyClass( M(12), ( 1, 3, 4, 8, 9,11,12, 2,10, 5, 6) ),
  ConjugacyClass( M(12), ( 1, 8, 6, 7,12)( 2, 3,10,11, 9) ),
  ConjugacyClass( M(12), ( 1, 2, 8, 3, 6,10, 7,11,12, 9)( 4, 5) ),
  ConjugacyClass( M(12), ( 1, 5, 7, 6, 4, 8, 2,11)( 3,12,10, 9) ),
  ConjugacyClass( M(12), ( 1,11)( 2, 7, 4,10, 5, 6,12, 3) ),
  ConjugacyClass( M(12), ( 1,10)( 2,12, 6,11, 3, 5)( 4, 8, 7) ) ]
# class 6B is at position 15 (use permutation character), 5A at position 11.

# get an empty matrix
gap> m:=0*IdentityMat(15,1);;
# compute the 11-th column of matrix 15
gap> d.ClassMatrixColumn(d,m,15,11); 

# look at it
gap> m;
[ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 60, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 80, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 280, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 440, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 510, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 510, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1320, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1440, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1440, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1560, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1560, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1980, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1980, 0, 0, 0, 0 ],
  [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2680, 0, 0, 0, 0 ] ]

# just to check, compare with the value from the character table. Here 6B is
# class number 10 and 5A class number 8
gap> c:=CharTable("m12");
CharTable( "M12" ) 

# as we see, the values agree
gap> MatClassMultCoeffsCharTable(c,10);
[ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ],
  [ 0, 0, 0, 54, 72, 96, 96, 60, 72, 54, 72, 72, 60, 66, 66 ],
  [ 0, 0, 192, 72, 96, 80, 80, 80, 96, 87, 72, 72, 80, 88, 88 ],
  [ 0, 240, 256, 270, 288, 304, 304, 280, 288, 330, 288, 288, 280, 286, 286
],
  [ 0, 480, 512, 432, 432, 416, 416, 440, 432, 464, 432, 432, 440, 440, 440
],
  [ 0, 720, 480, 513, 468, 384, 528, 510, 468, 489, 540, 468, 510, 495, 495
],
  [ 0, 720, 480, 513, 468, 528, 384, 510, 468, 489, 468, 540, 510, 495, 495
],
  [ 0, 1440, 1536, 1512, 1584, 1632, 1632, 1560, 1584, 1608, 1584, 1584,
      1560, 1584, 1584 ],
  [ 0, 1440, 1536, 1296, 1296, 1248, 1248, 1320, 1296, 1392, 1296, 1296,
      1320, 1320, 1320 ],
  [ 15840, 2160, 2784, 2970, 2784, 2608, 2608, 2680, 2784, 2574, 2592, 2592,
      2680, 2618, 2618 ],
  [ 0, 2160, 1728, 1944, 1944, 2160, 1872, 1980, 1944, 1944, 1944, 2088,
      1980, 1980, 1980 ],
  [ 0, 2160, 1728, 1944, 1944, 1872, 2160, 1980, 1944, 1944, 2088, 1944,
      1980, 1980, 1980 ],
  [ 0, 1440, 1536, 1512, 1584, 1632, 1632, 1560, 1584, 1608, 1584, 1584,
      1560, 1584, 1584 ],
  [ 0, 1440, 1536, 1404, 1440, 1440, 1440, 1440, 1440, 1428, 1440, 1440,
      1440, 1452, 1452 ],
  [ 0, 1440, 1536, 1404, 1440, 1440, 1440, 1440, 1440, 1428, 1440, 1440,
      1440, 1452, 1452 ] ]
gap> List(MatClassMultCoeffsCharTable(c,10),i->i[8]);
[ 0, 60, 80, 280, 440, 510, 510, 1560, 1320, 2680, 1980, 1980, 1560, 1440,
  1440 ]

Hope this helps,

Alexander Hulpke

> < [top]