The Hyperoctahedral Group

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 31 March 2012

The Hyperoctahedral Group

The hyperoctahedral group $W{B}_n$ is the group of signed permutations of $1,2,...,n,$ i.e. bijections $w:\{-n,...,-2,-1,1,2,...,n\}\to \{-n,...,-2,-1,1,2,...,n\}$ such that $w(-i)=-w\left(i\right).$ There are multiple notations for signed permutations

1. Two line notations: where $w\left(i\right)$ in the second line is below $i$ in the first line, for $1\le i\le n.$ $$w=\left(\begin{array}{cccccc}1& 2& 3& 4& 5& 6\\ 3& -1& 5& -6& 2& -4\end{array}\right)$$
2. In cycle notation as permutations in the symmetric group $S_{2n}.$ $$w=(1,3,5,2,-1,-3,-5,-2)(4,-6).$$
3. Matrix notation: where the $(\left|w\left(i\right)\right|,i)$ entry is $1$ if $w\left(i\right)$ is positive and $-1$ if $w\left(i\right)$ is negative, and all other entries are $0.$ $$w=\left(\begin{array}{cccccc}0& -1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& -1\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& -1& 0& 0\end{array}\right)$$
4. Diagram notation: where the $i^{\mathrm{th}}$ dot in the top row is connected to the $\left|w\left(i\right)\right|$th dot in the bottom row and the edge is labeled by $-1$ if $w\left(i\right)$ is negative. $$w=\begin{array}{c} -1 -1 -1 \end{array}$$

The hyperoctahedral group is also called the Weyl group of type $B_n$ and the Weyl group of type $C_n$ and is the same as the group $$O_n\left(\mathbb{Z}\right)=\{A\in M_n\left(\mathbb{Z}\right) | A{A}^t=\mathrm{Id}\}.$$ It is the group of $n\times n$ matrices such that

1. there is exactly one nonzero entry in each row and each column,
2. each nonzero entry is $\pm 1.$

The group $W{B}_n$ is isomorphic to the wreath product $(\mathbb{Z}/2\mathbb{Z})\wr S_n$ and has order $2^{n}n!.$

The reflections in $W{B}_n$ are the elements $$s_{{\epsilon }_i}=(i,-i)s_{{\epsilon }_i-{\epsilon }_j}=(i,j)(-i,-j),s_{{\epsilon }_i+{\epsilon }_j}=(i,-j)(-i,j).$$ The simple reflections are $$s_1=(1,-1)=\begin{array}{c} -1 ⋯ \end{array}and{s}_i=(i-1,i)=\begin{array}{c} ⋯ ⋯ \end{array}$$ for $2\le i\le n.$

The hyperoctahedral group $W{B}_n$ can be presented by generators $s_1,s_2,...,s_{n-1}$ and relations $$\begin{array}{rclcl}{s}_i{s}_j& =& s_j{s}_i,& & if\; |i-j|>1,\\ s_i{s}_{i+1}{s}_i& =& s_{i+1}{s}_i{s}_{i+1},& & 2\le i\le n-1,\\ s_1{s}_2{s}_1{s}_2& =& s_2{s}_1{s}_2{s}_1,& & \\ s_i^2& =& 1,& & 1\le i\le n.\end{array}$$

		Proof.
	There are three things to show: The simple reflections in $W{B}_n$ satisfy the given relations. The simple reflections in $W{B}_n$ generate $W{B}_n.$ The group given by generators $s_1,...,s_n$ and the relations in the statement has $2^{n}n!.$ The following pictures show that $s_1,...,s_n\in W{B}_n$ satisfy the relations in the statement of the theorem. $$\begin{array}{c} -1 -1 \end{array}=\begin{array}{c} \end{array}\begin{array}{c} -1 \end{array}=\begin{array}{c} -1 \end{array}=\begin{array}{c} -1 \end{array}\begin{array}{c} -1 -1 \end{array}=\begin{array}{c} -1 -1 \end{array}=\begin{array}{c} -1 -1 \end{array}$$ For each $1\le i\le n$ let $$t_i=(i,-i)=\begin{array}{c} -1 ith ⋯ ⋯ \end{array}=s_i{s}_{i-1}\cdots s_3{s}_2{s}_1{s}_2{s}_3\cdots s_{i-1}{s}_i.$$ Every $w\in W{B}_n$ can be written as $w=\pi t_{i_1}\cdots t_{i_k}$ where $\pi \in S_n$ is the permutation given by $\pi \left(i\right)=\left|w\left(i\right)\right|$ and $\{i_1,...,i_k\}=\left\{i \right| w\left(i\right) \; is\; negative\}.$ Pictorially $$w=\begin{array}{c} -1 -1 -1 \end{array}=\begin{array}{c} -1 -1 -1 \end{array}=\pi t_1{t}_3{t}_6$$ Since $s_2,...,s_n$ generate $S_n$ and $t_k=s_k\cdots s_2{s}_1{s}_2\cdots s_k$ for $1\le k\le n,$ it follows that $s_1,...,s_n$ generate $W{B}_n.$ Let $G_n$ be the free group generated by $s_1,...,s_n$ modulo the relations in the statement of the theorem. We will show that every element $w\in G_n$ is either $w\in G_{n-1},$ $w=w_1{s}_n{s}_{n-1}\cdots s_k,$ with $w_1\in G_{n-1}, 2\le k\le n,$ $w=w_1{s}_n{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_k,$ with $w_1\in G_{n-1}, 1\le k\le n.$ Let $w\in G_n$ and assume that $$w=w_1{s}_n{w}_2{s}_n{w}_3{s}_n\cdots w_{l-1}{s}_n{w}_l,where\; w_j\in G_{n-1}.$$ First we will show that every element of $G_n$ can be written in the form $$w=w_1{s}_n{w}_2{s}_n,with\; w_1,w_2\in G_{n-1}.$$ Suppose $w=w_1{s}_n{w}_2{s}_n{w}_3,$ with $w_1,w_2,w_3\in G_{n-2}.$ Then, by the induction assumption, $$\begin{array}{rcl}w& =& w_1{s}_{n}a{s}_{n-1}b{s}_{n-1}{s}_{n}c{s}_{n-1}d{s}_{n-1}\\ & =& w_{1}a{s}_n{\displaystyle \underset{}{\underbrace{s_{n-1}b{s}_{n-1}c}}}{s}_n{s}_{n-1}d{s}_{n-1}\\ & =& w_{1}a{s}_{n}x{s}_{n-1}y{s}_{n-1}{s}_n{s}_{n-1}d{s}_{n-1}\\ & =& w_{1}ax{s}_n{s}_{n-1}y{s}_n{s}_{n-1}{s}_{n}d{s}_{n-1}\\ & =& w_{1}ax{s}_n{s}_{n-1}{s}_{n}y{s}_{n-1}{s}_{n}d{s}_{n-1}\\ & =& {\displaystyle \underset{}{\underbrace{w_{1}ax{s}_{n-1}}}}{s}_n{\displaystyle \underset{}{\underbrace{s_{n-1}y{s}_{n}d}}}{s}_n{s}_{n-1}\\ & =& A{s}_n\beta s_{n-1}\gamma s_{n-1}{s}_n{s}_{n-1}\\ & =& A\beta s_n{s}_{n-1}\gamma s_n{s}_{n-1}{s}_n\\ & =& A\beta s_n{s}_{n-1}{s}_n\gamma s_{n-1}{s}_n\\ & =& {\displaystyle \underset{}{\underbrace{A\beta s_{n-1}}}}{s}_n{\displaystyle \underset{}{\underbrace{s_{n-1}\gamma s_{n-1}}}}{s}_n\\ & =& {w\prime }_1{s}_n{w\prime }_2{s}_n.\end{array}$$ It follows that if $w=w_1{s}_n{w}_2{s}_n{w}_3{s}_n$ with $w_1,w_2,w_3\in G_{n-2}$ then $w={w\prime }_1{s}_n{w\prime }_2{s}_n{s}_n={w\prime }_1{s}_n{w\prime }_2.$ Then, by the induction assumption $$w=w_1{s}_n{w}_2{s}_n,$$ with $w_2\in G_{n-2},$ or $w_2=a{s}_{n-1}\cdots s_k$ and $a\in G_{n-2},$ or $w_2=a{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_k$ and $a\in G_{n-2}.$ Case 1. $$w=w_1{s}_n{w}_2{s}_n=w_1{w}_2{s}_n{s}_n=w_1{w}_2\in G_{n-1}.$$ Case 2. $$\begin{array}{rcl}w& =& w_1{s}_{n}a{s}_{n-1}\cdots s_k{s}_n\\ & =& w_{1}a{s}_n{s}_{n-1}{s}_n{s}_{n-2}\cdots s_k\\ & =& w_{1}a{s}_{n-1}{s}_n{s}_{n-1}{s}_{n-2}\cdots s_k\\ & =& {w\prime }_1{s}_n{s}_{n-1}\cdots s_k,\end{array}$$ with ${w\prime }_1\in G_{n-1}.$ Case 3. $$\begin{array}{rcl}w& =& w_1{s}_{n}a{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_k{s}_n\\ & =& \{\begin{array}{ll}{w}_{1}a{s}_n{s}_{n-1}{s}_n{s}_{n-2}\cdots s_2{s}_1{s}_2\cdots s_k,& if\; k<n-1,\\ w_{1}a{s}_n{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_{n-1}{s}_n,& if\; k=n-1,\end{array}\phantom{\}}\\ & =& \{\begin{array}{ll}{w}_{1}a{s}_{n-1}{s}_n{s}_{n-1}{s}_{n-2}\cdots s_2{s}_1{s}_2\cdots s_k,& if\; k<n-1,\\ w_{1}a{s}_n{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_{n-1}{s}_n,& if\; k=n-1,\end{array}\phantom{\}}\\ & =& {w\prime }_{1}a{s}_n{s}_{n-1}\cdots s_2{s}_1{s}_2\cdots s_k,\end{array}$$ with ${w\prime }_1\in G_{n-1}.$ So $\mathrm{Card}\left(G_n\right)\le \mathrm{Card}\left(G_{n-1}\right)\cdot 2n.$ So $\mathrm{Card}\left(G_n\right)\le 2^{n}n!.$ $\square$

Let $(\alpha ,\beta )$ be a pair of partitions sucht that the total number of boxes in $\alpha$ and $\beta$ is $n.$ A standard tableau of shape $(\alpha ,\beta )$ is a filling $T$ of the boxes of $\alpha$ and $\beta$ with $1,2,...,n$ such that, in each partition,

1. the rows of $T$ are increasing left to right,
2. the columns of $T$ are increasing top to bottom.

$$T=\begin{array}{c} 1 5 7 4 10 12 8 13 α 2 3 9 6 11 β \end{array}$$ The rows and columns of each partition are indexed as for matrices, $$\begin{array}{rcl}T\left(i\right)& =& box\; containing\; i \; in\; T,\\ c\left(b\right)& =& j-i, \; if\; the\; box\; b \; is\; in\; position\; (i,j),\\ \mathrm{sgn}\left(b\right)& =& \{\begin{array}{ll}1,& if\; b \; is\; in\; \alpha ,\\ -1,& if\; b \; is\; in\; \beta .\end{array}\phantom{\}}\end{array}$$ The numbers $c\left(b\right)$ and $\mathrm{sgn}\left(b\right)$ are the content and the sign of the box $b,$ respectively. $$\begin{array}{c} 0 1 2 -1 0 1 -2 -1 0 1 2 -1 0 \\ Contents\; of\; boxes\end{array}\begin{array}{c} 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 \\ Signs\; of\; boxes\end{array}$$

1. The irreducible representations $S^{(\alpha ,\beta )}$ of the hyperoctahedral group $W{B}_n$ are indexed by pairs of partitions $(\alpha ,\beta )$ with $n$ boxes total.
2. $\dim S^{(\alpha ,\beta )}=\#$ of standard tableaux of shape $(\alpha ,\beta ).$
3. The irreducible $W{B}_n-$module $S^{(\alpha ,\beta )}$ is given by $$S^{(\alpha ,\beta )}=ℂ-span\left\{v_T \right| T \; is\; a\; standard\; tableau\; of\; shape\; (\alpha ,\beta )\}$$ with basis $\left\{v_T\right\}$ and with $W{B}_n$ action given by $$\begin{array}{rcl}{s}_1{v}_T& =& \mathrm{sgn}\left(T\left(1\right)\right)v_T,\\ s_i{v}_T& =& {\left(s_i\right)}_{TT}{v}_T+(1+{\left(s_i\right)}_{TT})v_{s_{i}T},i=2,3,...,n,\end{array}$$ where
   1. $s_1=(1,-1)$ and $s_i=(i,i-1)(-i,-(i-1)),$
   2. ${\left(s_i\right)}_{TT}=\{\begin{array}{ll}\frac{1}{c\left(T\left(i\right)\right)-c\left(T(i-1)\right)},& if\; \mathrm{sgn}\left(T\left(i\right)\right)=\mathrm{sgn}\left(T(i-1)\right),\\ 0,& if\; \mathrm{sgn}\left(T\left(i\right)\right)\ne \mathrm{sgn}\left(T(i-1)\right),\end{array}\phantom{\}}$
   3. $c\left(T\left(i\right)\right)$ is the content of the box containing $i$ in $T,$
   4. $\mathrm{sgn}\left(T\left(i\right)\right)$ is the sign of the box containing $i$ in $T,$
   5. $s_{i}T$ is the same as $T$ except that $i$ and $i-1$ are switched, and
   6. $v_{s_{i}T}=0,$ if $s_{i}T$ is not a standard tableau.

		Proof.
	We must show that The $S^{(\alpha ,\beta )}$ are $W{B}_n$ modules, The $S^{(\alpha ,\beta )}$ are irreducible $W{B}_n$ modules, The $S^{(\alpha ,\beta )}$ are inequivalent $W{B}_n$ modules, These are all the simple $W{B}_n$ modules. The proofs are similar to the proofs of the analogous statements in the symmetric group case. $\square$

Define elements $x_k, y_k,$ $1\le k\le n,$ in the group algebra of the hyperoctahedral group $W{B}_n$ by $$\begin{array}{rcll}{y}_k& =& (k,-k),& for\; 1\le k\le n,\\ x_1& =& 0,& and,\\ x_k& =& \sum _{i<k}(i,k)(-i,-k)+(i,-k)(-i,k),& 2\le k\le n.\end{array}$$ The action of these elements of the $W{B}_n-$module $S^{(\alpha ,\beta )}$ is given by $$y_k{v}_T=\mathrm{sgn}\left(T\left(k\right)\right)v_{T}and{x}_k{v}_T=c\left(T\left(k\right)\right)v_T,$$ where $\mathrm{sgn}\left(T\left(k\right)\right)$ and $c\left(T\left(k\right)\right)$ are the sign and the content of the box containing $k$ in $T,$ respectively.

		Proof.
	By induction $$\begin{array}{rcl}{y}_k{v}_T& =& s_k{y}_{k-1}{s}_k{v}_T\\ & =& s_k{y}_{k-1}({\left(s_k\right)}_{TT}{v}_T+(1+{\left(s_k\right)}_{TT})v_{s_{k}T})\\ & =& s_k(\mathrm{sgn}\left(T(k-1)\right){\left(s_k\right)}_{TT}+\mathrm{sgn}\left(T\left(k\right)\right)(1+{\left(s_k\right)}_{TT})v_{s_{k}T})\\ & =& \mathrm{sgn}\left(T\left(k\right)\right)s_k(s_k{v}_T+\frac{(\mathrm{sgn}\left(T(k-1)\right)-\mathrm{sgn}\left(T\left(k\right)\right))(1+\mathrm{sgn}\left(T\left(k\right)\right)\mathrm{sgn}\left(T(k-1)\right))}{c\left(T\left(k\right)\right)-c\left(T(k-1)\right)})v_T\\ & =& \mathrm{sgn}\left(T\left(k\right)\right)v_T.\end{array}$$ $\square$

Note that $$\dim \left(S^{(\alpha ,\beta )}\right)=\left(\genfrac{}{}{0ex}{}{n}{\left|\alpha \right|}\right)f^{\alpha }{f}^{\beta },$$ where $f^{\alpha }$ is the number of standard tableaux of shape $\alpha .$ Thus $f^{\alpha }$ is the dimension of the irreducible module $S^{\alpha }$ for the symmetric group $S_{\left|\alpha \right|}.$ Then $$\begin{array}{rcl}\sum _{\alpha ,\beta }\dim {\left(S^{(\alpha ,\beta )}\right)}^2& =& \sum _{\alpha ,\beta }{\left(\genfrac{}{}{0ex}{}{n}{\left|\alpha \right|}\right)}^2{\left(f^{\alpha }\right)}^2{\left(f^{\beta }\right)}^2\\ & =& \sum _{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2\left(\sum _{\alpha ⊢k}{\left(f^{\alpha }\right)}^2\right)\left(\sum _{\beta ⊢n-k}{\left(f^{\beta }\right)}^2\right)\\ & =& \sum _{k=0}^n\frac{n!}{k!(n-k)!}k!(n-k)!\left(\genfrac{}{}{0ex}{}{n}{k}\right)\\ & =& \sum _{k=0}^{n}n!\left(\genfrac{}{}{0ex}{}{n}{k}\right)\\ & =& 2^{n}n!.\end{array}$$

Notes and References

Where are these from?

References

References?

page history