Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix


Authors: Bartosz Makuracki and Andrzej Mróz
Journal: Math. Comp. 90 (2021), 389-412
MSC (2010): Primary 15A21, 68Q25; Secondary 05C22, 68W30
DOI: https://doi.org/10.1090/mcom/3559
Published electronically: August 1, 2020
MathSciNet review: 4166466
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Cartan matrices and quasi-Cartan matrices play an important role in such areas as Lie theory, representation theory, and algebraic graph theory. It is known that each (connected) positive definite quasi-Cartan matrix $ A\in \mathbb{M}_n(\mathbb{Z})$ is $ \mathbb{Z}$-equivalent with the Cartan matrix of a Dynkin diagram, called the Dynkin type of $ A$. We present a symbolic, graph-theoretic algorithm to compute the Dynkin type of $ A$, of the pessimistic arithmetic (word) complexity $ \mathcal {O}(n^2)$, significantly improving the existing algorithms. As an application we note that our algorithm can be used as a positive definiteness test for an arbitrary quasi-Cartan matrix, more efficient than standard tests. Moreover, we apply the algorithm to study a class of (symmetric and non-symmetric) quasi-Cartan matrices related to Nakayama algebras.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A21, 68Q25, 05C22, 68W30

Retrieve articles in all journals with MSC (2010): 15A21, 68Q25, 05C22, 68W30


Additional Information

Bartosz Makuracki
Affiliation: Department of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland
MR Author ID: 1226659
Email: bartmak@mat.umk.pl

Andrzej Mróz
Affiliation: Department of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland
Email: amroz@mat.umk.pl

DOI: https://doi.org/10.1090/mcom/3559
Keywords: Quasi-Cartan matrix, Cartan matrix, Gram matrix, inflation algorithm, integral quadratic form, Dynkin diagram.
Received by editor(s): September 9, 2019
Received by editor(s) in revised form: April 14, 2020
Published electronically: August 1, 2020
Additional Notes: The second author is the corresponding author.
Article copyright: © Copyright 2020 American Mathematical Society