|
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< q > 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 Ts of H
associated with an element s∈S on a basis element v is given by
v * Ts = cases(
( - q - 1) * v & if s is in the descent set of v,
q * v + ∑' (m * u)&if s is not in the descent set of v,
)
where ∑' 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∈S act on the set of
elementary roots (see [Bri98]).
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∈{1, ..., r} and j∈{1, ..., 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, ..., r} (corresponding
to words in S).
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∈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) |-> sv from S x P to P such that the action of H on
GSM(P) satisfies the following rules (for all s ∈S and v ∈P):
v * Ts = cases(
sv &if sv > v,
sv + (q - q - 1) * v &if sv < v,
- q - 1 * v &if sv = v and s∈D(v),
q * v + q * < earlier > &if sv = v and s ∈A(v),
)
where < earlier > denotes a linear combination of
{u ∈P | u < v}
with coefficients that are polynomials in q. For each s ∈A(v) either sv = v or sv > v, and for each s ∈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, ..., 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 ∈A(v)) it is
not proved that the polynomial coefficients of {u ∈P | 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) |-> sv from S x 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).
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∈W, let P be
the set
{x∈W | length(wx - 1) = length(w) - length(x)},
considered as a poset under the Bruhat order on W. Given also a
subset J of {t∈S | length(wt) > length(w)},
for each x∈P we define D(x) to be union of
{s∈S | length(sx) < length(x)} and
{s ∈S | sx = xt for some t ∈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 An, 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 ∈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 WK (where the set J may be
taken to be either K or the empty set).
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)]];
Return the elementary root action table for the Coxeter
group defined by the given mij-sequence.
The mij-sequence of the Coxeter groups of type name.
> 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
Returns the W-graph table and the Weyl group for the partition pi, where
pi is a nonincreasing sequence [a1, a2, ..., ak]
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 An, where n + 1 = ∑ai.
Convert a W-graph table to a W-graph.
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,
> SetVerbose("WGraph",1);
> wtable, W :=Partition2WGtable([4,4,3,1]);
> wg := WGtable2WG(wtable);
> TestWG(W,wg);
Returns the W-graph table and W-graph ideal of a W-graph
determining element g, subset K.
> 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) : GrphDir -> SeqEnum
Return the cells of the W-graph.
InduceWG(W,wg,seq) : GrpFPCox, GrphDir, SeqEnum -> GrphDir
Induce a W-graph from a standard parabolic subgroup.
Returns the table of the W-graph induced from the table of a
parabolic subgroup defined by J.
Test a W-graph for symmetry. If the graph is symmetric
the second return value is the undirected version of the
W-graph.
Convert an undirected W-graph to a directed W-graph.
Tests whether the matrices in r satisfy the defining relations of the
Hecke algebra of the Coxeter group W.
WG2GroupRep(wg) : GrphDir -> SeqEnum
The matrix representation of a W-graph.
WG2HeckeRep(W,wg) : GrpFPCox, GrphDir -> SeqEnum
Returns a sequence of sparse matrices that satisfy the
defining relations of the Hecke algebra.
Returns the W-graph table and W-graph ideal of a W-graph determining
generators dgens and subset K.
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
texttt{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,dwg) : MonStgElt, GrphDir -> .
Writes the W-graph to a file.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|