To begin, select a type of tableau for your output, using the radio buttons. Selecting a radio button will change the type used in subsequent runs of the algorithm.
The page can be used in two ways. First, you can have the page generate a random signed permutation. To do that, enter the size of the desired permutation in the first textbox. Then click the Run button directly to the right. The Run button will display a randomly-generated signed permutation and the output of the Robinson-Schensted algorithm when applied to that permutation. The defects of that tableau pair, the places where the tableaux are not special, are marked with colored squares. After that, the page displays the tableaux made special.
Instead, you can enter a permutation in the second textbox. To do that, list the (positive and negative) numbers of the signed permutation, separated by spaces. Then, use the Run button to the right of that box, as above.
Pressing Enter while in one of these two textboxes will click the Run button to the right. Pressing a button a second time, or a different button, will clear the previous result as it gives you a new result, as will pressing Enter while in a textbox.
This page first displays the Domino Robinson-Schensted algorithm. The Domino Robinson-Schensted algorithm is a relatively straightforward generalization of the Robinson-Schensted algorithm to the hyperoctrahedral group, that is, the group of signed permutations. The input to the Domino Robinson-Schensted algorithm is a "signed permutation", for example, 2 -5 3 6 -4 1. That is, the numbers 1 through n are permuted, and, in addition, each number has a sign (or orientation) associated with it. The output of the Domino Robinson-Schensted algorithm is a pair of domino tableaux with the same shape. That is, instead of a tableau being made of squares, it is made of 2 x 1 shapes (dominos), which can be horizontal or vertical in the tableau. However, unlike the dominos in a game, each domino has only one number in it.
As in the original Robinson-Schensted algorithm, the left tableau is the insertion, or bumping, tableau. The right tableau is the recording tableau. In this algorithm, insertion is either as a horizontal domino in the first row, if the number in the signed permutation is positive, or as a vertical domino in the first column, if the number in the signed permutation is positive. Bumping is also more complicated. A horizontal domino which is bumped entirely moves to the next row below. A vertical domino which is bumped entirely moves to the next column to the right. A domino which is bumped in one square rotates down and to the right on its unbumped square.
After a domino is added to the insertion tableau by this procedure, the resulting change to the shape of the insertion tableau is two squares, adjacent either horizontally or vertically. A domino is then added to the recording tableau to record this change.
You can see an animation of the bumping procedure here: Domino Robinson-Schensted Algorithm Animated.
Domino tableaux are used to answer questions about simple Lie groups of type B, C, or D. To use a domino tableau for a question about a Lie group of a specific type, you need to place the tableau on the grid associated to that type. The grid is the underlying array of 2 x 2 boxes on which the domino tableau is placed. A C type tableau is placed on the grid with its top left square in the top left square of the grid. A D type tableau is placed on the grid with its top left square in the top right square of the grid. A B type tableau is placed on the grid with its top left square in the bottom right square of the grid. In addition, a B type tableau, which is associated with the group SO(2n + 1, ℂ), has a single square with a 0 in it in its top left corner.
Domino tableaux are used to classify Kazhdan-Lusztig cells in the Weyl groups of type Bn, Cn, and Dn. (Or, equivalently, they are used to classify primitive ideals in the enveloping algrbra of the complexified Lie algebra with that Weyl group.) The Domino Robinson-Schensted algorithm starts that process. However, left (or right) cells are classified by tableau with special shape with respect to their grid. To get from the output of the Robinson-Schensted algorithm to the corresponding tableau with special shape, we need to move a tableau through all its open unboxed cycles.
A tableau is special with respect to its grid if every 2 x 2 square of the grid is either filled, half-fulll, or empty (where squares above or to the left of the tableau are considered as filled.) If a 2 x 2 grid square has only one of its four squares filled, that square (called a filled corner) is marked in green. If a 2 x 2 grid square has three of its four squares filled, the empty square (called an empty hole) is marked in purple.
This page first displays the result of applying the Domino Robinson-Schensted algorithm to a signed permutation. If the original tableaux are not special, the defects are marked. Filled corners are marked with green squares. Empty holes are marked with purple squares. After that, the page displays the result of moving the tableaux through their open unboxed cycles. The change in shape is that the squares marked green are no longer in the shape of the tableaux, whereas those marked purple now are.
You can see the process of making a tableau special by moving through its open unboxed cycles on this page: Animate Cycles Special. You can see the process of making a tableau pair special by moving through its open unboxed extended cycles on this page: Animate Extended Cycles Special.