Friday, May 2, 2008

Rothe Diagram

Last week I attended a seminar entitled "Symmetric Group Sn and it's Kissing Cousins", given by Ta Khongsap. This came hot on the heals of Dr. Arone's treatment of the Barratt-Priddy-Quillen Theorem (relating classifying spaces of the symmetric group with stable spheres, totally awesome, I should probably return to it again here sometime). The two together made me think I should probably try to learn more about the symmetric group. In the mean time, I wanted to mention one of the interesting things Ta brought up in his talk, called a Rothe/Lehmer Diagram.

Recall that the symmetric group on n letters (denoted here by Sn) is generated by the elementary transpositions si, for i=1,...,n-1, where si just switches i and i+1 (so it is typically written (i i+1)). Given an arbitrary σ in Sn, we might like to know how to write σ as a product of the generators si (say, using the least number of generators). To do this, we begin with the Rothe diagram, constructed as follows: Consider an n by n array, and in the i-th row, put an 'X' in the σ(i)-th column. For example, the permutation (1 4 2 5 3) in cycle notation (which I'll take to be in S5) has Rothe diagram:

 . . . X . . . . . X X . . . . . X . . . . . X . .

Next what Ta had us do was draw lines down from every 'X', and lines right from every 'X'. While I'm sure it looks terrible here, hopefully you get the idea:

 . . . X - . . . | X X - - + + | X - + + | | X + +

We're almost there. To finish up making the diagram, work your way down the rows. In each row, work right to left as follows: if you are in the i-th row, start with si in the right-most open cell, then si+1 in the next-right-most open cell, etc. So in the example above, we'll get:

 s3 s2 s1 X - s4 s3 s2 | X X - - + + | X - + + | | X + +

Now we can read off the product of the si, from top to bottom, left to right, and we see that:

σ=s3s2s1s4s3s2

(which is easy to check).

For more on this topic, I might point you toward either of these pages.

(I know this post broke my pretty borders on the left side of the page... sigh) [Update 12 May 2008: fixed it with a span around everything. Now about that ugly whitespace...]