$W$-graphs

$W$-graphs#

Given a Coxeter system $(W,S)$, a $W$-graph is a (directed or undirected) graph with vertex labels and edge weights. The label attached to a vertex $v$ is a subset of $S$ (called the descent set of $v$) and the edge weights are scalars (usually integers).

A $W$-graph must determine a representation of the Hecke algebra $H = H\langle q\rangle$ of the associated Coxeter system. The vertices of the $W$-graph can be identified with basis elements of the representation space, and by the conventions adopted here the action of the generator $T_s$ of $H$ associated with an element $s\in S$ on a basis element $v$ is given by

\[v*T_s = \cases{ (-q^{-1})*v & if $s$ is in the descent set of $v$,\cr q*v + \sum' (m*u)&if $s$ is not in the descent set of $v$,\cr}\]

where $\sum'$ indicates the sum over all edges with terminal vertex equal to $v$ for which $s$ is in the descent set of the initial vertex $u$, and $m$ is the weight of the edge.

For the Coxeter group calculations involved in these functions we need to know how the generators $s\in S$ act on the set of elementary roots (see [Brink, 1998]).

Magma has a function ReflectionTable that provides the necessary information. Specifically, let $W$ be a finitely presented Coxeter group with $N$ elementary roots (numbered from 1 to $N$) and $r$ simple reflections (numbered 1 to $r$). If we define

eltroots:=ReflectionTable(W);

then for $i\in \{1, \dots, r\}$ and $j\in \{1, \dots, N\}$, eltroots[i,j] = k if the $i$-th simple reflection takes the $j$-th elementary root to the $k$-th elementary root, or to a non-elementary root if $k = 0$, or to a negative root if $k < 0$. (This last alternative occurs if and only if $j = i$ and $k = -i$.) Knowing the table eltroots makes it quick and easy to do symbolic computation with elements of $W$, represented as sequences of integers in $\{1, \dots,r\}$ (corresponding to words in $S$).

SetVerbose("WGraph", v): MonStgElt, RngIntElt#: Set the verbose printing to level $v$ for all $W$-graph related functions. A level of $2$ means that informative messages and progress information will be printed durng a computation.

Sometimes it is convenient to use ‘mij-sequences’ to specify Coxeter groups. The mij-sequence consists of the on or below diagonal entries in the Coxeter matrix. Thus if seq is the mij-sequence and $M$ the Coxeter matrix then

M := SymmetricMatrix(seq);

and

seq := &cat[[M[i,j] : j in [1..i]] : i in [1..Rank(W)]];

Mij2EltRootTable(seq): SeqEnum → SeqEnum[SeqEnum[RngIntElt]]#: Return the elementary root action table for the Coxeter group defined by the given mij-sequence.

Name2Mij(name): MonStgElt → SeqEnum#: The mij-sequence of the Coxeter groups of type name.

Example: mijseq#

> e6:=[1,3,1,2,3,1,2,3,2,1,2,2,2,3,1,2,2,3,2,2,1];
> E6 := CoxeterGroup(GrpFPCox, SymmetricMatrix(e6) );
> ReflectionTable(E6) eq Mij2EltRootTable(e6);

true

The functions defined in this section are mainly concerned with $W$-graph posets. The motivating example for this concept is the set of all standard tableaux corresponding to a given partition, the partial order being dominance. By definition, if $P$ is a $W$-graph poset then $P$ must be in one-to-one correspondence with a basis for an $H$-module $V$ (where $H$ is the Hecke algebra associated with the given Coxeter system). In the standard tableaux example, this module is the Specht module; hence in the general case we refer to the module $V$ as GSM($P$) (for generalized Specht module). For each $v\in P$ the set $S$ must be the disjoint union of two sets $A(v)$ and $D(v)$, the ascents and descents of $v$. There must be a function $(s,v) \mapsto sv$ from $S \times P$ to $P$ such that the action of $H$ on GSM(P) satisfies the following rules (for all $s \in S$ and $v \in P$):

\[v*T_s = \cases{ sv &if $sv > v$,\cr sv + (q-q^{-1})*v &if $sv < v$,\cr -q^{-1}*v &if $sv = v$ and $s\in D(v)$,\cr q*v + q*\langle\hbox{earlier}\rangle &if $sv = v$ and $s \in A(v)$,\cr}\]

where $\langle$earlier$\rangle$ denotes a linear combination of $\{u \in P \mid u < v\}$ with coefficients that are polynomials in $q$. For each $s \in A(v)$ either $sv = v$ or $sv > v$, and for each $s \in D(v)$ either $sv < v$ or $sv = v$. This (admittedly strange) definition is motivated by the fact that Specht modules satisfy it. If $v$ is a standard tableau corresponding to a partition of $n$ then a number $i$ in $\{1,\dots,n-1\}$ is an ascent of $v$ if $i+1$ is in a later column of $t$ than $i$, and is a descent of $v$ if $i+1$ is in a lower row of $t$ than $i$. The fact that Specht modules satisfy the formulas above is proved in the literature (e.g. Mathas’ book), except that in the “weak ascent” case ($sv = v$ and $s \in A(v)$) it is not proved that the polynomial coefficients of $\{u \in P \mid u < v\}$ are all divisible by $q$. The fact that they are is a theorem of V. M. Nguyen (PhD thesis, University of Sydney, 2010). It turns out that there is an algorithm by which a $W$-graph may be constructed from a $W$-graph poset, the $W$-graph being uniquely determined by the function $(s,v) \mapsto sv$ from $S \times P \to P$ and the descent/ascent sets. The polynomial coefficients in the weak ascent case are not required. Of course the $H$-module determined by the resulting $W$-graph is isomorphic to GSM($P$).

Partition2WGtable(pi): SeqEnum → SeqEnum, GrpFPCox#: Returns the $W$-graph table and the Weyl group for the partition pi, where pi is a nonincreasing sequence $[a_1,a_2,\dots,a_k]$ of positive integers. It returns the table corresponding to the $W$-graph poset of standard tableaux of the given shape and the finitely presented Coxeter group of type $A_n$, where $n+1 = \sum a_i$.

WGtable2WG(table): SeqEnum → GrphUnd#: Convert a $W$-graph table to a $W$-graph.

TestWG(W, wg): GrpFPCox, GrphUnd → .#

TestWG(W, wg): GrpFPCox, GrphDir → .#

TestWG(tp, wg): MonStgElt, GrphDir → .#

TestWG(tp, wg): MonStgElt, GrphDir → .#

This procedure can be used to test whether a presumed undirected or directed $W$-graph is indeed a $W$-graph, where $W$ is a finitely presented Coxeter group of type tp. Two input values are required: the Coxeter group $W$ (or its type) and the $W$-graph. When applied to the $W$-graph produced by the WGtable2WG function, this tests whether the input table did genuinely correspond to a $W$-graph poset.

For example,

Example: Specht Wgraph#

> SetVerbose("WGraph",1);
> wtable, W :=Partition2WGtable([4,4,3,1]);
> wg := WGtable2WG(wtable);
> TestWG(W,wg);

which should cause the word true to be printed 66 times (as the defining relations of the Hecke algebra are checked).

Given a Coxeter system $(W,S)$ and an element $w\in W$, let $P$ be the set $\{x\in W \mid \hbox{length}(wx^{-1}) = \hbox{length}(w) - \hbox{length}(x)\}$, considered as a poset under the Bruhat order on $W$. Given also a subset $J$ of $\{t\in S \mid \hbox{length}(wt) > \hbox{length}(w)\}$, for each $x\in P$ we define $D(x)$ to be union of $\{s\in S \mid \hbox{length}(sx) < \hbox{length}(x)\}$ and $\{s \in S \mid sx = xt \hbox{ for some } t \in J \}$. If $P$ is now a $W$-graph poset with the sets $D(x)$ as the descent sets then we say that $w$ is a $W$-graph determining element relative to $J$.

For example, suppose that $(W,S)$ is of type $A_n$, and given a partition of $n+1$ let $t$ be the (unique) standard tableau whose column group is generated by a subset of $S$. Let $w$ be the maximal length element such that the tableau $wt$ is standard. Then $w$ is a $W$-graph determining element with respect to the set $J$ consisting of those $s \in S$ that are in the column stabilizer of $t$.

Other examples (for any Coxeter system with finite $W$) are provided by the distinguished left coset representatives of maximal length for standard parabolic subgroups $W_K$ (where the set $J$ may be taken to be either $K$ or the empty set).

WGelement2WGtable(g, K): GrpFPCoxElt, SetEnum → SeqEnum, SeqEnum#: Returns the $W$-graph table and $W$-graph ideal of a $W$-graph determining element $g$, subset $K$.

Example: B5Wgraph#

> b5 := [1,4,1,2,3,1,2,2,3,1,2,2,2,3,1];
> b5mat := SymmetricMatrix(b5);
> W := CoxeterGroup(GrpFPCox, b5mat );
> table, _ := WGelement2WGtable(W![5,4,3,2,1,2,3,4,5],{});
> wg := WGtable2WG(table);
> TestWG(W,wg);

true <1, 2> 4
true <2, 3> 3
true <3, 4> 3
true <4, 5> 3

GetCells(wg): GrphUnd → SeqEnum#

GetCells(wg): GrphDir → SeqEnum#: Return the cells of the $W$-graph.

InduceWG(W, wg, seq): GrpFPCox, GrphUnd, SeqEnum → GrphUnd#

InduceWG(W, wg, seq): GrpFPCox, GrphDir, SeqEnum → GrphDir#: Induce a $W$-graph from a standard parabolic subgroup.

InduceWGtable(J, table, W): SeqEnum, SeqEnum, GrpFPCox → SeqEnum[SeqEnum[RngIntElt]]#: Returns the table of the $W$-graph induced from the table of a parabolic subgroup defined by $J$.

IsWGsymmetric(dwg): GrphDir → BoolElt, GrphDir#: Test a $W$-graph for symmetry. If the graph is symmetric the second return value is the undirected version of the $W$-graph.

MakeDirected(uwg): GrphUnd → GrphDir#: Convert an undirected $W$-graph to a directed $W$-graph.

TestHeckeRep(W, r): GrpFPCox, SeqEnum → .#: Tests whether the matrices in r satisfy the defining relations of the Hecke algebra of the Coxeter group $W$.

WG2GroupRep(wg): GrphUnd → SeqEnum#

WG2GroupRep(wg): GrphDir → SeqEnum#: The matrix representation of a $W$-graph.

WG2HeckeRep(W, wg): GrpFPCox, GrphUnd → SeqEnum#

WG2HeckeRep(W, wg): GrpFPCox, GrphDir → SeqEnum#: Returns a sequence of sparse matrices that satisfy the defining relations of the Hecke algebra.

WGidealgens2WGtable(dgens, K): SeqEnum, SetEnum → SeqEnum[SeqEnum[RngIntElt]], SetIndx#: Returns the $W$-graph table and $W$-graph ideal of a $W$-graph determining generators dgens and subset $K$.

Example: Wgraph Ideal#

In type $E_6$ we start with a rank 3 standard parabolic subgroup. The set of minimal coset representatives is a (single-generator) $W$-graph ideal, corresponding to the representation induced from the trivial representation of the parabolic. We compute the $W$-graph and find the cells. The bottom cell is necessarily an ideal in the weak order. It turns out that 3 elements are required to generate it; we can use them to test the function WGidealgens2WGtable.

> mij:=[1,3,1,2,3,1,2,3,2,1,2,2,2,3,1,2,2,3,2,2,1];
> E6 := CoxeterGroup(GrpFPCox, SymmetricMatrix(mij) );
> J := {1,3,5};
> drs := Transversal(E6,J);
> ttt := WGidealgens2WGtable([drs[1398],drs[156],drs[99]],J);
> nwg := WGtable2WG(ttt);
> TestWG(E6,nwg);

true <1, 2> 3
true <2, 3> 3
true <2, 4> 3
true <4, 5> 3
true <3, 6> 3

WriteWG(file, uwg): MonStgElt, GrphUnd → .#

WriteWG(file, dwg): MonStgElt, GrphDir → .#: Writes the $W$-graph to a file.

$W$-graphs

Contents

$W$-graphs#