Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Cartan matrices
AUTHORS:
- Travis Scrimshaw (2012-04-22): Nicolas M. Thiery moved matrix creation to :class:`CartanType` to prepare :func:`cartan_matrix()` for deprecation. - Christian Stump, Travis Scrimshaw (2013-04-13): Created :class:`CartanMatrix`. """ #***************************************************************************** # Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>, # Copyright (C) 2012,2013 Travis Scrimshaw <tscrim at ucdavis.edu>, # Copyright (C) 2013 Christian Stump, # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from six.moves import range from six import add_metaclass
from sage.misc.cachefunc import cached_method from sage.matrix.constructor import matrix from sage.structure.element import is_Matrix from sage.matrix.matrix_space import MatrixSpace from sage.misc.inherit_comparison import InheritComparisonClasscallMetaclass from sage.misc.classcall_metaclass import typecall from sage.misc.misc import powerset from sage.matrix.matrix_integer_sparse import Matrix_integer_sparse from sage.rings.all import ZZ from sage.combinat.root_system.cartan_type import CartanType, CartanType_abstract from sage.combinat.root_system.root_system import RootSystem from sage.sets.family import Family from sage.graphs.digraph import DiGraph
@add_metaclass(InheritComparisonClasscallMetaclass) class CartanMatrix(Matrix_integer_sparse, CartanType_abstract): r""" A (generalized) Cartan matrix.
A matrix `A = (a_{ij})_{i,j \in I}` for some index set `I` is a generalized Cartan matrix if it satisfies the following properties:
- `a_{ii} = 2` for all `i`, - `a_{ij} \leq 0` for all `i \neq j`, - `a_{ij} = 0` if and only if `a_{ji} = 0` for all `i \neq j`.
Additionally some reference assume that a Cartan matrix is *symmetrizable* (see :meth:`is_symmetrizable`). However following Kac, we do not make that assumption here.
INPUT:
Can be anything which is accepted by ``CartanType`` or a matrix.
If given a matrix, one can also use the keyword ``cartan_type`` when giving a matrix to explicitly state the type. Otherwise this will try to check the input matrix against possible standard types of Cartan matrices. To disable this check, use the keyword ``cartan_type_check = False``.
EXAMPLES::
sage: CartanMatrix(['A', 4]) [ 2 -1 0 0] [-1 2 -1 0] [ 0 -1 2 -1] [ 0 0 -1 2] sage: CartanMatrix(['B', 6]) [ 2 -1 0 0 0 0] [-1 2 -1 0 0 0] [ 0 -1 2 -1 0 0] [ 0 0 -1 2 -1 0] [ 0 0 0 -1 2 -1] [ 0 0 0 0 -2 2] sage: CartanMatrix(['C', 4]) [ 2 -1 0 0] [-1 2 -1 0] [ 0 -1 2 -2] [ 0 0 -1 2] sage: CartanMatrix(['D', 6]) [ 2 -1 0 0 0 0] [-1 2 -1 0 0 0] [ 0 -1 2 -1 0 0] [ 0 0 -1 2 -1 -1] [ 0 0 0 -1 2 0] [ 0 0 0 -1 0 2] sage: CartanMatrix(['E',6]) [ 2 0 -1 0 0 0] [ 0 2 0 -1 0 0] [-1 0 2 -1 0 0] [ 0 -1 -1 2 -1 0] [ 0 0 0 -1 2 -1] [ 0 0 0 0 -1 2] sage: CartanMatrix(['E',7]) [ 2 0 -1 0 0 0 0] [ 0 2 0 -1 0 0 0] [-1 0 2 -1 0 0 0] [ 0 -1 -1 2 -1 0 0] [ 0 0 0 -1 2 -1 0] [ 0 0 0 0 -1 2 -1] [ 0 0 0 0 0 -1 2] sage: CartanMatrix(['E', 8]) [ 2 0 -1 0 0 0 0 0] [ 0 2 0 -1 0 0 0 0] [-1 0 2 -1 0 0 0 0] [ 0 -1 -1 2 -1 0 0 0] [ 0 0 0 -1 2 -1 0 0] [ 0 0 0 0 -1 2 -1 0] [ 0 0 0 0 0 -1 2 -1] [ 0 0 0 0 0 0 -1 2] sage: CartanMatrix(['F', 4]) [ 2 -1 0 0] [-1 2 -1 0] [ 0 -2 2 -1] [ 0 0 -1 2]
This is different from MuPAD-Combinat, due to different node convention?
::
sage: CartanMatrix(['G', 2]) [ 2 -3] [-1 2] sage: CartanMatrix(['A',1,1]) [ 2 -2] [-2 2] sage: CartanMatrix(['A', 3, 1]) [ 2 -1 0 -1] [-1 2 -1 0] [ 0 -1 2 -1] [-1 0 -1 2] sage: CartanMatrix(['B', 3, 1]) [ 2 0 -1 0] [ 0 2 -1 0] [-1 -1 2 -1] [ 0 0 -2 2] sage: CartanMatrix(['C', 3, 1]) [ 2 -1 0 0] [-2 2 -1 0] [ 0 -1 2 -2] [ 0 0 -1 2] sage: CartanMatrix(['D', 4, 1]) [ 2 0 -1 0 0] [ 0 2 -1 0 0] [-1 -1 2 -1 -1] [ 0 0 -1 2 0] [ 0 0 -1 0 2] sage: CartanMatrix(['E', 6, 1]) [ 2 0 -1 0 0 0 0] [ 0 2 0 -1 0 0 0] [-1 0 2 0 -1 0 0] [ 0 -1 0 2 -1 0 0] [ 0 0 -1 -1 2 -1 0] [ 0 0 0 0 -1 2 -1] [ 0 0 0 0 0 -1 2] sage: CartanMatrix(['E', 7, 1]) [ 2 -1 0 0 0 0 0 0] [-1 2 0 -1 0 0 0 0] [ 0 0 2 0 -1 0 0 0] [ 0 -1 0 2 -1 0 0 0] [ 0 0 -1 -1 2 -1 0 0] [ 0 0 0 0 -1 2 -1 0] [ 0 0 0 0 0 -1 2 -1] [ 0 0 0 0 0 0 -1 2] sage: CartanMatrix(['E', 8, 1]) [ 2 0 0 0 0 0 0 0 -1] [ 0 2 0 -1 0 0 0 0 0] [ 0 0 2 0 -1 0 0 0 0] [ 0 -1 0 2 -1 0 0 0 0] [ 0 0 -1 -1 2 -1 0 0 0] [ 0 0 0 0 -1 2 -1 0 0] [ 0 0 0 0 0 -1 2 -1 0] [ 0 0 0 0 0 0 -1 2 -1] [-1 0 0 0 0 0 0 -1 2] sage: CartanMatrix(['F', 4, 1]) [ 2 -1 0 0 0] [-1 2 -1 0 0] [ 0 -1 2 -1 0] [ 0 0 -2 2 -1] [ 0 0 0 -1 2] sage: CartanMatrix(['G', 2, 1]) [ 2 0 -1] [ 0 2 -3] [-1 -1 2]
.. NOTE::
Since this is a matrix, :meth:`row()` and :meth:`column()` will return the standard row and column respectively. To get the row with the indices as in Dynkin diagrams/Cartan types, use :meth:`row_with_indices()` and :meth:`column_with_indices()` respectively. """ @staticmethod def __classcall_private__(cls, data=None, index_set=None, cartan_type=None, cartan_type_check=True): """ Normalize input so we can inherit from sparse integer matrix.
.. NOTE::
To disable the Cartan type check, use the optional argument ``cartan_type_check = False``.
EXAMPLES::
sage: C = CartanMatrix(['A',1,1]) sage: C2 = CartanMatrix([[2, -2], [-2, 2]]) sage: C3 = CartanMatrix(matrix([[2, -2], [-2, 2]]), [0, 1]) sage: C == C2 and C == C3 True
TESTS:
Check that :trac:`15740` is fixed::
sage: d = DynkinDiagram() sage: d.add_edge('a', 'b', 2) sage: d.index_set() ('a', 'b') sage: cm = CartanMatrix(d) sage: cm.index_set() ('a', 'b') """ # Special case with 0 args and kwds has Cartan type data = CartanType(cartan_type)
data = [] n = 0 index_set = tuple() cartan_type = None subdivisions = None else:
else:
for i in range(n)} else: raise ValueError("the input matrix is not a generalized Cartan matrix")
else:
raise ValueError("the given index set is not valid")
# We can do the Cartan type initialization later as this is not # a unique representation # FIXME: We have to initialize the CartanMatrix part separately because # of the __cinit__ of the matrix. We should get rid of this workaround
def matrix_space(self, nrows=None, ncols=None, sparse=None): r""" Return a matrix space over the integers.
INPUT:
- ``nrows`` - number of rows
- ``ncols`` - number of columns
- ``sparse`` - (boolean) sparseness
EXAMPLES::
sage: cm = CartanMatrix(['A', 3]) sage: cm.matrix_space() Full MatrixSpace of 3 by 3 sparse matrices over Integer Ring sage: cm.matrix_space(2, 2) Full MatrixSpace of 2 by 2 sparse matrices over Integer Ring sage: cm[:2,1:] # indirect doctest [-1 0] [ 2 -1] """
else:
def _CM_init(self, cartan_type, index_set, cartan_type_check): """ Initialize ``self`` as a Cartan matrix.
TESTS::
sage: C = CartanMatrix(['A',1,1]) # indirect doctest sage: TestSuite(C).run(skip=["_test_category", "_test_change_ring"]) """
# Placeholder so we don't have to reimplement creating a # Dynkin diagram from a Cartan matrix
def __reduce__(self): """ Used for pickling.
TESTS::
sage: CM = CartanMatrix(['A',4]) sage: x = loads(dumps(CM)) sage: x._index_set (1, 2, 3, 4) """ return (CartanMatrix, (self.dynkin_diagram(),))
def root_system(self): """ Return the root system corresponding to ``self``.
EXAMPLES::
sage: C = CartanMatrix(['A',3]) sage: C.root_system() Root system of type ['A', 3] """
def root_space(self): """ Return the root space corresponding to ``self``.
EXAMPLES::
sage: C = CartanMatrix(['A',3]) sage: C.root_space() Root space over the Rational Field of the Root system of type ['A', 3] """
def reflection_group(self, type="matrix"): """ Return the reflection group corresponding to ``self``.
EXAMPLES::
sage: C = CartanMatrix(['A',3]) sage: C.reflection_group() Weyl Group of type ['A', 3] (as a matrix group acting on the root space) """
if type == "permutation": if not self.is_finite(): raise ValueError("only works for finite types") Phi = RS.roots() gens = {} from sage.groups.perm_gps.permgroup_named import SymmetricGroup S = SymmetricGroup(len(Phi)) for i in self.index_set(): pi = S([ Phi.index( beta.simple_reflection(i) ) + 1 for beta in Phi ]) gens[i] = pi return S.subgroup( gens[i] for i in gens )
raise ValueError("The reflection group is only available as a matrix group or as a permutation group.")
def symmetrizer(self): """ Return the symmetrizer of ``self``.
EXAMPLES::
sage: cm = CartanMatrix([[2,-5],[-2,2]]) sage: cm.symmetrizer() Finite family {0: 2, 1: 5}
TESTS:
Check that the symmetrizer computed from the Cartan matrix agrees with the values given by the Cartan type::
sage: ct = CartanType(['B',4,1]) sage: ct.symmetrizer() Finite family {0: 2, 1: 2, 2: 2, 3: 2, 4: 1} sage: ct.cartan_matrix().symmetrizer() Finite family {0: 2, 1: 2, 2: 2, 3: 2, 4: 1} """ raise ValueError("the Cartan matrix is not symmetrizable") # The result from is_symmetrizable needs to be scaled # to integer coefficients
@cached_method def symmetrized_matrix(self): """ Return the symmetrized matrix of ``self`` if symmetrizable.
EXAMPLES::
sage: cm = CartanMatrix(['B',4,1]) sage: cm.symmetrized_matrix() [ 4 0 -2 0 0] [ 0 4 -2 0 0] [-2 -2 4 -2 0] [ 0 0 -2 4 -2] [ 0 0 0 -2 2] """
########################################################################## # Cartan type methods
def index_set(self): """ Return the index set of ``self``.
EXAMPLES::
sage: C = CartanMatrix(['A',1,1]) sage: C.index_set() (0, 1) sage: C = CartanMatrix(['E',6]) sage: C.index_set() (1, 2, 3, 4, 5, 6) """
def cartan_type(self): """ Return the Cartan type of ``self`` or ``self`` if unknown.
EXAMPLES::
sage: C = CartanMatrix(['A',4,1]) sage: C.cartan_type() ['A', 4, 1]
If the Cartan type is unknown::
sage: C = CartanMatrix([[2,-1,-2], [-1,2,-1], [-2,-1,2]]) sage: C.cartan_type() [ 2 -1 -2] [-1 2 -1] [-2 -1 2] """
def subtype(self, index_set): """ 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: C = CartanMatrix(['F',4]) sage: S = C.subtype([1,2,3]) sage: S [ 2 -1 0] [-1 2 -1] [ 0 -2 2] sage: S.index_set() (1, 2, 3) """
def rank(self): r""" Return the rank of ``self``.
EXAMPLES::
sage: CartanMatrix(['C',3]).rank() 3 sage: CartanMatrix(["A2","B2","F4"]).rank() 8 """
def relabel(self, relabelling): """ Return the relabelled Cartan matrix.
EXAMPLES::
sage: CM = CartanMatrix(['C',3]) sage: R = CM.relabel({1:0, 2:4, 3:1}); R [ 2 0 -1] [ 0 2 -1] [-1 -2 2] sage: R.index_set() (0, 1, 4) sage: CM [ 2 -1 0] [-1 2 -2] [ 0 -1 2] """
@cached_method def dynkin_diagram(self): """ Return the Dynkin diagram corresponding to ``self``.
EXAMPLES::
sage: C = CartanMatrix(['A',2]) sage: C.dynkin_diagram() O---O 1 2 A2 sage: C = CartanMatrix(['F',4,1]) sage: C.dynkin_diagram() O---O---O=>=O---O 0 1 2 3 4 F4~ sage: C = CartanMatrix([[2,-4],[-4,2]]) sage: C.dynkin_diagram() Dynkin diagram of rank 2 """
def cartan_matrix(self): r""" Return the Cartan matrix of ``self``.
EXAMPLES::
sage: CartanMatrix(['C',3]).cartan_matrix() [ 2 -1 0] [-1 2 -2] [ 0 -1 2] """
def dual(self): r""" Return the dual Cartan matrix of ``self``, which is obtained by taking the transpose.
EXAMPLES::
sage: ct = CartanType(['C',3]) sage: M = CartanMatrix(ct); M [ 2 -1 0] [-1 2 -2] [ 0 -1 2] sage: M.dual() [ 2 -1 0] [-1 2 -1] [ 0 -2 2] sage: M.dual() == CartanMatrix(ct.dual()) True sage: M.dual().cartan_type() == ct.dual() True
An example with arbitrary Cartan matrices::
sage: cm = CartanMatrix([[2,-5], [-2, 2]]); cm [ 2 -5] [-2 2] sage: cm.dual() [ 2 -2] [-5 2] sage: cm.dual() == CartanMatrix(cm.transpose()) True sage: cm.dual().dual() == cm True """
def is_simply_laced(self): """ Implements :meth:`CartanType_abstract.is_simply_laced()`.
A Cartan matrix is simply-laced if all non diagonal entries are `0` or `-1`.
EXAMPLES::
sage: cm = CartanMatrix([[2, -1, -1, -1], [-1, 2, -1, -1], [-1, -1, 2, -1], [-1, -1, -1, 2]]) sage: cm.is_simply_laced() True """ return False
def is_crystallographic(self): """ Implements :meth:`CartanType_abstract.is_crystallographic`.
A Cartan matrix is crystallographic if it is symmetrizable.
EXAMPLES::
sage: CartanMatrix(['F',4]).is_crystallographic() True """
def column_with_indices(self, j): """ Return the `j^{th}` column `(a_{i,j})_i` of ``self`` as a container (or iterator) of tuples `(i, a_{i,j})`
EXAMPLES::
sage: M = CartanMatrix(['B',4]) sage: [ (i,a) for (i,a) in M.column_with_indices(3) ] [(3, 2), (2, -1), (4, -2)] """
def row_with_indices(self, i): """ Return the `i^{th}` row `(a_{i,j})_j` of ``self`` as a container (or iterator) of tuples `(j, a_{i,j})`
EXAMPLES::
sage: M = CartanMatrix(['C',4]) sage: [ (i,a) for (i,a) in M.row_with_indices(3) ] [(3, 2), (2, -1), (4, -2)] """
@cached_method def is_finite(self): """ Return ``True`` if ``self`` is a finite type or ``False`` otherwise.
A generalized Cartan matrix is finite if the determinant of all its principal submatrices (see :meth:`principal_submatrices`) is positive. Such matrices have a positive definite symmetrized matrix. Note that a finite matrix may consist of multiple blocks of Cartan matrices each having finite Cartan type.
EXAMPLES::
sage: M = CartanMatrix(['C',4]) sage: M.is_finite() True sage: M = CartanMatrix(['D',4,1]) sage: M.is_finite() False sage: M = CartanMatrix([[2, -4], [-3, 2]]) sage: M.is_finite() False """ return False
@cached_method def is_affine(self): """ Return ``True`` if ``self`` is an affine type or ``False`` otherwise.
A generalized Cartan matrix is affine if all of its indecomposable blocks are either finite (see :meth:`is_finite`) or have zero determinant with all proper principal minors positive.
EXAMPLES::
sage: M = CartanMatrix(['C',4]) sage: M.is_affine() False sage: M = CartanMatrix(['D',4,1]) sage: M.is_affine() True sage: M = CartanMatrix([[2, -4], [-3, 2]]) sage: M.is_affine() False """ for b in self.indecomposable_blocks(): if b.det() < 0 or not all( a.det() > 0 for a in b.principal_submatrices(proper=True)): return False return True
@cached_method def is_hyperbolic(self, compact=False): """ Return if ``True`` if ``self`` is a (compact) hyperbolic type or ``False`` otherwise.
An indecomposable generalized Cartan matrix is hyperbolic if it has negative determinant and if any proper connected subdiagram of its Dynkin diagram is of finite or affine type. It is compact hyperbolic if any proper connected subdiagram has finite type.
INPUT:
- ``compact`` -- if ``True``, check if matrix is compact hyperbolic
EXAMPLES::
sage: M = CartanMatrix([[2,-2,0],[-2,2,-1],[0,-1,2]]) sage: M.is_hyperbolic() True sage: M.is_hyperbolic(compact=True) False sage: M = CartanMatrix([[2,-3],[-3,2]]) sage: M.is_hyperbolic() True sage: M = CartanMatrix(['C',4]) sage: M.is_hyperbolic() False """
return False
@cached_method def is_lorentzian(self): """ Return ``True`` if ``self`` is a Lorentzian type or ``False`` otherwise.
A generalized Cartan matrix is Lorentzian if it has negative determinant and exactly one negative eigenvalue.
EXAMPLES::
sage: M = CartanMatrix([[2,-3],[-3,2]]) sage: M.is_lorentzian() True sage: M = CartanMatrix([[2,-1],[-1,2]]) sage: M.is_lorentzian() False """
@cached_method def is_indefinite(self): """ Return if ``self`` is an indefinite type or ``False`` otherwise.
EXAMPLES::
sage: M = CartanMatrix([[2,-3],[-3,2]]) sage: M.is_indefinite() True sage: M = CartanMatrix("A2") sage: M.is_indefinite() False """
@cached_method def is_indecomposable(self): """ Return if ``self`` is an indecomposable matrix or ``False`` otherwise.
EXAMPLES::
sage: M = CartanMatrix(['A',5]) sage: M.is_indecomposable() True sage: M = CartanMatrix([[2,-1,0],[-1,2,0],[0,0,2]]) sage: M.is_indecomposable() False """ # consider the empty matrix to be indecomposable
def principal_submatrices(self, proper=False): """ Return a list of all principal submatrices of ``self``.
INPUT:
- ``proper`` -- if ``True``, return only proper submatrices
EXAMPLES::
sage: M = CartanMatrix(['A',2]) sage: M.principal_submatrices() [ [ 2 -1] [], [2], [2], [-1 2] ] sage: M.principal_submatrices(proper=True) [[], [2], [2]]
"""
@cached_method def indecomposable_blocks(self): """ Return a tuple of all indecomposable blocks of ``self``.
EXAMPLES::
sage: M = CartanMatrix(['A',2]) sage: M.indecomposable_blocks() ( [ 2 -1] [-1 2] ) sage: M = CartanMatrix([['A',2,1],['A',3,1]]) sage: M.indecomposable_blocks() ( [ 2 -1 0 -1] [-1 2 -1 0] [ 2 -1 -1] [ 0 -1 2 -1] [-1 2 -1] [-1 0 -1 2], [-1 -1 2] ) """
def is_generalized_cartan_matrix(M): """ Return ``True`` if ``M`` is a generalized Cartan matrix. For a definition of a generalized Cartan matrix, see :class:`CartanMatrix`.
EXAMPLES::
sage: from sage.combinat.root_system.cartan_matrix import is_generalized_cartan_matrix sage: M = matrix([[2,-1,-2], [-1,2,-1], [-2,-1,2]]) sage: is_generalized_cartan_matrix(M) True sage: M = matrix([[2,-1,-2], [-1,2,-1], [0,-1,2]]) sage: is_generalized_cartan_matrix(M) False sage: M = matrix([[1,-1,-2], [-1,2,-1], [-2,-1,2]]) sage: is_generalized_cartan_matrix(M) False
A non-symmetrizable example::
sage: M = matrix([[2,-1,-2], [-1,2,-1], [-1,-1,2]]) sage: is_generalized_cartan_matrix(M) True """ return False return False return False return False
def find_cartan_type_from_matrix(CM): r""" Find a Cartan type by direct comparison of Dynkin diagrams given from the generalized Cartan matrix ``CM`` and return ``None`` if not found.
INPUT:
- ``CM`` -- a generalized Cartan matrix
EXAMPLES::
sage: from sage.combinat.root_system.cartan_matrix import find_cartan_type_from_matrix sage: CM = CartanMatrix([[2,-1,-1], [-1,2,-1], [-1,-1,2]]) sage: find_cartan_type_from_matrix(CM) ['A', 2, 1] sage: CM = CartanMatrix([[2,-1,0], [-1,2,-2], [0,-1,2]]) sage: find_cartan_type_from_matrix(CM) ['C', 3] relabelled by {1: 0, 2: 1, 3: 2} sage: CM = CartanMatrix([[2,-1,-2], [-1,2,-1], [-2,-1,2]]) sage: find_cartan_type_from_matrix(CM) """ # Build the list to test based upon rank
test.append(['E',6]) test += [['E',7], ['E',6,1]] test += [['E',8], ['E',7,1]] test.append(['E',8,1])
# Test every possible Cartan type and its dual
|