.. _SectCartanDynDigrph:

.. _dynkindigraph:

Dynkin Digraphs
===============

A *Dynkin digraph* is a directed labelled graph describing a *crystallographic*
Cartan matrix :math:`C=(c_{ij})_{i,j=1}^n`. The Dynkin digraph has vertices
:math:`1,\dots,n`; whenever :math:`c_{ij}<0` there is an edge from :math:`i` to
:math:`j` labeled by the value :math:`-c_{ij}`. When :math:`c_{ij}=-1`, the
label is usually omitted.

In the literature, the term *Dynkin diagram* is used, but here this will be
reserved for a printed display of the Dynkin digraph (or Coxeter graph)
corresponding to a finite or affine Coxeter group (see
Section :ref:`SectCartanFinAff` below). For convenience,
Dynkin digraphs have labelled edges rather than multiple edges.

Clearly a Dynkin digraph must be standard, i.e. its vertices must be the
integers :math:`1,2,\dots,n` for some :math:`n`. A Dynkin digraph has an edge
from :math:`i` to :math:`j` if, and only if, it has an edge from :math:`j` to
:math:`i` (although the labels may be different). Hence strong and weak
connectivity are equivalent for these graphs. The Coxeter system is irreducible
if, and only if, the Dynkin digraph is connected. Two Dynkin digraphs give rise
to Cartan equivalent Cartan matrices if they are isomorphic as labelled
digraphs. See Chapter :ref:`Graph` for more information on digraphs.

Note that functions are not given for computing the Dynkin digraph of a Coxeter
matrix or Coxeter graph, since a particular choice of crystallographic Cartan
matrix is required.

.. magma:function:: IsDynkinDigraph(D)
   :input_types: GrphDir
   :output_types: BoolElt
   :label: IsDynkinDigraph_GrphDir

   Returns ``true`` if, and only if, the digraph :math:`D` is the Dynkin digraph of
   some crystallographic Cartan matrix.

.. magma:function:: DynkinDigraph(C)
   :input_types: AlgMatElt
   :output_types: GrphDir
   :label: DynkinDigraph_AlgMatElt

   The Dynkin digraph of the crystallographic Cartan matrix :math:`C`.

.. magma:function:: CoxeterGroupOrder(D)
   :input_types: GrphDir
   :output_types: .
   :label: CoxeterGroupOrder_GrphDir

.. magma:function:: CoxeterGroupFactoredOrder(D)
   :input_types: GrphDir
   :output_types: .
   :label: CoxeterGroupFactoredOrder_GrphDir

   The (factored) order of the Coxeter group with Dynkin digraph :math:`D`.

.. magma:function:: FundamentalGroup(D)
   :input_types: GrphDir
   :output_types: GrpAb
   :label: FundamentalGroup_GrphDir

   The fundamental group of the Dynkin digraph :math:`D`,
   i.e. :math:`{\mathbb{Z}}^n/\Gamma` where :math:`n` is the degree of :math:`D`
   and :math:`\Gamma` is the lattice generated by the rows of the corresponding
   Cartan matrix. The natural mapping
   :math:`{\mathbb{Z}}^n\to{\mathbb{Z}}^n/\Gamma` is the second returned value.

.. magma:function:: IsSimplyLaced(D)
   :input_types: GrphDir
   :output_types: BoolElt
   :label: IsSimplyLaced_GrphDir

   Returns ``true`` if, and only if, the Dynkin digraph :math:`D` is simply laced,
   i.e. unlabelled.

.. magma:example:: Example: Cartan Matrices
   :label: CartanMatrices

   .. code-block:: magma

      > D := Digraph< 4 | <1,{2,3,4}>, <2,{1}>, <3,{1}>, <4,{1}> >;
      > AssignLabel(D, 1,2, 2);
      > AssignLabel(D, 1,3, 5);
      > IsDynkinDigraph(D);
      true
      %%a> assert $1;
      > CartanMatrix(D);
      [ 2 -2 -5 -1]
      [-1  2  0  0]
      [-1  0  2  0]
      [-1  0  0  2]
      > FundamentalGroup(D);
      Abelian Group isomorphic to Z/2 + Z/8
      Defined on 2 generators
      Relations:
          2*$.1 = 0
          8*$.2 = 0
      Mapping from: Standard Lattice of rank 4 and degree 4 to Abelian Group
      isomorphic to Z/2 + Z/8
      Defined on 2 generators
      Relations:
          2*$.1 = 0
          8*$.2 = 0