.. _SectGrpFPCoxWgraph:

.. _group-wgraphs:

$W$-graphs
==========

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

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

.. math::

   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 :math:`\sum'` indicates the sum over all edges with terminal vertex equal
to :math:`v` for which :math:`s` is in the descent set of the initial vertex
:math:`u`, and :math:`m` is the weight of the edge.

For the Coxeter group calculations involved in these functions we need to know
how the generators :math:`s\in S` act on the set of elementary roots
(see :cite:`Brink98`).

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

``eltroots:=ReflectionTable(W);``

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

.. magma:function:: SetVerbose("WGraph", v)
   :input_types: MonStgElt, RngIntElt
   :label: SetVerbose_MonStgElt_RngIntElt

   Set the verbose printing to level :math:`v` for all :math:`W`-graph related
   functions. A level of :math:`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 :math:`M` the Coxeter matrix then

``M := SymmetricMatrix(seq);``

and

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

.. magma:function:: Mij2EltRootTable(seq)
   :input_types: SeqEnum
   :output_types: SeqEnum[SeqEnum[RngIntElt]]
   :label: Mij2EltRootTable_SeqEnum

   Return the elementary root action table for the Coxeter group defined by the
   given mij-sequence.

.. magma:function:: Name2Mij(name)
   :input_types: MonStgElt
   :output_types: SeqEnum
   :label: Name2Mij_MonStgElt

   The mij-sequence of the Coxeter groups of type name.

.. magma:example:: Example: mijseq
   :label: mijseq

   .. code-block:: magma

      > 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 :math:`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 :math:`P` is a :math:`W`-graph poset then :math:`P` must be in
one-to-one correspondence with a basis for an :math:`H`-module :math:`V` (where
:math:`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 :math:`V` as GSM(:math:`P`) (for generalized
Specht module). For each :math:`v\in P` the set :math:`S` must be the disjoint
union of two sets :math:`A(v)` and :math:`D(v)`, the ascents and descents of
:math:`v`. There must be a function :math:`(s,v) \mapsto sv` from
:math:`S \times P` to :math:`P` such that the action of :math:`H` on GSM(P)
satisfies the following rules (for all :math:`s \in S` and :math:`v \in P`):

.. math::

   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 :math:`\langle`\ earlier\ :math:`\rangle` denotes a linear combination of
:math:`\{u \in P \mid u < v\}` with coefficients that are polynomials in
:math:`q`. For each :math:`s \in
A(v)` either :math:`sv = v` or :math:`sv > v`, and for each :math:`s \in D(v)`
either :math:`sv < v` or :math:`sv = v`. This (admittedly strange) definition is
motivated by the fact that Specht modules satisfy it. If :math:`v` is a standard
tableau corresponding to a partition of :math:`n` then a number :math:`i` in
:math:`\{1,\dots,n-1\}` is an ascent of :math:`v` if :math:`i+1` is in a later
column of :math:`t` than :math:`i`, and is a descent of :math:`v` if :math:`i+1`
is in a lower row of :math:`t` than :math:`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 (:math:`sv = v` and :math:`s \in A(v)`) it
is not proved that the polynomial coefficients of :math:`\{u \in P \mid u < v\}`
are all divisible by :math:`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 :math:`W`-graph may be constructed from a :math:`W`-graph
poset, the :math:`W`-graph being uniquely determined by the function
:math:`(s,v) \mapsto sv` from :math:`S \times P \to P` and the descent/ascent
sets. The polynomial coefficients in the weak ascent case are not required. Of
course the :math:`H`-module determined by the resulting :math:`W`-graph is
isomorphic to GSM(:math:`P`).

.. magma:function:: Partition2WGtable(pi)
   :input_types: SeqEnum
   :output_types: SeqEnum, GrpFPCox
   :label: Partition2WGtable_SeqEnum

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

.. magma:function:: WGtable2WG(table)
   :input_types: SeqEnum
   :output_types: GrphUnd
   :label: WGtable2WG_SeqEnum

   Convert a :math:`W`-graph table to a :math:`W`-graph.

.. magma:function:: TestWG(W,wg)
   :input_types: GrpFPCox, GrphUnd
   :output_types: .
   :label: TestWG_GrpFPCox_GrphUnd

.. magma:function:: TestWG(W,wg)
   :input_types: GrpFPCox, GrphDir
   :output_types: .
   :label: TestWG_GrpFPCox_GrphDir

.. magma:function:: TestWG(tp,wg)
   :input_types: MonStgElt, GrphDir
   :output_types: .
   :label: TestWG_MonStgElt_GrphDir

.. magma:function:: TestWG(tp,wg)
   :input_types: MonStgElt, GrphDir
   :output_types: .
   :label: TestWG_MonStgElt_GrphDir_2

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

   For example,

.. magma:example:: Example: Specht Wgraph
   :label: SpechtWgraph

   .. code-block:: magma

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

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

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

.. magma:function:: WGelement2WGtable(g,K)
   :input_types: GrpFPCoxElt, SetEnum
   :output_types: SeqEnum, SeqEnum
   :label: WGelement2WGtable_GrpFPCoxElt_SetEnum

   Returns the :math:`W`-graph table and :math:`W`-graph ideal of a :math:`W`-graph
   determining element :math:`g`, subset :math:`K`.

.. magma:example:: Example: B5Wgraph
   :label: B5Wgraph

   .. code-block:: magma

      > 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

.. magma:function:: GetCells(wg)
   :input_types: GrphUnd
   :output_types: SeqEnum
   :label: GetCells_GrphUnd

.. magma:function:: GetCells(wg)
   :input_types: GrphDir
   :output_types: SeqEnum
   :label: GetCells_GrphDir

   Return the cells of the :math:`W`-graph.

.. magma:function:: InduceWG(W,wg,seq)
   :input_types: GrpFPCox, GrphUnd, SeqEnum
   :output_types: GrphUnd
   :label: InduceWG_GrpFPCox_GrphUnd_SeqEnum

.. magma:function:: InduceWG(W,wg,seq)
   :input_types: GrpFPCox, GrphDir, SeqEnum
   :output_types: GrphDir
   :label: InduceWG_GrpFPCox_GrphDir_SeqEnum

   Induce a :math:`W`-graph from a standard parabolic subgroup.

.. magma:function:: InduceWGtable(J, table, W)
   :input_types: SeqEnum, SeqEnum, GrpFPCox
   :output_types: SeqEnum[SeqEnum[RngIntElt]]
   :label: InduceWGtable_SeqEnum_SeqEnum_GrpFPCox

   Returns the table of the :math:`W`-graph induced from the table of a parabolic
   subgroup defined by :math:`J`.

.. magma:function:: IsWGsymmetric(dwg)
   :input_types: GrphDir
   :output_types: BoolElt, GrphDir
   :label: IsWGsymmetric_GrphDir

   Test a :math:`W`-graph for symmetry. If the graph is symmetric the second return
   value is the undirected version of the :math:`W`-graph.

.. magma:function:: MakeDirected(uwg)
   :input_types: GrphUnd
   :output_types: GrphDir
   :label: MakeDirected_GrphUnd

   Convert an undirected :math:`W`-graph to a directed :math:`W`-graph.

.. magma:function:: TestHeckeRep(W,r)
   :input_types: GrpFPCox, SeqEnum
   :output_types: .
   :label: TestHeckeRep_GrpFPCox_SeqEnum

   Tests whether the matrices in r satisfy the defining relations of the Hecke
   algebra of the Coxeter group :math:`W`.

.. magma:function:: WG2GroupRep(wg)
   :input_types: GrphUnd
   :output_types: SeqEnum
   :label: WG2GroupRep_GrphUnd

.. magma:function:: WG2GroupRep(wg)
   :input_types: GrphDir
   :output_types: SeqEnum
   :label: WG2GroupRep_GrphDir

   The matrix representation of a :math:`W`-graph.

.. magma:function:: WG2HeckeRep(W,wg)
   :input_types: GrpFPCox, GrphUnd
   :output_types: SeqEnum
   :label: WG2HeckeRep_GrpFPCox_GrphUnd

.. magma:function:: WG2HeckeRep(W,wg)
   :input_types: GrpFPCox, GrphDir
   :output_types: SeqEnum
   :label: WG2HeckeRep_GrpFPCox_GrphDir

   Returns a sequence of sparse matrices that satisfy the defining relations of the
   Hecke algebra.

.. magma:function:: WGidealgens2WGtable(dgens,K)
   :input_types: SeqEnum, SetEnum
   :output_types: SeqEnum[SeqEnum[RngIntElt]], SetIndx
   :label: WGidealgens2WGtable_SeqEnum_SetEnum

   Returns the :math:`W`-graph table and :math:`W`-graph ideal of a :math:`W`-graph
   determining generators dgens and subset :math:`K`.

.. magma:example:: Example: Wgraph Ideal
   :label: WgraphIdeal

   In type :math:`E_6` we start with a rank 3 standard parabolic subgroup. The set
   of minimal coset representatives is a (single-generator) :math:`W`-graph ideal,
   corresponding to the representation induced from the trivial representation of
   the parabolic. We compute the :math:`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``.

   .. code-block:: magma

      > 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

.. magma:function:: WriteWG(file,uwg)
   :input_types: MonStgElt, GrphUnd
   :output_types: .
   :label: WriteWG_MonStgElt_GrphUnd

.. magma:function:: WriteWG(file,dwg)
   :input_types: MonStgElt, GrphDir
   :output_types: .
   :label: WriteWG_MonStgElt_GrphDir

   Writes the :math:`W`-graph to a file.