Dynkin diagrams#

AUTHORS:

  • Travis Scrimshaw (2012-04-22): Nicolas M. Thiery moved Cartan matrix creation to here and I cached results for speed.

  • Travis Scrimshaw (2013-06-11): Changed inputs of Dynkin diagrams to handle other Dynkin diagrams and graphs. Implemented remaining Cartan type methods.

  • Christian Stump, Travis Scrimshaw (2013-04-11): Added Cartan matrix as possible input for Dynkin diagrams.

sage.combinat.root_system.dynkin_diagram.DynkinDiagram(*args, **kwds)[source]#

Return the Dynkin diagram corresponding to the input.

INPUT:

The input can be one of the following:

  • empty to obtain an empty Dynkin diagram

  • a Cartan type

  • a Cartan matrix

  • a Cartan matrix and an indexing set

One can also input an indexing set by passing a tuple using the optional argument index_set.

The edge multiplicities are encoded as edge labels. For the corresponding Cartan matrices, this uses the convention in Hong and Kang, Kac, Fulton and Harris, and crystals. This is the opposite convention in Bourbaki and Wikipedia’s Dynkin diagram (Wikipedia article Dynkin_diagram). That is for \(i \neq j\):

i <--k-- j <==> a_ij = -k
           <==> -scalar(coroot[i], root[j]) = k
           <==> multiple arrows point from the longer root
                to the shorter one

For example, in type \(C_2\), we have:

sage: C2 = DynkinDiagram(['C',2]); C2
O=<=O
1   2
C2
sage: C2.cartan_matrix()
[ 2 -2]
[-1  2]

>>> from sage.all import *
>>> C2 = DynkinDiagram(['C',Integer(2)]); C2
O=<=O
1   2
C2
>>> C2.cartan_matrix()
[ 2 -2]
[-1  2]

However Bourbaki would have the Cartan matrix as:

\[\begin{split}\begin{bmatrix} 2 & -1 \\ -2 & 2 \end{bmatrix}.\end{split}\]

EXAMPLES:

sage: DynkinDiagram(['A', 4])
O---O---O---O
1   2   3   4
A4

sage: DynkinDiagram(['A',1],['A',1])
O
1
O
2
A1xA1

sage: R = RootSystem("A2xB2xF4")
sage: DynkinDiagram(R)
O---O
1   2
O=>=O
3   4
O---O=>=O---O
5   6   7   8
A2xB2xF4

sage: R = RootSystem("A2xB2xF4")
sage: CM = R.cartan_matrix(); CM
[ 2 -1| 0  0| 0  0  0  0]
[-1  2| 0  0| 0  0  0  0]
[-----+-----+-----------]
[ 0  0| 2 -1| 0  0  0  0]
[ 0  0|-2  2| 0  0  0  0]
[-----+-----+-----------]
[ 0  0| 0  0| 2 -1  0  0]
[ 0  0| 0  0|-1  2 -1  0]
[ 0  0| 0  0| 0 -2  2 -1]
[ 0  0| 0  0| 0  0 -1  2]
sage: DD = DynkinDiagram(CM); DD
O---O
1   2
O=>=O
3   4
O---O=>=O---O
5   6   7   8
A2xB2xF4
sage: DD.cartan_matrix()
[ 2 -1  0  0  0  0  0  0]
[-1  2  0  0  0  0  0  0]
[ 0  0  2 -1  0  0  0  0]
[ 0  0 -2  2  0  0  0  0]
[ 0  0  0  0  2 -1  0  0]
[ 0  0  0  0 -1  2 -1  0]
[ 0  0  0  0  0 -2  2 -1]
[ 0  0  0  0  0  0 -1  2]

>>> from sage.all import *
>>> DynkinDiagram(['A', Integer(4)])
O---O---O---O
1   2   3   4
A4

>>> DynkinDiagram(['A',Integer(1)],['A',Integer(1)])
O
1
O
2
A1xA1

>>> R = RootSystem("A2xB2xF4")
>>> DynkinDiagram(R)
O---O
1   2
O=>=O
3   4
O---O=>=O---O
5   6   7   8
A2xB2xF4

>>> R = RootSystem("A2xB2xF4")
>>> CM = R.cartan_matrix(); CM
[ 2 -1| 0  0| 0  0  0  0]
[-1  2| 0  0| 0  0  0  0]
[-----+-----+-----------]
[ 0  0| 2 -1| 0  0  0  0]
[ 0  0|-2  2| 0  0  0  0]
[-----+-----+-----------]
[ 0  0| 0  0| 2 -1  0  0]
[ 0  0| 0  0|-1  2 -1  0]
[ 0  0| 0  0| 0 -2  2 -1]
[ 0  0| 0  0| 0  0 -1  2]
>>> DD = DynkinDiagram(CM); DD
O---O
1   2
O=>=O
3   4
O---O=>=O---O
5   6   7   8
A2xB2xF4
>>> DD.cartan_matrix()
[ 2 -1  0  0  0  0  0  0]
[-1  2  0  0  0  0  0  0]
[ 0  0  2 -1  0  0  0  0]
[ 0  0 -2  2  0  0  0  0]
[ 0  0  0  0  2 -1  0  0]
[ 0  0  0  0 -1  2 -1  0]
[ 0  0  0  0  0 -2  2 -1]
[ 0  0  0  0  0  0 -1  2]

We can also create Dynkin diagrams from arbitrary Cartan matrices:

sage: C = CartanMatrix([[2, -3], [-4, 2]])
sage: DynkinDiagram(C)
Dynkin diagram of rank 2
sage: C.index_set()
(0, 1)
sage: CI = CartanMatrix([[2, -3], [-4, 2]], [3, 5])
sage: DI = DynkinDiagram(CI)
sage: DI.index_set()
(3, 5)
sage: CII = CartanMatrix([[2, -3], [-4, 2]])
sage: DII = DynkinDiagram(CII, ('y', 'x'))
sage: DII.index_set()
('x', 'y')

>>> from sage.all import *
>>> C = CartanMatrix([[Integer(2), -Integer(3)], [-Integer(4), Integer(2)]])
>>> DynkinDiagram(C)
Dynkin diagram of rank 2
>>> C.index_set()
(0, 1)
>>> CI = CartanMatrix([[Integer(2), -Integer(3)], [-Integer(4), Integer(2)]], [Integer(3), Integer(5)])
>>> DI = DynkinDiagram(CI)
>>> DI.index_set()
(3, 5)
>>> CII = CartanMatrix([[Integer(2), -Integer(3)], [-Integer(4), Integer(2)]])
>>> DII = DynkinDiagram(CII, ('y', 'x'))
>>> DII.index_set()
('x', 'y')

See also

CartanType() for a general discussion on Cartan types and in particular node labeling conventions.

class sage.combinat.root_system.dynkin_diagram.DynkinDiagram_class(t=None, index_set=None, odd_isotropic_roots=[], **options)[source]#

Bases: DiGraph, CartanType_abstract

A Dynkin diagram.

See also

DynkinDiagram()

INPUT:

  • t – a Cartan type, Cartan matrix, or None

EXAMPLES:

sage: DynkinDiagram(['A', 3])
O---O---O
1   2   3
A3
sage: C = CartanMatrix([[2, -3], [-4, 2]])
sage: DynkinDiagram(C)
Dynkin diagram of rank 2
sage: C.dynkin_diagram().cartan_matrix() == C
True

>>> from sage.all import *
>>> DynkinDiagram(['A', Integer(3)])
O---O---O
1   2   3
A3
>>> C = CartanMatrix([[Integer(2), -Integer(3)], [-Integer(4), Integer(2)]])
>>> DynkinDiagram(C)
Dynkin diagram of rank 2
>>> C.dynkin_diagram().cartan_matrix() == C
True
add_edge(i, j, label=1)[source]#

EXAMPLES:

sage: from sage.combinat.root_system.dynkin_diagram import DynkinDiagram_class
sage: d = DynkinDiagram_class(CartanType(['A',3]))
sage: sorted(d.edges(sort=True))
[]
sage: d.add_edge(2, 3)
sage: sorted(d.edges(sort=True))
[(2, 3, 1), (3, 2, 1)]

>>> from sage.all import *
>>> from sage.combinat.root_system.dynkin_diagram import DynkinDiagram_class
>>> d = DynkinDiagram_class(CartanType(['A',Integer(3)]))
>>> sorted(d.edges(sort=True))
[]
>>> d.add_edge(Integer(2), Integer(3))
>>> sorted(d.edges(sort=True))
[(2, 3, 1), (3, 2, 1)]
static an_instance()[source]#

Returns an example of Dynkin diagram

EXAMPLES:

sage: from sage.combinat.root_system.dynkin_diagram import DynkinDiagram_class
sage: g = DynkinDiagram_class.an_instance()
sage: g
Dynkin diagram of rank 3
sage: g.cartan_matrix()
[ 2 -1 -1]
[-2  2 -1]
[-1 -1  2]

>>> from sage.all import *
>>> from sage.combinat.root_system.dynkin_diagram import DynkinDiagram_class
>>> g = DynkinDiagram_class.an_instance()
>>> g
Dynkin diagram of rank 3
>>> g.cartan_matrix()
[ 2 -1 -1]
[-2  2 -1]
[-1 -1  2]
cartan_matrix()[source]#

Returns the Cartan matrix for this Dynkin diagram

EXAMPLES:

sage: DynkinDiagram(['C',3]).cartan_matrix()
[ 2 -1  0]
[-1  2 -2]
[ 0 -1  2]

>>> from sage.all import *
>>> DynkinDiagram(['C',Integer(3)]).cartan_matrix()
[ 2 -1  0]
[-1  2 -2]
[ 0 -1  2]
cartan_type()[source]#

EXAMPLES:

sage: DynkinDiagram("A2","B2","F4").cartan_type()
A2xB2xF4

>>> from sage.all import *
>>> DynkinDiagram("A2","B2","F4").cartan_type()
A2xB2xF4
column(j)[source]#

Returns the \(j^{th}\) column \((a_{i,j})_i\) of the Cartan matrix corresponding to this Dynkin diagram, as a container (or iterator) of tuples \((i, a_{i,j})\)

EXAMPLES:

sage: g = DynkinDiagram(["B",4])
sage: [ (i,a) for (i,a) in g.column(3) ]
[(3, 2), (2, -1), (4, -2)]

>>> from sage.all import *
>>> g = DynkinDiagram(["B",Integer(4)])
>>> [ (i,a) for (i,a) in g.column(Integer(3)) ]
[(3, 2), (2, -1), (4, -2)]
coxeter_diagram()[source]#

Construct the Coxeter diagram of self.

See also

CartanType_abstract.coxeter_diagram()

EXAMPLES:

sage: cm = CartanMatrix([[2,-5,0],[-2,2,-1],[0,-1,2]])
sage: D = cm.dynkin_diagram()
sage: G = D.coxeter_diagram(); G
Graph on 3 vertices
sage: G.edges(sort=True)
[(0, 1, +Infinity), (1, 2, 3)]

sage: ct = CartanType([['A',2,2], ['B',3]])
sage: ct.coxeter_diagram()
Graph on 5 vertices
sage: ct.dynkin_diagram().coxeter_diagram() == ct.coxeter_diagram()
True

>>> from sage.all import *
>>> cm = CartanMatrix([[Integer(2),-Integer(5),Integer(0)],[-Integer(2),Integer(2),-Integer(1)],[Integer(0),-Integer(1),Integer(2)]])
>>> D = cm.dynkin_diagram()
>>> G = D.coxeter_diagram(); G
Graph on 3 vertices
>>> G.edges(sort=True)
[(0, 1, +Infinity), (1, 2, 3)]

>>> ct = CartanType([['A',Integer(2),Integer(2)], ['B',Integer(3)]])
>>> ct.coxeter_diagram()
Graph on 5 vertices
>>> ct.dynkin_diagram().coxeter_diagram() == ct.coxeter_diagram()
True
dual()[source]#

Returns the dual Dynkin diagram, obtained by reversing all edges.

EXAMPLES:

sage: D = DynkinDiagram(['C',3])
sage: D.edges(sort=True)
[(1, 2, 1), (2, 1, 1), (2, 3, 1), (3, 2, 2)]
sage: D.dual()
O---O=>=O
1   2   3
B3
sage: D.dual().edges(sort=True)
[(1, 2, 1), (2, 1, 1), (2, 3, 2), (3, 2, 1)]
sage: D.dual() == DynkinDiagram(['B',3])
True

>>> from sage.all import *
>>> D = DynkinDiagram(['C',Integer(3)])
>>> D.edges(sort=True)
[(1, 2, 1), (2, 1, 1), (2, 3, 1), (3, 2, 2)]
>>> D.dual()
O---O=>=O
1   2   3
B3
>>> D.dual().edges(sort=True)
[(1, 2, 1), (2, 1, 1), (2, 3, 2), (3, 2, 1)]
>>> D.dual() == DynkinDiagram(['B',Integer(3)])
True
dynkin_diagram()[source]#

EXAMPLES:

sage: DynkinDiagram(['C',3]).dynkin_diagram()
O---O=<=O
1   2   3
C3

>>> from sage.all import *
>>> DynkinDiagram(['C',Integer(3)]).dynkin_diagram()
O---O=<=O
1   2   3
C3
index_set()[source]#

EXAMPLES:

sage: DynkinDiagram(['C',3]).index_set()
(1, 2, 3)
sage: DynkinDiagram("A2","B2","F4").index_set()
(1, 2, 3, 4, 5, 6, 7, 8)

>>> from sage.all import *
>>> DynkinDiagram(['C',Integer(3)]).index_set()
(1, 2, 3)
>>> DynkinDiagram("A2","B2","F4").index_set()
(1, 2, 3, 4, 5, 6, 7, 8)
is_affine()[source]#

Check if self corresponds to an affine root system.

EXAMPLES:

sage: CartanType(['F',4]).dynkin_diagram().is_affine()
False
sage: D = DynkinDiagram(CartanMatrix([[2, -4], [-3, 2]]))
sage: D.is_affine()
False

>>> from sage.all import *
>>> CartanType(['F',Integer(4)]).dynkin_diagram().is_affine()
False
>>> D = DynkinDiagram(CartanMatrix([[Integer(2), -Integer(4)], [-Integer(3), Integer(2)]]))
>>> D.is_affine()
False
is_crystallographic()[source]#

Implements CartanType_abstract.is_crystallographic()

A Dynkin diagram always corresponds to a crystallographic root system.

EXAMPLES:

sage: CartanType(['F',4]).dynkin_diagram().is_crystallographic()
True

>>> from sage.all import *
>>> CartanType(['F',Integer(4)]).dynkin_diagram().is_crystallographic()
True
is_finite()[source]#

Check if self corresponds to a finite root system.

EXAMPLES:

sage: CartanType(['F',4]).dynkin_diagram().is_finite()
True
sage: D = DynkinDiagram(CartanMatrix([[2, -4], [-3, 2]]))
sage: D.is_finite()
False

>>> from sage.all import *
>>> CartanType(['F',Integer(4)]).dynkin_diagram().is_finite()
True
>>> D = DynkinDiagram(CartanMatrix([[Integer(2), -Integer(4)], [-Integer(3), Integer(2)]]))
>>> D.is_finite()
False
is_irreducible()[source]#

Check if self corresponds to an irreducible root system.

EXAMPLES:

sage: CartanType(['F',4]).dynkin_diagram().is_irreducible()
True
sage: CM = CartanMatrix([[2,-6],[-4,2]])
sage: CM.dynkin_diagram().is_irreducible()
True
sage: CartanType("A2xB3").dynkin_diagram().is_irreducible()
False
sage: CM = CartanMatrix([[2,-6,0],[-4,2,0],[0,0,2]])
sage: CM.dynkin_diagram().is_irreducible()
False

>>> from sage.all import *
>>> CartanType(['F',Integer(4)]).dynkin_diagram().is_irreducible()
True
>>> CM = CartanMatrix([[Integer(2),-Integer(6)],[-Integer(4),Integer(2)]])
>>> CM.dynkin_diagram().is_irreducible()
True
>>> CartanType("A2xB3").dynkin_diagram().is_irreducible()
False
>>> CM = CartanMatrix([[Integer(2),-Integer(6),Integer(0)],[-Integer(4),Integer(2),Integer(0)],[Integer(0),Integer(0),Integer(2)]])
>>> CM.dynkin_diagram().is_irreducible()
False
odd_isotropic_roots()[source]#

Return the odd isotropic roots of self.

EXAMPLES:

sage: g = DynkinDiagram(['A',4])
sage: g.odd_isotropic_roots()
()
sage: g = DynkinDiagram(['A',[4,3]])
sage: g.odd_isotropic_roots()
(0,)

>>> from sage.all import *
>>> g = DynkinDiagram(['A',Integer(4)])
>>> g.odd_isotropic_roots()
()
>>> g = DynkinDiagram(['A',[Integer(4),Integer(3)]])
>>> g.odd_isotropic_roots()
(0,)
rank()[source]#

Returns the index set for this Dynkin diagram

EXAMPLES:

sage: DynkinDiagram(['C',3]).rank()
3
sage: DynkinDiagram("A2","B2","F4").rank()
8

>>> from sage.all import *
>>> DynkinDiagram(['C',Integer(3)]).rank()
3
>>> DynkinDiagram("A2","B2","F4").rank()
8
relabel(*args, **kwds)[source]#

Return the relabelled Dynkin diagram of self.

INPUT: see relabel()

There is one difference: the default value for inplace is False instead of True.

EXAMPLES:

sage: D = DynkinDiagram(['C',3])
sage: D.relabel({1:0, 2:4, 3:1})
O---O=<=O
0   4   1
C3 relabelled by {1: 0, 2: 4, 3: 1}
sage: D
O---O=<=O
1   2   3
C3

sage: _ = D.relabel({1:0, 2:4, 3:1}, inplace=True)
sage: D
O---O=<=O
0   4   1
C3 relabelled by {1: 0, 2: 4, 3: 1}

sage: D = DynkinDiagram(['A', [1,2]])
sage: Dp = D.relabel({-1:4, 0:-3, 1:3, 2:2})
sage: Dp
O---X---O---O
4   -3  3   2
A1|2 relabelled by {-1: 4, 0: -3, 1: 3, 2: 2}
sage: Dp.odd_isotropic_roots()
(-3,)

sage: D = DynkinDiagram(['D', 5])
sage: G, perm = D.relabel(range(5), return_map=True)
sage: G
        O 4
        |
        |
O---O---O---O
0   1   2   3
D5 relabelled by {1: 0, 2: 1, 3: 2, 4: 3, 5: 4}
sage: perm
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4}

sage: perm = D.relabel(range(5), return_map=True, inplace=True)
sage: D
        O 4
        |
        |
O---O---O---O
0   1   2   3
D5 relabelled by {1: 0, 2: 1, 3: 2, 4: 3, 5: 4}
sage: perm
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4}

>>> from sage.all import *
>>> D = DynkinDiagram(['C',Integer(3)])
>>> D.relabel({Integer(1):Integer(0), Integer(2):Integer(4), Integer(3):Integer(1)})
O---O=<=O
0   4   1
C3 relabelled by {1: 0, 2: 4, 3: 1}
>>> D
O---O=<=O
1   2   3
C3

>>> _ = D.relabel({Integer(1):Integer(0), Integer(2):Integer(4), Integer(3):Integer(1)}, inplace=True)
>>> D
O---O=<=O
0   4   1
C3 relabelled by {1: 0, 2: 4, 3: 1}

>>> D = DynkinDiagram(['A', [Integer(1),Integer(2)]])
>>> Dp = D.relabel({-Integer(1):Integer(4), Integer(0):-Integer(3), Integer(1):Integer(3), Integer(2):Integer(2)})
>>> Dp
O---X---O---O
4   -3  3   2
A1|2 relabelled by {-1: 4, 0: -3, 1: 3, 2: 2}
>>> Dp.odd_isotropic_roots()
(-3,)

>>> D = DynkinDiagram(['D', Integer(5)])
>>> G, perm = D.relabel(range(Integer(5)), return_map=True)
>>> G
        O 4
        |
        |
O---O---O---O
0   1   2   3
D5 relabelled by {1: 0, 2: 1, 3: 2, 4: 3, 5: 4}
>>> perm
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4}

>>> perm = D.relabel(range(Integer(5)), return_map=True, inplace=True)
>>> D
        O 4
        |
        |
O---O---O---O
0   1   2   3
D5 relabelled by {1: 0, 2: 1, 3: 2, 4: 3, 5: 4}
>>> perm
{1: 0, 2: 1, 3: 2, 4: 3, 5: 4}
row(i)[source]#

Returns the \(i^{th}\) row \((a_{i,j})_j\) of the Cartan matrix corresponding to this Dynkin diagram, as a container (or iterator) of tuples \((j, a_{i,j})\)

EXAMPLES:

sage: g = DynkinDiagram(["C",4])
sage: [ (i,a) for (i,a) in g.row(3) ]
[(3, 2), (2, -1), (4, -2)]

>>> from sage.all import *
>>> g = DynkinDiagram(["C",Integer(4)])
>>> [ (i,a) for (i,a) in g.row(Integer(3)) ]
[(3, 2), (2, -1), (4, -2)]
subtype(index_set)[source]#

Return a subtype of self given by index_set.

A subtype can be considered the Dynkin diagram induced from the Dynkin diagram of self by index_set.

EXAMPLES:

sage: D = DynkinDiagram(['A',6,2]); D
O=<=O---O=<=O
0   1   2   3
BC3~
sage: D.subtype([1,2,3])
Dynkin diagram of rank 3

>>> from sage.all import *
>>> D = DynkinDiagram(['A',Integer(6),Integer(2)]); D
O=<=O---O=<=O
0   1   2   3
BC3~
>>> D.subtype([Integer(1),Integer(2),Integer(3)])
Dynkin diagram of rank 3
symmetrizer()[source]#

Return the symmetrizer of the corresponding Cartan matrix.

EXAMPLES:

sage: d = DynkinDiagram()
sage: d.add_edge(1,2,3)
sage: d.add_edge(2,3)
sage: d.add_edge(3,4,3)
sage: d.symmetrizer()
Finite family {1: 9, 2: 3, 3: 3, 4: 1}

>>> from sage.all import *
>>> d = DynkinDiagram()
>>> d.add_edge(Integer(1),Integer(2),Integer(3))
>>> d.add_edge(Integer(2),Integer(3))
>>> d.add_edge(Integer(3),Integer(4),Integer(3))
>>> d.symmetrizer()
Finite family {1: 9, 2: 3, 3: 3, 4: 1}
sage.combinat.root_system.dynkin_diagram.precheck(t, letter=None, length=None, affine=None, n_ge=None, n=None)[source]#

EXAMPLES:

sage: from sage.combinat.root_system.dynkin_diagram import precheck
sage: ct = CartanType(['A',4])
sage: precheck(ct, letter='C')
Traceback (most recent call last):
...
ValueError: t[0] must be = 'C'
sage: precheck(ct, affine=1)
Traceback (most recent call last):
...
ValueError: t[2] must be = 1
sage: precheck(ct, length=3)
Traceback (most recent call last):
...
ValueError: len(t) must be = 3
sage: precheck(ct, n=3)
Traceback (most recent call last):
...
ValueError: t[1] must be = 3
sage: precheck(ct, n_ge=5)
Traceback (most recent call last):
...
ValueError: t[1] must be >= 5

>>> from sage.all import *
>>> from sage.combinat.root_system.dynkin_diagram import precheck
>>> ct = CartanType(['A',Integer(4)])
>>> precheck(ct, letter='C')
Traceback (most recent call last):
...
ValueError: t[0] must be = 'C'
>>> precheck(ct, affine=Integer(1))
Traceback (most recent call last):
...
ValueError: t[2] must be = 1
>>> precheck(ct, length=Integer(3))
Traceback (most recent call last):
...
ValueError: len(t) must be = 3
>>> precheck(ct, n=Integer(3))
Traceback (most recent call last):
...
ValueError: t[1] must be = 3
>>> precheck(ct, n_ge=Integer(5))
Traceback (most recent call last):
...
ValueError: t[1] must be >= 5