6
$\begingroup$

Let $W(B_n)$ be a Weyl group of type $B_n$ and $SBT (n)$ the set of standard bitableaux of size $n$. Similar to Robinson-Schensted correspondences, I know that there exists a map $W(B_n) \to SBT (n) \times SBT (n)$ such that the image of $W(B_n)$ is the set of the same shape pairs of standard bitableaux.

But, I don't know what the map $W(B_n) \to SBT (n) \times SBT (n)$ is. In particular, $W(B_2) \to SBT (2) \times SBT (2)$? Here \begin{align*} W(B_2) \cong & \left\{ \begin{pmatrix} 1 & 2 & -1 & -2 \\ 1 & 2 & -1 & -2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & -1 & -2 \\ 2 & 1 & -2 & -1 \end{pmatrix}, \begin{pmatrix} 1 & 2 & -1 & -2 \\ -1 & 2 & 1 & -2 \end{pmatrix}, \right. \\ & \left. \begin{pmatrix} 1 & 2 & -1 & -2 \\ 1 & -2 & -1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & -1 & -2 \\ -2 & 1 & 2 & -1 \end{pmatrix}, \begin{pmatrix} 1 & 2 & -1 & -2 \\ 2 & -1 & -2 & 1 \end{pmatrix}, \right. \\ & \left. \begin{pmatrix} 1 & 2 & -1 & -2 \\ -1 & -2 & 1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 & -1 & -2 \\ -2 & -1 & 2 & 1 \end{pmatrix}\right\}. \end{align*}

$\endgroup$

2 Answers 2

3
$\begingroup$

Before getting into my answer, let me explain what I understand by a bitableau of size $n$ (I hope it is the same as what you mean). This is a pair of tableaux $(P, P')$, where each of the integers $1,\dotsc,n$ occurs exactly once, and moreover, the numbers increase along rows and columns in both $P$ and $P'$. The shape of the bitableaux is $(\mu, \mu')$ where $\mu$ and $\mu'$ are the shapes of $P$ and $P'$. Bitableaux of shape $(\mu, \mu')$ correspond to maximal chains in the Bratelli diagram of the sequence of groups $W(B_n)$ which begin at $(\emptyset, \emptyset)$ and end at $(\mu, \mu')$.

The Robinson-Schensted correspondence has a generalization - the RSK correspondence. This correspondence is between (nonnegetive) integer matrices and pairs of semistandard Young tableaux of the same shape (see Knuth's 1970 paper in PJM, or my book). If the rows of the integer matrix sum to $\lambda = (\lambda_1,\dots, \lambda_l)$, and the columns sum to $\mu = (\mu_1,\dotsc, \mu_m)$, then the correspondence associates to $A$ a pair $(P, Q)$ of semistandard young tableaux, $P$ having content $\lambda$, and $Q$ having content $\mu$.

The matrix $A$ is said to be a partial permutation if all the row and column sums are at most $1$. Now, an element $w\in W(B_n)$ may be regarded as a pair of partial permutations, $(A, B)$ such that $A + B$ is a permutation matrix as follows: $A_{ij} = 1$ if $w:j\mapsto i$, and is $0$ otherwise. $B_{ij} = 1$ if $w:j\mapsto -i$, and is $0$ otherwise.

Now apply the RSK correspondence to $A$ and to $B$, getting $(P_A, Q_A)$ and $(P_B, Q_B)$. Then $(P_A, P_B)$ and $(Q_A, Q_B)$ are both bitableaux of the same shape.

Consider for example, the element (in your notation) $$w = \begin{pmatrix} 1 & 2 & 3 & -1 & -2 & -3\\ 2 & -1 & -3 & -2 & 1 & 3 \end{pmatrix}$$ corresponds to the matrices: $$ A = \begin{pmatrix} 0 & 0 & 0\\ 1 & 0 & 0\\ 0 & 0 & 0\end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1\end{pmatrix} $$ Under the RSK correspondence $A$ maps to $P=(1)$, $Q = (2)$ (of shape $(1)$), while $B$ corresponds to $(2, 3)$ and $(1, 3)$ (of shape $(2)$). So the bitableaux pair for $w$ is $(1), (2, 3)$ and $(2), (1, 3)$.

The relation to domino tableaux is rather interesting. Given a bipartition $(\alpha, \beta)$, let $\lambda$ denote the unique partition whose $2$-core is trivial and whose $2$-quotient is $(\alpha, \beta)$. Then adding a box to either $\alpha$ or $\beta$ corresponds to adding a domino to $\lambda$ (see the book by James and Kerber, or the paper of Frame, Robinson and Thrall for details). The size of $\lambda$ will be twice the sum of the sizes of $\alpha$ and $\beta$. Thus we may regard a bitableau of size $n$ as a domino-tableau of size $2n$. Thus the correspondence that I described above may also be regarded as a bijection from $W(B_n)$ onto the set of pairs of domino tableaux of the same shape.

In the running example, the associated domino tableau are $P = \begin{array}{cccc}1&2&3&3\\1&2&&\end{array}$ and $Q = \begin{array}{cccc}1&1&3&3\\2&2&&\end{array}$.

Here is some Sage code for the computation:

from sage.combinat.tableau import from_chain

def matrices(w):
    n = len(w)
    A = Matrix(ZZ, n, n, lambda i,j: int(w[j] == i+1))
    B = Matrix(ZZ, n, n, lambda i,j: int(w[j] == -i-1))
    return A, B

def domino_rsk(w, dominoes=True):
    n = len(w)
    A, B = matrices(w)
    P1, Q1 = tuple(RSK(A))
    P2, Q2 = tuple(RSK(B))
    if dominoes:
        ch_P1 = P1.to_chain(max_entry=n)
        ch_P2 = P2.to_chain(max_entry=n)
        ch_Q1 = Q1.to_chain(max_entry=n)
        ch_Q2 = Q2.to_chain(max_entry=n)
        P = from_chain([Partition(core=[], quotient=[ch_P1[i], ch_P2[i]]) for i in range(n+1)])
        Q = from_chain([Partition(core=[], quotient=[ch_Q1[i], ch_Q2[i]]) for i in range(n+1)])
        return P, Q
    else:
        return [P1,P2], [Q1, Q2]

For the elements of $W(B_2)$, I got (in terms of bitableaux):

[1, 2] ([[[1, 2]], []], [[[1, 2]], []])
[1, -2] ([[[1]], [[2]]], [[[1]], [[2]]])
[-1, 2] ([[[2]], [[1]]], [[[2]], [[1]]])
[-1, -2] ([[], [[1, 2]]], [[], [[1, 2]]])
[2, 1] ([[[1], [2]], []], [[[1], [2]], []])
[2, -1] ([[[1]], [[2]]], [[[2]], [[1]]])
[-2, 1] ([[[2]], [[1]]], [[[1]], [[2]]])
[-2, -1] ([[], [[1], [2]]], [[], [[1], [2]]])

and in terms of domino tableaux:

[1, 2] ([[1, 2, 2], [1]], [[1, 2, 2], [1]])
[1, -2] ([[1, 2], [1, 2]], [[1, 2], [1, 2]])
[-1, 2] ([[1, 1], [2, 2]], [[1, 1], [2, 2]])
[-1, -2] ([[1, 1, 2, 2]], [[1, 1, 2, 2]])
[2, 1] ([[1], [1], [2], [2]], [[1], [1], [2], [2]])
[2, -1] ([[1, 2], [1, 2]], [[1, 1], [2, 2]])
[-2, 1] ([[1, 1], [2, 2]], [[1, 2], [1, 2]])
[-2, -1] ([[1, 1], [2], [2]], [[1, 1], [2], [2]])

This is not the same as the answer obtained by Brian Hopkins, whose dominoes have an extra $0$, and I must admit that I have not looked carefully the references he gave as yet (and am not convinced that this question should need one to read four papers in Compositio). However, if I tweak my code so that $\lambda$ has core $(1)$ and quotient $(\alpha,\beta)$, then I do seem to get his answer.

$\endgroup$
8
  • $\begingroup$ Thank you very much. But I think that \begin{align*} w = \begin{pmatrix} 1 & 2 & 3 & -1 & -2 & -3\\ 2 & -1 & -3 & -2 & 1 & 3 \end{pmatrix} \in W(B_3) .\end{align*} How to define a pair of partial permutations (A,B)? For $w$, could we define $$ A = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{pmatrix}, \quad B = \begin{pmatrix} 0 & 0 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{pmatrix}? $$ $\endgroup$
    – bing
    Oct 11, 2016 at 6:50
  • 1
    $\begingroup$ Yes, I added more details just now, along with the $W(B_2)$ examples and Sage code. Do let me know if you have trouble with the code. My e-mail address is available from my webpage, which is linked in my profile. $\endgroup$ Oct 11, 2016 at 6:58
  • $\begingroup$ @ Amritanshu Prasad Thank you very much. I will send you an E-mail. $\endgroup$
    – bing
    Oct 11, 2016 at 7:04
  • 1
    $\begingroup$ There are two possible (mutually transpose) conventions for representing permutations by matrices. The one I chose is the more commonly used one (used by Knuth). $\endgroup$ Oct 11, 2016 at 7:06
  • 1
    $\begingroup$ Each line of output is an element of $W(D_2)$, followed by a pair of bitableaux. For example $[2, -1]$ is the element $\begin{pmatrix}1 & 2 & -1 &-2\\2&-1&-2&1\end{pmatrix}$. In general, I am simply listing the first $n$ elements of your second row. Then enclosed in parentheses are two domino tableaux, listed by row. So $[[1, 2, 2], [1]]$ represents the tableau $\begin{matrix}1&2&2\\1&&\end{matrix}$. $\endgroup$ Oct 11, 2016 at 7:49
3
$\begingroup$

Devra Garfinkle developed such a correspondence to pairs of domino tableaux in a series of Compositio Mathematica papers in the early 1990s. (The first & third, but curiously not the second, are available through EUDML: https://eudml.org/doc/90031 and https://eudml.org/doc/90244.) More succinct summaries are given in the work of McGovern, van Leeuwen, Shimizono, Pietraho, Taskin, etc.

The $W(B_2)$ example you request doesn't involve any of the horizontal/vertical domino rotations that make this theory tricky, just a little bumping. Here are the 8 domino tableaux pairs in the order you gave the $W(B_2)$ elements. Note that all but the 5th and 6th are involutions, so their left and right tableaux are the same in all but those. [If someone knows how to TeX these into nice domino pictures, please do so and let me know how you do it.]

\begin{gather*} \left(\begin{matrix} 0 & 1 & 1 & 2 & 2 \end{matrix}, \quad \begin{matrix} 0 & 1 & 1 & 2 & 2 \end{matrix}\right), \quad \left(\begin{matrix} 0 & 1 & 1 \\ 2 & 2 \end{matrix}, \quad \begin{matrix} 0 & 1 & 1 \\ 2 & 2 \end{matrix}\right), \\ \\ \left(\begin{matrix} 0 & 2 & 2 \\ 1 \\ 1 \end{matrix}, \quad \begin{matrix} 0 & 2 & 2 \\ 1 \\ 1 \end{matrix}\right), \quad \left(\begin{matrix} 0 & 1 & 1 \\ 2 \\ 2 \end{matrix}, \quad \begin{matrix} 0 & 1 & 1 \\ 2 \\ 2 \end{matrix}\right), \\ \\ \left(\begin{matrix} 0 & 1 & 1 \\ 2 \\ 2 \end{matrix}, \quad \begin{matrix} 0 & 2 & 2 \\ 1 \\ 1 \end{matrix}\right), \quad \left(\begin{matrix} 0 & 2 & 2 \\ 1 \\ 1 \end{matrix}, \quad \begin{matrix} 0 & 1 & 1 \\ 2 \\ 2 \end{matrix}\right), \\ \\ \left(\begin{matrix} 0 & 2 \\ 1 & 2 \\ 1 \end{matrix}, \quad \begin{matrix} 0 & 2 \\ 1 & 2 \\ 1 \end{matrix}\right), \quad \left(\begin{matrix} 0 \\ 1 \\ 1 \\ 2 \\ 2 \end{matrix}, \quad \begin{matrix} 0 \\ 1 \\ 1 \\ 2 \\ 2 \end{matrix}\right). \end{gather*}

(The domino tableaux for $W(C_2)$ also have dominoes labeled 1 and 2, but no 0 square.)

$\endgroup$
5
  • 2
    $\begingroup$ if you want a pair of domino tableaux, I think the local rules given by Thomas Lam are excellent, see Thomas Lam. Growth diagrams, domino insertion and sign-imbalance. Journal of Combinatorial Theory, Series A Volume 107, Number 1 (2004), pp. 87-115. Shameless plug: trac.sagemath.org/ticket/21594 $\endgroup$ Oct 10, 2016 at 17:26
  • 1
    $\begingroup$ Second one's on EUDML too: eudml.org/doc/90142 $\endgroup$ Oct 10, 2016 at 17:35
  • 1
    $\begingroup$ And here's the fourth: math.washington.edu/~mcgovern/G4-2016-1-31.pdf (see mathoverflow.net/questions/223168/… for history) $\endgroup$ Oct 10, 2016 at 17:36
  • 1
    $\begingroup$ Thanks for the updates, especially Thomas and Monty's realization of the long asserted but never seen fourth paper. My answer is based on my thesis work some twenty years ago, but I have not kept up with this field. $\endgroup$ Oct 10, 2016 at 18:34
  • $\begingroup$ @Brian Hopkins Thank you very much. $\endgroup$
    – bing
    Oct 11, 2016 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.