-------------------------------------------------
Weyl Groups, Coxeter Groups and the Bruhat Order
-------------------------------------------------

Classical and affine Weyl Groups
---------------------------------

You can create Weyl groups and affine Weyl groups for any root system.
A variety of methods are available for these. Some of these are
methods are available for general Coxeter groups.

By default, elements of the Weyl group are represented as matrices::

    sage: WeylGroup("A3").simple_reflection(1)
    [0 1 0 0]
    [1 0 0 0]
    [0 0 1 0]
    [0 0 0 1]

You may prefer a notation in which elements are written out
as products of simple reflections. In order to implement this
you need to specify a prefix, typically ``"s"``::

    sage: W = WeylGroup("A3",prefix="s")
    sage: [s1,s2,s3]=W.simple_reflections()
    sage: (s1*s2*s1).length()
    3
    sage: W.long_element()
    s1*s2*s3*s1*s2*s1
    sage: s1*s2*s3*s1*s2*s1 == s3*s2*s1*s3*s2*s3
    True

The Weyl group acts on the ambient space, which is
available as a :meth:`space`. To illustrate this, recall
that if :math:`w_0` is the long element then :math:`\alpha\mapsto -w_0(\alpha)`
is a permutation of the simple roots. We may compute this
as follows::

    sage: W = WeylGroup("E6",prefix="s")
    sage: w0 = W.long_element(); w0
    s1*s3*s4*s5*s6*s2*s4*s5*s3*s4*s1*s3*s2*s4*s5*s6*s2*s4*s5*s3*s4*s1*s3*s2*s4*s5*
    s3*s4*s1*s3*s2*s4*s1*s3*s2*s1
    sage: sr = W.space().simple_roots().list(); sr
    [(1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2), (1, 1, 0, 0, 0, 0, 0, 0), 
    (-1, 1, 0, 0, 0, 0, 0, 0), (0, -1, 1, 0, 0, 0, 0, 0), (0, 0, -1, 1, 0, 0, 0, 0), 
    (0, 0, 0, -1, 1, 0, 0, 0)]
    sage: [-w0.action(a) for a in sr]
    [(0, 0, 0, -1, 1, 0, 0, 0), (1, 1, 0, 0, 0, 0, 0, 0), (0, 0, -1, 1, 0, 0, 0, 0),
    (0, -1, 1, 0, 0, 0, 0, 0), (-1, 1, 0, 0, 0, 0, 0, 0), 
    (1/2, -1/2, -1/2, -1/2, -1/2, -1/2, -1/2, 1/2)]

We may ask when this permutation is trivial. If it is nontrivial
it induces an automorphism of the Dynkin diagram, so it must
be nontrivial when the Dynkin diagram has no automorphism. But
if there is a nontrivial automorphism, the permutation might
or might not be trivial::

    sage: def roots_not_permuted(ct):
    ....:     W = WeylGroup(ct)
    ....:     w0 = W.long_element()
    ....:     sr = W.space().simple_roots()
    ....:     return all(a == -w0.action(a) for a in sr)
    ....: 
    sage: for ct in [CartanType(['D',r]) for r in [2..8]]:
    ....:    print ct,roots_not_permuted(ct)
    ....: 
    ['D', 2] True
    ['D', 3] False
    ['D', 4] True
    ['D', 5] False
    ['D', 6] True
    ['D', 7] False
    ['D', 8] True

If :math:`\alpha` is a root let :math:`r_\alpha` denote the reflection
in the hyperplane of the ambient space that is orthogonal
to :math:`\alpha`. We reserve the notation :math:`s_\alpha` for
the simple reflections, that is, the case where :math:`\alpha` is a simple
root. The reflections are just the conjugates of the simple
reflections.

The reflections are the keys in a finite family, which is a
wrapper around a python dictionary. The values are the positive
roots, so given a reflection, you can look up the corresponding root. If
you want a list of all reflections, use the method :meth:`keys` for the
family of reflections::

    sage: W = WeylGroup("B3",prefix="s")
    sage: [s1,s2,s3] = W.simple_reflections()
    sage: ref = W.reflections(); ref
    sage: Finite family {s1*s2*s1: (1, 0, -1), s2: (0, 1, -1), s3*s2*s3: (0, 1, 1), 
    s3*s1*s2*s3*s1: (1, 0, 1), s1: (1, -1, 0), s2*s3*s1*s2*s3*s1*s2: (1, 1, 0), 
    s1*s2*s3*s2*s1: (1, 0, 0), s2*s3*s2: (0, 1, 0), s3: (0, 0, 1)}
    sage: ref[s3*s2*s3]
    (0, 1, 1)
    sage: ref.keys()
    [s1*s2*s1, s2, s3*s2*s3, s2*s3*s1*s2*s3*s1*s2, s1, s3*s1*s2*s3*s1, s1*s2*s3*s2*s1, s2*s3*s2, s3]

If instead you want a dictionary whose keys are the roots and whose values are
the reflections, you may use the inverse family::

    sage: altref=W.reflections().inverse_family(); altref
    Finite family {(1, 0, 0): s1*s2*s3*s2*s1, (1, 0, 1): s3*s1*s2*s3*s1, (0, 1, 0): s2*s3*s2, 
    (0, 1, -1): s2, (1, 0, -1): s1*s2*s1, (0, 1, 1): s3*s2*s3, (1, 1, 0): s2*s3*s1*s2*s3*s1*s2,
    (0, 0, 1): s3, (1, -1, 0): s1}
    sage: [a1,a2,a3]=W.space().simple_roots()
    sage: a1+a2+a3
    (1, 0, 0)
    sage: altref[a1+a2+a3]
    s1*s2*s3*s2*s1

The Weyl group is implemented as a GAP Matrix group. You therefore
can display its character table. The character table is
returned as a string, which you can print::

    sage: print WeylGroup("D4").character_table()
    CT1
    
          2  6  4  5  1  3  5  5  4  3  3  1  4  6
          3  1  .  .  1  .  .  .  .  .  .  1  .  1
    
            1a 2a 2b 6a 4a 2c 2d 2e 4b 4c 3a 4d 2f
    
    X.1      1  1  1  1  1  1  1  1  1  1  1  1  1
    X.2      1 -1  1  1 -1  1  1 -1 -1 -1  1  1  1
    X.3      2  .  2 -1  .  2  2  .  .  . -1  2  2
    X.4      3 -1  3  . -1 -1 -1 -1  1  1  . -1  3
    X.5      3 -1 -1  .  1  3 -1 -1 -1  1  . -1  3
    X.6      3  1  3  .  1 -1 -1  1 -1 -1  . -1  3
    X.7      3  1 -1  . -1  3 -1  1  1 -1  . -1  3
    X.8      3 -1 -1  .  1 -1  3 -1  1 -1  . -1  3
    X.9      3  1 -1  . -1 -1  3  1 -1  1  . -1  3
    X.10     4 -2  . -1  .  .  .  2  .  .  1  . -4
    X.11     4  2  . -1  .  .  . -2  .  .  1  . -4
    X.12     6  . -2  .  . -2 -2  .  .  .  .  2  6
    X.13     8  .  .  1  .  .  .  .  .  . -1  . -8


Affine Weyl Groups
-------------------

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

    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

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: 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}

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

    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]

Bruhat order
------------

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

If :math:`u,v \in W`, find a reduced expression of :math:`v` into a product
of simple reflections: :math:`v=s_1\cdots s_n`. (It is not assumed
that the :math:`s_i` are distinct.) If omitting some of the :math:`s_i`
gives a product that represents :math:`u`, then :math:`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 :math:`u`, :math:`v\in W` then ``u.bruhat_le(v)`` returns true of
:math:`u\le v` in the Bruhat order.

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

    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, s1*s2, s1*s2*s1, s2*s1]

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

    sage: W.bruhat_interval(s1,s1*s2*s1)
    [s1*s2*s1, s2*s1, s1*s2, s1]

This works even for affine Weyl groups.

The Bruhat Graph
----------------

References:

- Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and
  rational smoothness of Schubert varieties, in Algebraic groups
  and their generalizations: classical methods, AMS Proc. Sympos. Pure Math., 56, 
  53--61 (1994).

- Deodhar, Vinay V., Some characterizations of Bruhat ordering on a
  Coxeter group and determination of the relative Moebius function,
  Invent. Math., 39, 1977, 2, 187--198.

- Dyer, The nil Hecke ring and Deodhar's conjecture on Bruhat intervals,
  Invent. Math., 111, 1993, 3, 571--574.

- Bump and Nakasuji, Casselman's basis of Iwahori vectors and the Bruhat order,
  http://arxiv.org/abs/1002.2996.

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

If :math:`W` is a classical Weyl group the Bruhat graph is
implemented in 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()

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
:math:`P_{u,v}` and :math:`P_{w_0v,w_0u}` are 1, where :math:`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 :math:`u<v` then the Bruhat interval
:math:`[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 :math:`r` such
that left (or right) multiplication by :math:`r` takes the
Bruhat interval :math:`[u,v]` to itself, then this gives
an explicit bijection between the elements of odd and
even length in :math:`[u,v]`.

Let us search for such reflections. Put the following
commands in a file and load or attach 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

Now inspect the output of this command::

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