´

The ladder game


The ladder game is an algorithm for the stepwise determination of transversals of the sets of double cosets $A\backslash G/L_1$to $A\backslash G/L_\alpha$for a subgroup $A$of a group $G$and a sequence of subgroups, a so-called ladder, $L_1,\ldots, L_\alpha$of $G$with either $L_i\ge L_}$or $L_\ge L_i$for all $i=1,\ldots \alpha-1$.

We call a step from $A\backslash G/L_i$to $A\backslash G/L_$with $L_i\ge L$a step down. A double coset of $A$and $L_i$splits into double cosets of $A$and $L_$:

\begin{displaymath}AgL_i=\bigcup_{t\in T_i}AgtL_,\end{displaymath}


for a transversal $T_i$of $L_{/L$. Therefore, a transversal of the $(A,L)$-double cosets is a subset of $\{gt\vert g\in D_i,t \in T_i\}$where $D_i$means a transversal of the $(A,L_i)$-double cosets. This subset has to be determined.

A step up from $A\backslash G/L_i$to $A\backslash G/L$is a step with $L\ge L_{i}$. Such double cosets of $A$and $L_i$fuse to a double coset of $A$and $L$:

\begin{displaymath}\bigcup_{t\in T_i}AgtL_i=AgL,\end{displaymath}


for a transversal $T_i$of $L_/L_i$. We obtain a transversal of the double cosets of $A$and $L$as a subset of a transversal of the double cosets of $A$and $L_i$.

To keep down the complexity of this algorithm, we should try to choose a ladder $L_1,\ldots, L_\alpha$with a small index between $L_i$and $L_{}$for all $i=1,\ldots,\alpha-1$, because during each step, dow or up, respectively, we run through a transversal of $L_i/L_{}$and $L_{}/L_i$, respectively.

In order to visualize the ladder game we introduce a graph which we call orbit graph:

  • The $(A,L_i)$-double cosets, $i=1,\ldots,\alpha$, correspond to the vertices of the graph.
  • Two vertices are connected by an edge iff the corresponding double cosets $Ag_{L_{i_1}$and $Ag_{L_{i_2}$fulfill
    1. $\vert i_1-i_2\vert=1$
    2. $Ag_{L_{i_1}\subseteq Ag_{i_2}L_{i_2}$or $Ag_{L_{i_2}\subseteq Ag_{i_1}L_{i_1}$.
  • Each vertex is labeled by a tuple $(i,j,k)\in {\mathbb{N}}^3$, where $i$means the step in the ladder game, $j$is the $j$-th double coset of $A$and $L_i$and $k$is the order of the stabilizer of the corresponding double coset in $A$.

Let us return to the determination of transversals of $A\backslash GL_v(q)/GL_v(q)_{S_k}$and of $A\backslash GL_v(q)/GL_v(q)_{S_t}.$We need a ladder of $GL_v(q)$containing $GL_v(q)_{S_k}$and $GL_v(q)_{S_t}$. For this purpose we take the following sequence of parabolic subgroups (generalizing this way the ladder game that we applied to designs on sets, where we took a ladder of Young subgroups!)

 $$

$GL_v(q)$

 $$

$GL_v(q)_{S_{v-1}}$

 $$

$GL_v(q)_{S_{v-1}}\cap GL_v(q)_{S_{v-2}}$

 $$

$GL_v(q)_{S_{v-2}}$

$\vdots$

 $$

$GL_v(q)_{S_{2}}$

 $$

$GL_v(q)_{S_{2}}\cap GL_v(q)_{S_{1}}$

 $$

$GL_v(q)_{S_{1}}$

as a ladder. Starting from the trivial transversal of $A\backslash GL_v(q)/GL_v(q)$we can determine step by step all transversals of $A\backslash GL_v(q)/GL_v(q)_{S_i}$for all $i=v-1,\ldots,1$.

Let us display a concrete example: We take the parameters $(v,q):=(4,2)$and, for $A\le GL_4(2),$we choose $A:=M_4(q)$, the complete monomial group, which is isomorph to the wreath product $GF(2)^*\wr S_4$. Then we get the following orbit graph:


\begin{picture}(90,70) \put(7,35){\circle{1.5}} \put(3,33){\tiny (0,0,24)} \p... ...\bezier{46}(67,61)(74,52)(82,43) \bezier{86}(67,66)(74,45)(82,25) \end{picture}

In this graph the vertices with the labels $(3,-,-)$correspond to the orbits of $M_4(2)$on the set of $2$-supspaces of $GF(2)^4$and the vertices labeled by the tuples $(5,-,-)$correspond to the orbits of $M_4(2)$on the set of $1$-subspaces.

Back to the title page

University of Bayreuth -