West African Summer School in Algebraic Combinatorics

Cape Coast, Ghana - August 18-29, 2003

Computer Labs

In many of these labs you are expected to write little programs.   All of these exercises involve taking the other procedures and copying and pasting and changing the program a little.  The other exercises ask you to complete a calculation and explain what the computer is telling you by conjecturing a formula or explaining the result.

You will need to know what each of the commands does and Maple will tell you by typing "?" followed by a command name.  For example "? subs" gives a page on how the command "subs" (short for 'substitute') works.  The important part of the help page is almost always at the end where there are examples of how the command is used.  You will probably want to ignore the long detailed explanations because for the most part I do not find them helpful.

A short tutorial on Maple is here.

Notes on symmetric functions that are similar to a computer development.
Or broken into chapters: Chapter 1, Chapter 2, Chapter 3, Chapter 4, Chapter 5.

David Little's notes on partitions and species.

Groups and representations

  1. Introduction to groups and representations - This lab develops a way of working with groups, modules, representations and characters.  The purpose of this lab is to experiment with and break down several modules into their irreducible submodules.  We will use some of these functions in the other labs.
    HTML version
    • Decompose the module of the regular representation of S_3 and S_4 into irreducible submodules
    • Calculate the conjugacy classes of Dn for n=2,3,4,5,6.  Give a description of the conjugacy classes of Dn and then prove your answer.
    • Try to find a matrix T such that T &* permrep5(j) &* T^(-1) is diagonal for all 1 \leq j < 5.  What does this say about the the matrix representation?

  2. The Quotient of C[x1, x2, ..., xn] by the ideal generated by the symmetric functions - We use techniques of Groebner bases to work with the ideal < e_i(x1, x2, ..., xn) : i=1... n>.  A Grobner basis of an ideal is a minimal set of generators which are needed for a computer to "work nicely" with an ideal.  Maple has packages built in to do these these computations.  There is a natural S_n action on this quotient space and so it can be viewed as a graded S_n module. The main exercise of this lab will be to decompose the space for n=4.
    HTML version
    • Find a basis for the ring C[x1,x2,x3,x4]/<e1,e2,e3,e4>, grade this basis by degree since the S_4 action will preserve the degree on the elements of the ring.
    • Define an S_4 action on the basis you found
    • Determine the graded Frobenius image of the ring C[x1, x2, x3, x4]/<e1,e2,e3,e4>. In this exercise you will break this module down into components graded by degree and then determine the Frobenius image.

  3. The Specht module - In this lab we construct an irreducible representation of S_n for each partition of n and we can show that it is irreducible by computing the scalar product of the character of the module with itself.  Finally we experiment with the branching rule and determine what happens to the module when we restrict from S_n to S_{n-1}.
    HTML version
    • Determine which irreducible representations of S_7 when restricted to S_6 will also be irreducible.  How will all of the irreducible representations of S_7 break up under this restriction? Will there ever be any irreducible representations of S_n which when restricted to S_{n-1} break into representations with multiplicity greater than 1?

Symmetric functions

  1. The Schur functions - This lab experiments with several definitions of the Schur functions and shows how they are equivalent.  By finding the coefficient of the Schur function in the power basis the exercise will be to give the character table for S_n.  We will use these functions in other labs to manipulate symmetric functions.
    HTML version
    • Write the functions "Schur_in_e" and "skew_Schur_in_e" (analogous to "Schur_in_h") using the Jacobi-Trudi identity for the e-basis.
    • Use the identity P(t) = ln( H(t) ) to write the functions "pn2h" and "p2h" modeled after the functions "hn2p" and "h2p."  Use these functions to show that p2h(e2p(Schur_in_e(la))) = Schur_in_h(la) for various paritions la.
    • verify the correspondence between each of the monomials in the Schur function s[2,2,1](x1,x2,x3,x4) and the column strict tableaux of shape [2,2,1] in the values 1,2,3,4.
    • What happens when we multiply a Schur function by hk, pk or ek?  Calculate the examples and explain the computer responses,
    • In the Jacobi-Trudi defintion, it is not necessary that the indexing sequence be a partition.  Our function ehp2s will expand this in the Schur basis (which is indexed by a partition).  What happens?

  2. Counting necklaces - We will count the number of ways of coloring a necklace with k beads and n colors in two ways, one of them will be to use symmetric functions the other will be to create lists of numbers which represent necklaces and count the number of orbits under the action of a group.
    HTML version
    • count the number of different necklaces with 5 beads with 3 colors if the beads are allowed to rotate around the necklace
    • count the number of different necklaces with 5 beads and 3 colors if the beads are allowed to rotate around the necklace or the necklace can be flipped over
    • count the number of different necklaces with 5 beads with 3 red, and 1 blue and 1 green if the beads are allowed to rotate around the necklace
    • count the number of different necklaces with 5 beads with 3 red, and 1 blue and 1 green if the beads are allowed to rotate around the necklace or it can be flipped over.
    • Count the number of ways of coloring the faces of the cube with 6 colors so that all 6 faces are a different color.

  3. Tableaux and symmetric functions - In this lab we use the Robinson-Schenstead-Knuth algorithm to decompose symmetric functions in the Schur basis.
    HTML version
    • Add all Schur_in_mon(T, 5) for T all standard tableaux of shape 3 and factor the result (next do 4 and 5).  What do you see?  Why? How does this show that sum_la  f_la s_la = h1^n?
    • Let S be the set of sequences of length 6 in the numbers 1,2,3,4 that may have descents in positions 3 and 4.  Show that the sum over x[w[1]]*x[w[2]]*...*x[w[6]] for w in S is a homogeneous symmetric function.
      Convert each w in S to a pair of tableau and select out the "leading terms" of the Schur functions and then expand these Schur functions in the h-basis.  Do you get the same answer if the words only have the numbers 1,2,3?  What happens if you only have the numbers 1 and 2 in the words?