Weyl Groups, Coxeter Groups and the Bruhat Order¶

Affine Weyl groups¶

Affine Weyl groups may be created the same way. You simply begin with an affine Cartan type:

Sage

sage: W = WeylGroup(['A',2,1],prefix="s")
sage: W.cardinality()
+Infinity
sage: [s0,s1,s2] = W.simple_reflections()
sage: s0*s1*s2*s1*s0
s0*s1*s2*s1*s0

Python

>>> from sage.all import *
>>> W = WeylGroup(['A',Integer(2),Integer(1)],prefix="s")
>>> W.cardinality()
+Infinity
>>> [s0,s1,s2] = W.simple_reflections()
>>> s0*s1*s2*s1*s0
s0*s1*s2*s1*s0

Sage Live

W = WeylGroup(['A',2,1],prefix="s")
W.cardinality()
[s0,s1,s2] = W.simple_reflections()
s0*s1*s2*s1*s0

The affine Weyl group differs from a classical Weyl group since it is infinite. The associated classical Weyl group is a subgroup that may be extracted as follows:

Sage

sage: W = WeylGroup(['A',2,1],prefix="s")
sage: W1 = W.classical(); W1
Parabolic Subgroup of the Weyl Group of type ['A', 2, 1] (as a matrix group
acting on the root space)
sage: W1.simple_reflections()
Finite family {1: s1, 2: s2}

Python

>>> from sage.all import *
>>> W = WeylGroup(['A',Integer(2),Integer(1)],prefix="s")
>>> W1 = W.classical(); W1
Parabolic Subgroup of the Weyl Group of type ['A', 2, 1] (as a matrix group
acting on the root space)
>>> W1.simple_reflections()
Finite family {1: s1, 2: s2}

Sage Live

W = WeylGroup(['A',2,1],prefix="s")
W1 = W.classical(); W1
W1.simple_reflections()

Although W1 in this example is isomorphic to WeylGroup("A2") it has a different matrix realization:

Sage

sage: for s in WeylGroup(['A',2,1]).classical().simple_reflections():
....:     print(s)
....:     print("")
[ 1  0  0]
[ 1 -1  1]
[ 0  0  1]

[ 1  0  0]
[ 0  1  0]
[ 1  1 -1]

sage: for s in WeylGroup(['A',2]).simple_reflections():
....:     print(s)
....:     print("")
[0 1 0]
[1 0 0]
[0 0 1]

[1 0 0]
[0 0 1]
[0 1 0]

Python

>>> from sage.all import *
>>> for s in WeylGroup(['A',Integer(2),Integer(1)]).classical().simple_reflections():
...     print(s)
...     print("")
[ 1  0  0]
[ 1 -1  1]
[ 0  0  1]
<BLANKLINE>
[ 1  0  0]
[ 0  1  0]
[ 1  1 -1]

>>> for s in WeylGroup(['A',Integer(2)]).simple_reflections():
...     print(s)
...     print("")
[0 1 0]
[1 0 0]
[0 0 1]
<BLANKLINE>
[1 0 0]
[0 0 1]
[0 1 0]

Sage Live

for s in WeylGroup(['A',2,1]).classical().simple_reflections():
    print(s)
    print("")
for s in WeylGroup(['A',2]).simple_reflections():
    print(s)
    print("")

Bruhat order¶

The Bruhat partial order on the Weyl group may be defined as follows.

If \(u,v \in W\), find a reduced expression of \(v\) into a product of simple reflections: \(v = s_1 \cdots s_n\). (It is not assumed that the \(s_i\) are distinct.) If omitting some of the \(s_i\) gives a product that represents \(u\), then \(u \le v\).

The Bruhat order is implemented in Sage as a method of Coxeter groups, and so it is available for Weyl groups, classical or affine.

If \(u\), \(v \in W\) then u.bruhat_le(v) returns True if \(u \le v\) in the Bruhat order.

If \(u \le v\) then the Bruhat interval \([u,v]\) is defined to be the set of all \(t\) such that \(u \le t \le v\). One might try to implement this as follows:

Sage

sage: W = WeylGroup("A2",prefix="s")
sage: [s1,s2] = W.simple_reflections()
sage: def bi(u,v) : return [t for t in W if u.bruhat_le(t) and t.bruhat_le(v)]
...
sage: bi(s1,s1*s2*s1)
[s1*s2, s2*s1, s1, s1*s2*s1]

Python

>>> from sage.all import *
>>> W = WeylGroup("A2",prefix="s")
>>> [s1,s2] = W.simple_reflections()
>>> def bi(u,v) : return [t for t in W if u.bruhat_le(t) and t.bruhat_le(v)]
...
>>> bi(s1,s1*s2*s1)
[s1*s2, s2*s1, s1, s1*s2*s1]

Sage Live

W = WeylGroup("A2",prefix="s")
[s1,s2] = W.simple_reflections()
def bi(u,v) : return [t for t in W if u.bruhat_le(t) and t.bruhat_le(v)]
bi(s1,s1*s2*s1)

This would not be a good definition since it would fail if \(W\) is affine and be inefficient of \(W\) is large. Sage has a Bruhat interval method:

Sage

sage: W = WeylGroup("A2",prefix="s")
sage: [s1,s2] = W.simple_reflections()
sage: W.bruhat_interval(s1,s1*s2*s1)
[s1*s2*s1, s2*s1, s1*s2, s1]

Python

>>> from sage.all import *
>>> W = WeylGroup("A2",prefix="s")
>>> [s1,s2] = W.simple_reflections()
>>> W.bruhat_interval(s1,s1*s2*s1)
[s1*s2*s1, s2*s1, s1*s2, s1]

Sage Live

W = WeylGroup("A2",prefix="s")
[s1,s2] = W.simple_reflections()
W.bruhat_interval(s1,s1*s2*s1)

This works even for affine Weyl groups.

The Bruhat graph¶

References:

The Bruhat graph is a structure on the Bruhat interval. Suppose that \(u \le v\). The vertices of the graph are \(x\) with \(u \le x \le v\). There is a vertex connecting \(x,y \in [x,y]\) if \(x = y \cdot r\) where \(r\) is a reflection. If this is true then either \(x < y\) or \(y < x\).

If \(W\) is a classical Weyl group the Bruhat graph is implemented in Sage:

Sage

sage: W = WeylGroup("A3",prefix="s")
sage: [s1,s2,s3] = W.simple_reflections()
sage: bg = W.bruhat_graph(s2,s2*s1*s3*s2); bg
Digraph on 10 vertices
sage: bg.show3d()

Python

>>> from sage.all import *
>>> W = WeylGroup("A3",prefix="s")
>>> [s1,s2,s3] = W.simple_reflections()
>>> bg = W.bruhat_graph(s2,s2*s1*s3*s2); bg
Digraph on 10 vertices
>>> bg.show3d()

Sage Live

W = WeylGroup("A3",prefix="s")
[s1,s2,s3] = W.simple_reflections()
bg = W.bruhat_graph(s2,s2*s1*s3*s2); bg
bg.show3d()

The Bruhat graph has interesting regularity properties that were investigated by Carrell and Peterson. It is a regular graph if both the Kazhdan Lusztig polynomials \(P_{u,v}\) and \(P_{w_0v,w_0u}\) are 1, where \(w_0\) is the long Weyl group element. It is closely related to the Deodhar conjecture, which was proved by Deodhar, Carrell and Peterson, Dyer and Polo.

Deodhar proved that if \(u < v\) then the Bruhat interval \([u,v]\) contains as many elements of odd length as it does of even length. We observe that often this can be strengthened: If there exists a reflection \(r\) such that left (or right) multiplication by \(r\) takes the Bruhat interval \([u,v]\) to itself, then this gives an explicit bijection between the elements of odd and even length in \([u,v]\).

Let us search for such reflections. Put the following commands in a file and load the file:

W = WeylGroup("A3",prefix="s")
[s1,s2,s3] = W.simple_reflections()
ref = W.reflections().keys()

def find_reflection(u,v):
    bi = W.bruhat_interval(u,v)
    ret = []
    for r in ref:
        if all( r*x in bi for x in bi):
            ret.append(r)
    return ret

for v in W:
    for u in W.bruhat_interval(1,v):
        if u != v:
            print((u,v,find_reflection(u,v)))

This shows that the Bruhat interval is stabilized by a reflection for all pairs \((u,v)\) with \(u < v\) except the following two: \(s_3s_1,s_1s_2s_3s_2s_1\) and \(s_2,s_2s_3s_1s_2\). Now these are precisely the pairs such that \(u\prec v\) in the notation of Kazhdan and Lusztig, and \(l(v)-l(u) > 1\). One should not rashly suppose that this is a general characterization of the pairs \((u,v)\) such that no reflection stabilizes the Bruhat interval, for this is not true. However it does suggest that the question is worthy of further investigation.

Weyl Groups, Coxeter Groups and the Bruhat Order¶

Classical and affine Weyl groups¶

Affine Weyl groups¶

Bruhat order¶

The Bruhat graph¶