1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630

COMMENT:
The HICCUP.C module deals with the generation of explicit irreducible
matrix representations of the Hecke algebra H_n of type A.
In addition, routines are provided which enable calculations in
H_n to be carried out.
This file gives a very brief introduction to the irreducible
representations of H_n, describes aspects of their implementation in
Symmetrica, describes the pertinent library functions, and finally
describes the example programs.
In the case when q is not a root of unity, the irreducible representations
of H_n are labelled by the partitions of n, and are provided here by
the generalisation of the Specht modules of the symmetric group
described in:
R.C. King & B.G. Wybourne, "Representations and Traces of the Hecke
Algebras H_n(q) of type A_{n1}", J. Math. Phys. 33(1), pp414 (1992).
Although the Specht modules remain valid representations of H_n when
q is a root of unity, they may be reducible. In fact, if q is a
primitive pth root of unity, a full set of irreducibles are labelled
by the pregular partitions of n. They may be obtained by factoring
the corresponding Specht module by its maximal submodule.
For those representations labelled by partitions with two parts, this
was first described in the conference paper:
T.A. Welsh, "Tworowed Hecke algebra representations at roots of
unity", Czech J. Phys. 45, pp283291 (1996).
A more extensive version which details the algorithms required to
produce the representation matrices is available from the proceedings
of the 35th Seminaire Lotharingien de Combinatoire at the
WorldWideWeb site http://cartan.ustrasbg.fr:80/~slc/
(a more comprehensive paper is on the cards  maybe 1996). The
algorithms in this work are implemented here. They are very much
based on the Specht modules.
The Hecke algebra H_n is the unital associative algebra over the
complex numbers, generated by h_1,h_2,...,h_{n1} and subject to:
1. (h_i+1)(h_iq)=0 (1 <= i <= n1);
2. h_i h_{i+1} h_i = h_{i+1} h_i h_{i+1} (1 <= i <= n2);
3. h_i h_j = h_j h_i (1 <= i < j1 <= n2).
Here q is a fixed complex number.
These relations enable a map h:S_n > H_n to be unambiguously defined
as follows. Let s_i be the simple transposition (i,i+1) of S_n, and
for w in S_m let
w = s_{i_1} s_{i_2} s_{i_3} ... s_{i_l}
be a reduced expression for w in that l is the length of w. Then define
h(w) = h_{i_1} h_{i_2} h_{i_3} ... h_{i_l}.
In fact, the images of all w in S_n provide a basis for H_n
(moreover, if q is not a root of unity, then H_n and the group algebra
of S_n over the complex numbers are isomorphic). This is made use of
in the routines, where elements of H_n are stored as qlinear
combinations of permutations: a permutation corresponds to the
element of H_n obtained from the map h.
In terms of the objects of Symmetrica, an element of H_n is a linked
LIST of MONOM objects. The "self" part of each MONOM is the
PERMUTATION, and the "koeff" part is its coefficient  a MONOPOLY
object representing a polynomial in the single variable q.
The MONOPOLY object is itself a linked list of MONOMs representing
the individual terms in the polynomial. Here both the "self" and
"koeff" parts of the MONOM are INTEGER objects; the former giving
the power of the term, and the latter its coefficient.
Schematically, this data structure is as follows:
LIST > LIST (next)
> MONOM > PERMUTATION
> MONOPOLY (LIST) > MONOPOLY (next)
> MONOM > INTEGER (power)
> INTEGER (coefficient).
In the constructions introduced above, the module corresponding to a
particular partition is spanned by tableaux of the shape of that
partition. Thus a data structure similar to the above is used to
store elements of the module:
LIST > LIST (next)
> MONOM > TABLEAUX
> MONOPOLY (LIST) > MONOPOLY (next)
> MONOM > INTEGER (power)
> INTEGER (coefficient).
Each module has a basis which is a subset of the full set of tableaux.
For the Specht module, the basis elements are known as standard tableaux
(or S_n  standard tableaux). For the root of unity cases a subset
of the standard tableaux, known as proot standard tableaux, provide
a basis. At the heart of the module constructions are algorithms that
enable a tableau which is not in the basis to be rewritten in terms of
those tableaux that are. The action of an arbitrary element of H_n on a
tableau (see eq. (3) of [Welsh] which supercedes eqs. (3.8), (3.9) &
(3.10) of [Ki & Wy]) then completes the description of the module.
/********************************************************************
Here follow routines dealing with the generic irreducible modules.
********************************************************************/
NAME:
generate_standard_tableaux
SYNOPSIS:
INT generate_standard_tableaux (OP partition, OP std)
DESCRIPTION:
Generates the full set of standard tableaux for the
given partition. The tableaux are returned as a
lexicographically ordered list. If no error occurs,
their number is returned.
(The number of standard tableaux may also be obtained
from the Symmetrica function
dimension_partition (OP pt, OP dim),
which is described in the section of user manual
concerning PARTITION objects.)
RETURN:
ERROR or count of standard tableaux.
NAME:
hecke_generator_reps
SYNOPSIS:
INT hecke_generator_reps (OP partition, OP vector)
DESCRIPTION:
For the given partition of n, calculates representation
matrices for each of the generators h_1,h_2,...,h_{n1}.
The matrices are stored as MATRIX object elements of
a VECTOR of length n1.
RETURN:
OK or ERROR.
NAME:
represent_hecke_element
SYNOPSIS:
INT represent_hecke_element (OP partition, OP hecke, OP mat)
DESCRIPTION:
For the given partition of n, calculates the matrix
representing the element of H_n given by hecke which
is a qlinear combination of PERMUTATIONS as described
in the preamble above.
RETURN:
OK or ERROR.
NAME:
hecke_dg
SYNOPSIS:
INT hecke_dg(OP part, OP perm, OP mat)
DESCRIPTION:
uses the routine represent_hecke_element to compute the matrix
representing the permutation perm.
NAME:
build_lc
SYNOPSIS:
INT build_lc (OP schizo, OP list)
DESCRIPTION:
This routine converts schizo, which is either a PERMUTATION
object or a TABLEAUX object into a linear combination LIST,
of the type described in the preamble above. The LIST has
one term (schizo) whose coefficient is a MONOPOLY
representing 1. schizo is incorporated into the list and
should not be subsequently freed.
This routine is sometimes useful before calling
hecke_action_lc_on_lc() or standardise_cold_tableaux_list().
RETURN:
OK or ERROR.
NAME:
hecke_action_lc_on_lc
SYNOPSIS:
INT hecke_action_lc_on_lc (OP tableaux, OP hecke, OP result)
DESCRIPTION:
The linear combination of Hecke algebra permutations given
in hecke, acts on the linear combination of tableaux. The
resultant linear combination of (in general, nonstandard)
tableaux is in result. This result is not ordered and has
not had terms collected.
RETURN:
OK or ERROR.
NAME:
standardise_cold_tableaux_list
SYNOPSIS:
INT standardise_cold_tableaux_list (OP tableaux, OP result)
DESCRIPTION:
The linear combination of tableaux is reexpressed in terms
of standard tableaux. The result is an ordered list in which
terms have been collected.
(This routine makes use of only Garnir & column relations).
RETURN:
OK or ERROR.
NAME:
input_tableau
SYNOPSIS:
INT input_tableau (OP partit, OP tab)
DESCRIPTION:
Asks the user to input a tableau of the shape specified
by the PARTITION object partit. An ERROR is returned if
the entries are not distinct elements of {1,2,...,n},
where n is the weight of partit.
RETURN:
OK or ERROR.
NAME:
input_lc_permutations
SYNOPSIS:
INT input_lc_permutations (OP save)
DESCRIPTION:
Asks the user to input a linear combination of permutations.
RETURN:
OK.
NAME:
substitute_one_matrix
SYNOPSIS:
INT substitute_one_matrix (OP matrix)
DESCRIPTION:
Every entry of the matrix that is a MONOPOLY polynomial has
q=1 substituted. Using this function, the Specht module
representations of the Hecke algebra are converted into
those of the symmetric group.
RETURN:
OK or ERROR.
NAME:
substitute_one_monopoly
SYNOPSIS:
INT substitute_one_monopoly (OP monopoly)
DESCRIPTION:
The MONOPOLY polynomial has q=1 substituted (it is
converted into an INTEGER object).
RETURN:
OK or ERROR.
COMMENT:
/********************************************************************
Here follow routines dealing with the 2rowed nongeneric modules.
********************************************************************/
NAME:
root_dimension
SYNOPSIS:
INT root_dimension (OP partition, OP p_root, OP dim)
DESCRIPTION:
Calculates the dimension of irreducible representation
labelled by partition at primitive p_root of unity.
The result is in the INTEGER object dim.
(Calculated using eq. (22) of [Welsh].)
RETURN:
OK or ERROR.
NAME:
generate_root_tableaux
SYNOPSIS:
INT generate_root_tableaux (OP partition, OP p_root, OP std)
DESCRIPTION:
Generates the full set of proot standard tableaux for
the given partition. The tableaux are returned as a
lexicographically ordered list. If no error occurs,
their number is returned. This number should be equal
to that obtained from root_dimension().
(This routine simply generates all standard tableaux and
discards those that are not proot standard.)
RETURN:
ERROR or the number of proot standard tableaux.
NAME:
hecke_root_generator_reps
SYNOPSIS:
INT hecke_root_generator_reps (OP partition, OP p_root, OP vector)
DESCRIPTION:
For the given partition of n, and primitive p_root of
unity, calculates representation matrices for each of
the generators h_1,h_2,...,h_{n1}.
The matrices are stored as MATRIX object elements of
a VECTOR of length n1.
RETURN:
OK or ERROR
NAME:
root_represent_hecke_element
SYNOPSIS:
INT root_represent_hecke_element (OP partition, OP p_root, OP hecke, OP mat)
DESCRIPTION:
For the given partition of n, and primitive p_root of
unity, calculates the matrix representing the element
of H_n given by hecke which is a qlinear combination
of PERMUTATIONS as described in the preamble above.
RETURN:
OK or ERROR
NAME:
root_standardise_cold_tableaux_list
SYNOPSIS:
INT root_standardise_cold_tableaux_list (OP tableaux, OP p_root, OP result)
DESCRIPTION:
The linear combination of tableaux is reexpressed in
terms of the p_root standard tableaux. The result is
an ordered list in which terms have been collected.
(This routine makes use of Garnir & column relations
and some new relations known as strip relations  yet
to be documented).
RETURN:
OK or ERROR.
COMMENT:
/********************************************************************
The following routines check the representation matrices
********************************************************************/
NAME:
check_hecke_generators
SYNOPSIS:
INT check_hecke_generators (OP vector, OP p_root, INT flag)
DESCRIPTION:
This routine checks that the MATRIX object elements of
the VECTOR object vector, satisfy the defining
relations 1, 2, 3, of the Hecke algebra given in
the preamble above. n is deduced from the length
of the vector. If p_root=0, then the relations
are checked for general q. Otherwise they are
checked for q a primitive p_root of unity.
For each identity checked, a message is printed
indicating whether the identity is OK for general q,
whether is it OK provided q is a root of unity with
the given primitive index, or whether it is not OK.
If flag is nonzero and the relation is not OK then the
difference between the two sides is output (untidily!).
RETURN:
OK or ERROR
NAME:
check_hecke_quadratic
SYNOPSIS:
INT check_hecke_quadratic (OP mat, OP p_root, INT flag)
DESCRIPTION:
Checks that the matrix satisfies the first Hecke algebra
relation. ( (m+1)(mq) == 0 )
If p_root=0, then the relations are checked for general q.
Otherwise they are checked for q a primitive p_root of unity.
If there is no ERROR, returns 0 if true for all q,
1 if true at primitive p_root of unity, 2 otherwise.
If flag is nonzero and the relation is not OK then the
left side is output.
RETURN:
ERROR, 0, 1, or 2 as described above.
NAME:
check_braid
SYNOPSIS:
INT check_braid (OP mat1, OP mat2, OP p_root, INT flag)
DESCRIPTION:
Checks that the matrices satisfy the second Hecke algebra
relation. ( m1*m2*m1 == m2*m1*m2 )
If p_root=0, then the relations are checked for general q.
Otherwise they are checked for q a primitive p_root of unity.
If there is no ERROR, returns 0 if true for all q,
1 if true at primitive p_root of unity, 2 otherwise.
If flag is nonzero and the relation is not OK then the
difference between the two sides is output.
RETURN:
ERROR, 0, 1, or 2 as described above.
NAME:
check_commute
SYNOPSIS:
INT check_commute (OP mat1, OP mat2, OP p_root, INT flag)
DESCRIPTION:
Checks that the matrices satisfy the third Hecke algebra
relation. ( m1*m2 == m2*m1 )
If p_root=0, then the relations are checked for general q.
Otherwise they are checked for q a primitive p_root of unity.
If there is no ERROR, returns 0 if true for all q,
1 if true at primitive p_root of unity, 2 otherwise.
If flag is nonzero and the relation is not OK then the
difference between the two sides is output.
RETURN:
ERROR, 0, 1, or 2 as described above.
NAME:
check_zero_matrix
SYNOPSIS:
INT check_zero_matrix (OP mat, OP p_root)
DESCRIPTION:
Checks that the matrix is zero.
If p_root=0, then the matrix is checked for general q.
Otherwise it is checked for q a primitive p_root of unity.
If there is no ERROR, returns 0 if zero for all q,
1 if zero at primitive p_root of unity, 2 if nonzero.
RETURN:
ERROR, 0, 1, or 2 as described above.
COMMENT:
/********************************************************************
Here follow routines to add or multiply hecke algebra elements
********************************************************************/
NAME:
hecke_add
SYNOPSIS:
INT hecke_add (OP hecke1, OP hecke2, OP result)
DESCRIPTION:
The hecke algebra elements hecke1 and hecke2,
which are linear combinations of permutations
as described in the preamble, are added to
give result. hecke1 and hecke2 are unchanged.
RETURN:
ERROR or OK.
NAME:
hecke_mult
SYNOPSIS:
INT hecke_mult (OP hecke1, OP hecke2, OP result)
DESCRIPTION:
The hecke algebra elements hecke1 and hecke2,
which are linear combinations of permutations
as described in the preamble, are multiplied to
give result. hecke1 and hecke2 are unchanged.
RETURN:
ERROR or OK.
NAME:
hecke_scale
SYNOPSIS:
INT hecke_scale (OP hecke, OP power, OP coeff)
DESCRIPTION:
The hecke algebra element hecke which is a linear
combinations of permutations as described in the
preamble, is multiplied by coeff*q^power where
coeff & power are both INTEGER objects.
RETURN:
ERROR or OK.
COMMENT:
/********************************************************************
Here follows a list of prototypes for the routines described above.
********************************************************************/
/* function prototypes for generic representation routines */
INT generate_standard_tableaux (OP partition, OP std);
INT hecke_generator_reps (OP partition, OP vector);
INT represent_hecke_element (OP partition, OP hecke, OP mat);
INT build_lc (OP schizo, OP list);
INT hecke_action_lc_on_lc (OP tableaux, OP hecke, OP result);
INT standardise_cold_tableaux_list (OP tableaux, OP result);
INT input_tableau (OP partit, OP tab);
INT input_lc_permutations (OP save);
INT substitute_one_matrix (OP mat);
INT substitute_one_monopoly (OP mp);
/* function prototypes for nongeneric representation routines */
INT root_dimension (OP partition, OP p_root, OP dim);
INT generate_root_tableaux (OP partition, OP p_root, OP std);
INT hecke_root_generator_reps (OP partition, OP p_root, OP vector);
INT root_represent_hecke_action (OP partition, OP p_root, OP hecke, OP mat);
INT root_standardise_cold_tableaux_list (OP tableaux, OP p_root, OP result);
/* function prototypes for matrix representation checking routines */
INT check_hecke_generators (OP vector, OP p_root, INT flag);
INT check_hecke_quadratic (OP mat, OP p_root, INT flag);
INT check_braid (OP mat1, OP mat2, OP p_root, INT flag);
INT check_commute (OP mat1, OP mat2, OP p_root, INT flag);
INT check_zero_matrix (OP mat, OP p_root);
/* function prototypes to add or multiply hecke algebra elements */
INT hecke_add (OP hecke1, OP hecke2, OP result);
INT hecke_mult (OP hecke1, OP hecke2, OP result);
INT hecke_scale (OP hecke, OP power, OP coeff);
/********************************************************************
Here follow brief descriptions of the example programs.
********************************************************************/
The following programs are each written in the C language, using the
Symmetrica object oriented approach.
EX1.C
This program first requests a partition from the user. It then
calculates the dimension of the corresponding irreducible representation
of H_n in the generic case (using the function dimension_partition()),
and outputs it. It then calculates representation matrices for each
of the generators h_1,h_2,...h_{n1} of H_n. These are stored as
elements of the VECTOR object v. They are output. It is then
checked that they satisfy the Hecke algebra defining relations.
Note that this check may take considerably more time than the
generation of the matrices themselves.
EX2.C
As in EX1.C, a partition is requested, and the dimension of the
corresponding irreducible representation calculated and output.
The user is then requested for a permutation (which should be
input with length not exceeding the weight of the original
partition). The matrix representing the element of H_n
corresponding to the permutation is calculated and output.
Note that in the call to represent_hecke_element(), a linear
combination of permutations is required. This is the reason
that the call to build_lc() is necessary: it converts the
permutation into the required linear combination.
A program more sophisticated than EX2.C would enable a linear
combination of permutations to be input, and thus the matrix
representing an arbitrary element of H_n to be obtained
(using e.g., input_lc_permutations(); c.f. EX2X.C & EX4.C).
Also note that the object w is not freed, since it is inside
l, and is freed when l is freed.
EX3.C
As in EX1.C, a partition is requested, and the dimension of the
corresponding irreducible representation calculated and output.
The user is then requested for a tableau of the corresponding
shape. This should be input row by row, starting from the top
row (or the bottom row if you are French!). The tableau is
then expressed in terms of the standard tableaux, and this
result output. The earlier declaration
english_tableau=TRUE;
ensures that the tableaux are output in the conventional way
for nonFrench people.
Note that the function standardise_cold_tableaux_list() requires
a linear combination of tableaux: hence the preceding call
to build_lc().
Here, account is taken of the possibility that the user enters
an inappropriate tableau (i.e. not one whose entries are distinct
and from {1,2,...,weight_of_partition} ). In such a case, the
function input_tableau() will return an ERROR, and the program
will end gracefully.
EX4.C
As in EX1.C, a partition is requested, and the dimension of the
corresponding irreducible representation calculated and output.
The user is then requested for a tableau, and further for a linear
combination of permutations. The action of the latter on the former
is calculated and output. This list is then standardised.
In essence, the action of an arbitrary element of H_n on a
particular vector in the module is calculated.
Error checking is rife: if one should occur, the program will
exit gracefully.
The way in which input_lc_permutations() requests for input is
as follows: first a permutation is requested, then its one
variable polynomial coefficient is built up a term at a time;
an exponent is input followed by its coefficient. The program
asks whether there are more terms to be added to the polynomial.
When this polynomial coefficient is completed, the program asks
whether there are further permutations. If the answer is 'y', then
they and their coefficients will be requested.
EX5.C
As EX4.C except that the result of the action of the Hecke algebra
element on the tableau can be subsequently acted on by another
Hecke algebra element. And that subsequent result also, and so on.
This program is more conveniently used with input redirected from
a file (using e.g., a.out <input). A sample input file IN5 is provided.
EX1X.C
This program is the same as EX1.C, except that q=1 is substituted
into the final matrices (using the function substitute_one_matrix()
on each matrix). This yields explicit matrix representations
of the generators of the symmetric group. Note that when they are
checked using the function check_hecke_generators(), it is necessary
to specify that we are using a 1st root of unity!
EX2X.C
As for EX2.C except that an arbitrary Hecke algebra element
may be represented. The qlinear combination of permutations
is input using input_lc_permutations() as in EX4.C. The program
finally asks whether there are more elements to represent.
If not, the program finishes; but if so, the entering phase is
repeated. As with EX5.C, the input is more conveniently achieved
using redirected input: a sample input file IN2X is provided.
EX6.C
This program is similar to EX1.C, except that irreducible matrix
representations at roots of unity are generated (but only for
partitions with 2 parts). The user is first prompted for the
primitive index of the root of unity. The program then proceeds
as in EX1.C, except that here the appropriate rootstandard
tableaux are calculated (using generate_root_tableaux()) and
displayed. The integer value of the INTEGER object r is obtained
via s_i_i(r).
EX7.C
This program performs the same function as EX2.C except that an
irreducible matrix representation at root of unity is calculated
for a partition with two parts.
EX8.C
This program performs the same function as EX3.C except that the
result is in terms of the rootstandard tableaux appropriate to
the input (index of the) primitive root of unity.
A little more error checking is performed here and in one instance
t has to be freed since it would not be freed at the end.
EX9.C
This program performs the same function as EX4.C except that,
once more, the result is in terms of the rootstandard tableaux
appropriate to the input (index of the) primitive root of unity.
EX10.C
This program obtains two elements of the Hecke algebra from
the user, and calculates and outputs their product.
Trevor Welsh, Bayreuth, November 1995.
Modified 12/1/96.
