---
title: "$W$-graphs"
canonical: "https://docs.magma-maths.org/v2.30-1/LieTheory/CoxeterGroups/group-wgraphs.html"
source: "https://docs.magma-maths.org/v2.30-1/LieTheory/CoxeterGroups/group-wgraphs.md"
part: "Lie Theory"
chapter: "Coxeter Groups"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Lie Theory", "source": "https://docs.magma-maths.org/v2.30-1/LieTheory/index-lie-theory.md"}
  - {"title": "Coxeter Groups", "source": "https://docs.magma-maths.org/v2.30-1/LieTheory/CoxeterGroups/index-coxeter-groups.md"}
prev: {"title": "Braid Groups", "source": "https://docs.magma-maths.org/v2.30-1/LieTheory/CoxeterGroups/group-braid.md"}
next: {"title": "Related Structures", "source": "https://docs.magma-maths.org/v2.30-1/LieTheory/CoxeterGroups/related.md"}
intrinsics:
  - {"name": "SetVerbose", "signature": "SetVerbose(\"WGraph\", v): MonStgElt, RngIntElt"}
  - {"name": "Mij2EltRootTable", "signature": "Mij2EltRootTable(seq): SeqEnum -> SeqEnum[SeqEnum[RngIntElt]]"}
  - {"name": "Name2Mij", "signature": "Name2Mij(name): MonStgElt -> SeqEnum"}
  - {"name": "Partition2WGtable", "signature": "Partition2WGtable(pi): SeqEnum -> SeqEnum, GrpFPCox"}
  - {"name": "WGtable2WG", "signature": "WGtable2WG(table): SeqEnum -> GrphUnd"}
  - {"name": "TestWG", "signature": "TestWG(W, wg): GrpFPCox, GrphUnd -> ."}
  - {"name": "TestWG", "signature": "TestWG(W, wg): GrpFPCox, GrphDir -> ."}
  - {"name": "TestWG", "signature": "TestWG(tp, wg): MonStgElt, GrphDir -> ."}
  - {"name": "TestWG", "signature": "TestWG(tp, wg): MonStgElt, GrphDir -> ."}
  - {"name": "WGelement2WGtable", "signature": "WGelement2WGtable(g, K): GrpFPCoxElt, SetEnum -> SeqEnum, SeqEnum"}
  - {"name": "GetCells", "signature": "GetCells(wg): GrphUnd -> SeqEnum"}
  - {"name": "GetCells", "signature": "GetCells(wg): GrphDir -> SeqEnum"}
  - {"name": "InduceWG", "signature": "InduceWG(W, wg, seq): GrpFPCox, GrphUnd, SeqEnum -> GrphUnd"}
  - {"name": "InduceWG", "signature": "InduceWG(W, wg, seq): GrpFPCox, GrphDir, SeqEnum -> GrphDir"}
  - {"name": "InduceWGtable", "signature": "InduceWGtable(J, table, W): SeqEnum, SeqEnum, GrpFPCox -> SeqEnum[SeqEnum[RngIntElt]]"}
  - {"name": "IsWGsymmetric", "signature": "IsWGsymmetric(dwg): GrphDir -> BoolElt, GrphDir"}
  - {"name": "MakeDirected", "signature": "MakeDirected(uwg): GrphUnd -> GrphDir"}
  - {"name": "TestHeckeRep", "signature": "TestHeckeRep(W, r): GrpFPCox, SeqEnum -> ."}
  - {"name": "WG2GroupRep", "signature": "WG2GroupRep(wg): GrphUnd -> SeqEnum"}
  - {"name": "WG2GroupRep", "signature": "WG2GroupRep(wg): GrphDir -> SeqEnum"}
  - {"name": "WG2HeckeRep", "signature": "WG2HeckeRep(W, wg): GrpFPCox, GrphUnd -> SeqEnum"}
  - {"name": "WG2HeckeRep", "signature": "WG2HeckeRep(W, wg): GrpFPCox, GrphDir -> SeqEnum"}
  - {"name": "WGidealgens2WGtable", "signature": "WGidealgens2WGtable(dgens, K): SeqEnum, SetEnum -> SeqEnum[SeqEnum[RngIntElt]], SetIndx"}
  - {"name": "WriteWG", "signature": "WriteWG(file, uwg): MonStgElt, GrphUnd -> ."}
  - {"name": "WriteWG", "signature": "WriteWG(file, dwg): MonStgElt, GrphDir -> ."}
examples:
  - "ex-320506"
  - "ex-8afb5c"
  - "ex-0bb421"
  - "ex-8bb5d1"
---

<a id="group-wgraphs"></a>
<a id="sectgrpfpcoxwgraph"></a>
# $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$,\\
    q*v + \sum' (m*u)&if $s$ is not in the descent set of $v$,\\}
$$

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 [[Bri98](https://docs.magma-maths.org/v2.30-1/references.md#cite-brink98)]).

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$).

<a id="procedure-setverbose-monstgelt-rngintelt-wgraph"></a>
## `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)]];`

<a id="function-mij2eltroottable-seqenum"></a>
## `Mij2EltRootTable(seq): SeqEnum -> SeqEnum[SeqEnum[RngIntElt]]`

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

<a id="function-name2mij-monstgelt"></a>
## `Name2Mij(name): MonStgElt -> SeqEnum`

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

<a id="example-ex-320506"></a>
## `Example: Reflection Table from Coxeter Matrix Entries (ex-320506)`

```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 $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$,\\
  sv + (q-q^{-1})*v    &if $sv < v$,\\
  -q^{-1}*v            &if $sv = v$ and $s\in D(v)$,\\
  q*v + q*\langle\hbox{earlier}\rangle &if $sv = v$ and $s \in A(v)$,\\}
$$

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$).

<a id="function-partition2wgtable-seqenum"></a>
## `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$.

<a id="function-wgtable2wg-seqenum"></a>
## `WGtable2WG(table): SeqEnum -> GrphUnd`

Convert a $W$-graph table to a $W$-graph.

<a id="function-testwg-grpfpcox-grphund"></a>
## `TestWG(W, wg): GrpFPCox, GrphUnd -> .`

<a id="function-testwg-grpfpcox-grphdir"></a>
## `TestWG(W, wg): GrpFPCox, GrphDir -> .`

<a id="function-testwg-monstgelt-grphdir"></a>
## `TestWG(tp, wg): MonStgElt, GrphDir -> .`

<a id="function-testwg-monstgelt-grphdir-2"></a>
## `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,

<a id="example-ex-8afb5c"></a>
## `Example: W-Graph of a Specht Module (ex-8afb5c)`

```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 $(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).

<a id="function-wgelement2wgtable-grpfpcoxelt-setenum"></a>
## `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$.

<a id="example-ex-0bb421"></a>
## `Example: W-Graph of Type B5 (ex-0bb421)`

```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
```

<a id="function-getcells-grphund"></a>
## `GetCells(wg): GrphUnd -> SeqEnum`

<a id="function-getcells-grphdir"></a>
## `GetCells(wg): GrphDir -> SeqEnum`

Return the cells of the $W$-graph.

<a id="function-inducewg-grpfpcox-grphund-seqenum"></a>
## `InduceWG(W, wg, seq): GrpFPCox, GrphUnd, SeqEnum -> GrphUnd`

<a id="function-inducewg-grpfpcox-grphdir-seqenum"></a>
## `InduceWG(W, wg, seq): GrpFPCox, GrphDir, SeqEnum -> GrphDir`

Induce a $W$-graph from a standard parabolic subgroup.

<a id="function-inducewgtable-seqenum-seqenum-grpfpcox"></a>
## `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$.

<a id="function-iswgsymmetric-grphdir"></a>
## `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.

<a id="function-makedirected-grphund"></a>
## `MakeDirected(uwg): GrphUnd -> GrphDir`

Convert an undirected $W$-graph to a directed $W$-graph.

<a id="function-testheckerep-grpfpcox-seqenum"></a>
## `TestHeckeRep(W, r): GrpFPCox, SeqEnum -> .`

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

<a id="function-wg2grouprep-grphund"></a>
## `WG2GroupRep(wg): GrphUnd -> SeqEnum`

<a id="function-wg2grouprep-grphdir"></a>
## `WG2GroupRep(wg): GrphDir -> SeqEnum`

The matrix representation of a $W$-graph.

<a id="function-wg2heckerep-grpfpcox-grphund"></a>
## `WG2HeckeRep(W, wg): GrpFPCox, GrphUnd -> SeqEnum`

<a id="function-wg2heckerep-grpfpcox-grphdir"></a>
## `WG2HeckeRep(W, wg): GrpFPCox, GrphDir -> SeqEnum`

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

<a id="function-wgidealgens2wgtable-seqenum-setenum"></a>
## `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$.

<a id="example-ex-8bb5d1"></a>
## `Example: W-Graph Ideal in Type E6 (ex-8bb5d1)`

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`.

```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
```

<a id="function-writewg-monstgelt-grphund"></a>
## `WriteWG(file, uwg): MonStgElt, GrphUnd -> .`

<a id="function-writewg-monstgelt-grphdir"></a>
## `WriteWG(file, dwg): MonStgElt, GrphDir -> .`

Writes the $W$-graph to a file.
