Rothe Diagram

Last week I attended a seminar entitled "Symmetric Group S_n 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 S_n) is generated by the elementary transpositions s_i, for i=1,...,n-1, where s_i just switches i and i+1 (so it is typically written (i i+1)). Given an arbitrary σ in S_n, we might like to know how to write σ as a product of the generators s_i (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 S₅) 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 s_i in the right-most open cell, then s_i+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 s_i, from top to bottom, left to right, and we see that:

σ=s₃s₂s₁s₄s₃s₂

(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...]