Weyl Groups
===========

The mutation matrices :math:`M_0, M_1, \ldots, M_{n-1}` generate a group
under matrix multiplication: the **Weyl group** :math:`W`. This section
describes the general theory and illustrates it for every Dynkin type.

1. General properties
----------------------

Every Weyl group is determined by its mutation matrices, which satisfy three
types of relations.

**Involutions.** Each generator is its own inverse:

.. math::

   M_k^2 = I \qquad \text{for all } k

This is because the mutation rule is self-reversing: mutating the same node
twice restores the original vector.

**Commutation.** If nodes :math:`i` and :math:`j` are **not connected** by
any edge in the Dynkin diagram, then their mutations commute:

.. math::

   M_i M_j = M_j M_i \qquad \text{(equivalently, } (M_i M_j)^2 = I\text{)}

This is because mutating at node :math:`i` only changes the :math:`i`-th
component, and the formula for that component involves only the neighbors of
:math:`i`. If :math:`j` is not a neighbor, the two mutations don't interfere.

**Braid relations.** If nodes :math:`i` and :math:`j` are connected by
:math:`m` edges (counting multiplicity, in either direction), then:

.. math::

   (M_i M_j)^{m_{ij}} = I

where the order :math:`m_{ij}` depends on the edge type:

.. list-table::
   :header-rows: 1

   * - Edge type
     - Adjacency
     - Order of :math:`M_i M_j`
     - Appears in
   * - No edge
     - :math:`A_{ij} = A_{ji} = 0`
     - 2 (commuting)
     - Non-adjacent nodes
   * - Simple edge
     - :math:`A_{ij} = A_{ji} = 1`
     - 3
     - ADE types
   * - Double edge (2,1)
     - :math:`A_{ij} = 2, A_{ji} = 1`
     - 4
     - B, C, F\ :sub:`4`
   * - Triple edge (3,1)
     - :math:`A_{ij} = 3, A_{ji} = 1`
     - 6
     - G\ :sub:`2`

These three sets of relations (involutions, commutations, braids) are a
**complete presentation** of the Weyl group. That is, :math:`W` is the
largest group generated by :math:`n` involutions satisfying these relations,
and nothing more.

**The Coxeter element.** The product of all generators in order,

.. math::

   c = M_0 \, M_1 \, M_2 \cdots M_{n-1}

is called the **Coxeter element**. Its order :math:`h` is the **Coxeter
number**, an important invariant that satisfies:

.. math::

   |\Phi^+| = \frac{n \cdot h}{2}

where :math:`|\Phi^+|` is the number of positive roots and :math:`n` is the
number of nodes (rank).

2. Summary table
-----------------

.. list-table::
   :header-rows: 1
   :widths: 8 8 10 10 12 20

   * - Type
     - Rank :math:`n`
     - :math:`|\Phi^+|`
     - :math:`h`
     - :math:`|W|`
     - :math:`W` isomorphic to
   * - :math:`A_n`
     - :math:`n`
     - :math:`\frac{n(n+1)}{2}`
     - :math:`n + 1`
     - :math:`(n+1)!`
     - :math:`S_{n+1}` (symmetric group)
   * - :math:`D_n`
     - :math:`n`
     - :math:`n(n-1)`
     - :math:`2(n-1)`
     - :math:`2^{n-1} \cdot n!`
     - :math:`(\mathbb{Z}/2)^{n-1} \rtimes S_n`
   * - :math:`E_6`
     - 6
     - 36
     - 12
     - 51,840
     - :math:`O^-(6, \mathbb{F}_2)`
   * - :math:`E_7`
     - 7
     - 63
     - 18
     - 2,903,040
     - :math:`Sp(6, \mathbb{F}_2) \times \mathbb{Z}/2`
   * - :math:`E_8`
     - 8
     - 120
     - 30
     - 696,729,600
     - :math:`O^+(8, \mathbb{F}_2)`
   * - :math:`B_n`
     - :math:`n`
     - :math:`n^2`
     - :math:`2n`
     - :math:`2^n \cdot n!`
     - Signed permutations (hyperoctahedral)
   * - :math:`C_n`
     - :math:`n`
     - :math:`n^2`
     - :math:`2n`
     - :math:`2^n \cdot n!`
     - Same as :math:`B_n`
   * - :math:`F_4`
     - 4
     - 24
     - 12
     - 1,152
     - :math:`(\mathbb{Z}/2)^4 \rtimes S_4` (with extra relations)
   * - :math:`G_2`
     - 2
     - 6
     - 6
     - 12
     - Dihedral group :math:`D_6`

Note that :math:`B_n` and :math:`C_n` have the **same** Weyl group despite
having different root systems. This is because the Weyl group depends only on
the angles between simple roots (the pairwise orders), not on their lengths.

3. Worked examples
-------------------

A\ :sub:`2`\ : the symmetric group S\ :sub:`3`
"""""""""""""""""""""""""""""""""""""""""""""""""

.. code-block:: pycon

   >>> from mutation_game import MutationGame
   >>> import numpy as np
   >>> game = MutationGame.from_dynkin("A2")

   >>> # Two generators
   >>> print("M_0 ="); print(game.mutation_matrix(0))
   M_0 =
   [[-1  1]
    [ 0  1]]
   >>> print("M_1 ="); print(game.mutation_matrix(1))
   M_1 =
   [[ 1  0]
    [ 1 -1]]

   >>> # Braid relation: (M_0 M_1)^3 = I
   >>> prod = game.mutation_matrix(0) @ game.mutation_matrix(1)
   >>> print("(M_0 M_1)^3 ="); print(np.linalg.matrix_power(prod, 3))
   (M_0 M_1)^3 =
   [[1 0]
    [0 1]]

The Weyl group :math:`W(A_2) \cong S_3` has 6 elements. We can list them all:

.. code-block:: pycon

   >>> # All 6 elements: I, M_0, M_1, M_0 M_1, M_1 M_0, M_0 M_1 M_0
   >>> M0, M1 = game.mutation_matrix(0), game.mutation_matrix(1)
   >>> I = np.eye(2, dtype=int)
   >>> elements = [I, M0, M1, M0 @ M1, M1 @ M0, M0 @ M1 @ M0]
   >>> print(f"  |W(A2)| = {len(elements)}")
     |W(A2)| = 6

These correspond to the 6 permutations of :math:`\{1, 2, 3\}`: the identity,
two transpositions :math:`(12)` and :math:`(23)`, two 3-cycles
:math:`(123)` and :math:`(132)`, and the transposition :math:`(13)`.

G\ :sub:`2`\ : the dihedral group D\ :sub:`6`
"""""""""""""""""""""""""""""""""""""""""""""""

.. code-block:: pycon

   >>> game = MutationGame.from_dynkin("G2")
   >>> M0, M1 = game.mutation_matrix(0), game.mutation_matrix(1)

   >>> # Triple edge => order 6
   >>> prod = M0 @ M1
   >>> P = np.eye(2, dtype=int)
   >>> for k in range(1, 10):
   ...     P = P @ prod
   ...     if np.allclose(P, np.eye(2)):
   ...         print(f"  (M_0 M_1)^{k} = I")
   ...         break
     (M_0 M_1)^6 = I

   >>> # Coxeter number
   >>> print(f"  Coxeter number h = 6")
   >>> print(f"  |W(G2)| = 2h = 12")
     Coxeter number h = 6
     |W(G2)| = 2h = 12

:math:`W(G_2)` is the dihedral group :math:`D_6` — the symmetry group of a
regular hexagon (6 rotations + 6 reflections). The Coxeter element acts as a
60-degree rotation.

F\ :sub:`4`\ : generators, relations, and Coxeter element
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""

.. code-block:: pycon

   >>> game = MutationGame.from_dynkin("F4")

   >>> # The four generators
   >>> for k in range(4):
   ...     print(f"M_{k} ="); print(game.mutation_matrix(k))
   M_0 =
   [[-1  1  0  0]
    [ 0  1  0  0]
    [ 0  0  1  0]
    [ 0  0  0  1]]
   M_1 =
   [[ 1  0  0  0]
    [ 1 -1  1  0]
    [ 0  0  1  0]
    [ 0  0  0  1]]
   M_2 =
   [[ 1  0  0  0]
    [ 0  1  0  0]
    [ 0  2 -1  1]
    [ 0  0  0  1]]
   M_3 =
   [[ 1  0  0  0]
    [ 0  1  0  0]
    [ 0  0  1  0]
    [ 0  0  1 -1]]

Note :math:`M_2` has a ``2`` in its replaced row — this comes from the double
edge (two incoming edges from node 1 to node 2).

.. code-block:: pycon

   >>> # Pairwise orders reveal the Dynkin diagram structure
   >>> for i in range(4):
   ...     for j in range(i+1, 4):
   ...         prod = game.mutation_matrix(i) @ game.mutation_matrix(j)
   ...         P = np.eye(4, dtype=int)
   ...         for order in range(1, 20):
   ...             P = P @ prod
   ...             if np.allclose(P, np.eye(4)):
   ...                 print(f"  (M_{i} M_{j})^{order} = I")
   ...                 break
     (M_0 M_1)^3 = I
     (M_0 M_2)^2 = I
     (M_0 M_3)^2 = I
     (M_1 M_2)^4 = I
     (M_1 M_3)^2 = I
     (M_2 M_3)^3 = I

Reading off the orders: 3 (simple edge 0-1), 4 (double edge 1-2), 3 (simple
edge 2-3), and 2 for all non-adjacent pairs. This recovers the :math:`F_4`
Dynkin diagram.

.. code-block:: pycon

   >>> # Coxeter element and Coxeter number
   >>> C = np.eye(4, dtype=int)
   >>> for k in range(4):
   ...     C = C @ game.mutation_matrix(k)
   >>> print("Coxeter element ="); print(C)
   Coxeter element =
   [[ 0  1  0 -1]
    [ 1  1  0 -1]
    [ 0  2  0 -1]
    [ 0  0  1 -1]]

   >>> P = np.eye(4, dtype=int)
   >>> for h in range(1, 30):
   ...     P = P @ C
   ...     if np.allclose(P, np.eye(4)):
   ...         print(f"  Coxeter number h = {h}")
   ...         break
     Coxeter number h = 12

   >>> # Verify: |Phi+| = n*h/2
   >>> roots = game.calculate_roots()
   >>> pos = [r for r in roots if all(v >= 0 for v in r)]
   >>> print(f"  n*h/2 = {4*12//2}, |Phi+| = {len(pos)}")
     n*h/2 = 24, |Phi+| = 24

D\ :sub:`4`\ : triality
"""""""""""""""""""""""""

:math:`D_4` is special because it has a **triality symmetry** — the three
outer nodes (0, 2, 3) are interchangeable.

.. code-block:: pycon

   >>> game = MutationGame.from_dynkin("D4")

   >>> # Pairwise orders
   >>> for i in range(4):
   ...     for j in range(i+1, 4):
   ...         prod = game.mutation_matrix(i) @ game.mutation_matrix(j)
   ...         P = np.eye(4, dtype=int)
   ...         for order in range(1, 20):
   ...             P = P @ prod
   ...             if np.allclose(P, np.eye(4)):
   ...                 print(f"  (M_{i} M_{j})^{order} = I")
   ...                 break
     (M_0 M_1)^3 = I
     (M_0 M_2)^2 = I
     (M_0 M_3)^2 = I
     (M_1 M_2)^3 = I
     (M_1 M_3)^3 = I
     (M_2 M_3)^2 = I

Node 1 is connected to all three outer nodes (0, 2, 3) by simple edges, while
the outer nodes commute with each other. The Weyl group has order
:math:`2^3 \cdot 4! = 192`.

.. code-block:: pycon

   >>> # Coxeter number
   >>> C = np.eye(4, dtype=int)
   >>> for k in range(4):
   ...     C = C @ game.mutation_matrix(k)
   >>> P = np.eye(4, dtype=int)
   >>> for h in range(1, 30):
   ...     P = P @ C
   ...     if np.allclose(P, np.eye(4)):
   ...         print(f"  Coxeter number h = {h}")
   ...         break
     Coxeter number h = 6

4. Recovering the Dynkin diagram from the Weyl group
-----------------------------------------------------

A remarkable fact: you can recover the Dynkin diagram **entirely** from the
pairwise orders of the generators. The recipe is:

1. Compute :math:`(M_i M_j)^k` for increasing :math:`k` until you reach
   the identity
2. Record the order :math:`m_{ij}` for each pair
3. Draw an edge between nodes :math:`i` and :math:`j` if
   :math:`m_{ij} > 2`:

   - :math:`m_{ij} = 3`: simple edge
   - :math:`m_{ij} = 4`: double edge
   - :math:`m_{ij} = 6`: triple edge

.. code-block:: pycon

   >>> from mutation_game import MutationGame
   >>> import numpy as np

   >>> # Mystery graph: what type is it?
   >>> game = MutationGame.from_dynkin("E6")
   >>> n = game.num_nodes
   >>> print("Pairwise orders:")
   >>> for i in range(n):
   ...     for j in range(i+1, n):
   ...         prod = game.mutation_matrix(i) @ game.mutation_matrix(j)
   ...         P = np.eye(n, dtype=int)
   ...         for order in range(1, 20):
   ...             P = P @ prod
   ...             if np.allclose(P, np.eye(n)):
   ...                 if order > 2:
   ...                     print(f"  nodes {i}-{j}: order {order} => edge")
   ...                 break
   Pairwise orders:
     nodes 0-1: order 3 => edge
     nodes 1-2: order 3 => edge
     nodes 2-3: order 3 => edge
     nodes 2-5: order 3 => edge
     nodes 3-4: order 3 => edge

This recovers the :math:`E_6` diagram: a chain ``0-1-2-3-4`` with a branch
at node 2 connecting to node 5.