Cubic Algorithm to Compute the Dynkin Type of a Positive Definite Quasi-Cartan Matrix

• Autorzy: Pérez C. , Abarca M. , Rivera D.

Identyfikatory

DOI

10.3233/FI-2018-1653

• Języki publikacji: EN

Abstrakty

EN

Inflations algorithm is a procedure that appears implicitly in Ovsienko’s classical proof for the classification of positive definite integral quadratic forms. The best known upper asymptotic bound for its time complexity is an exponential one. In this paper we show that this bound can be tightened to O(n⁶) for the naive implementation. Also, we propose a new approach to show how to decide whether an admissible quasi-Cartan matrix is positive definite and compute the Dynkin type in just O(n³) operations taking an integer matrix as input.

Słowa kluczowe

EN

Dynkin diagram; inflation algorithm; integral quadratic form; quasi-Cartan matrix; root system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 158, nr 4
• Strony: 369--384
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Pérez C.

• Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

autor

Abarca M.

• Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

autor

Rivera D.

• Instituto de Investigación en Ciencias Básicas y Aplicadas, Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

Bibliografia

• [1] Barot M, Geiss C, Zelevinsky A. Cluster algebras of finite type and positive symmetrizable matrices. Journal of the London Mathematical Society. 2006;73(3):545-564.
• [2] Knapp AW. Lie Groups Beyond an Introduction. vol. 140 of Progress in Mathematics. 2nd ed. Birkhäuser; 2002. URL http://www.springer.com/book/978-0-8176-4259-4.
• [3] Abarca M, Rivera D. Graph Theoretical and Algorithmic Characterizations of Positive Definite Symmetric Quasi-Cartan Matrices. Fundamenta Informaticae. 2016;149(3):241-261. doi:10.3233/FI-2016-1448.
• [4] Barot M, Rivera D. Generalized Serre relations for Lie algebras associated with positive unit forms. Journal of Pure and Applied Algebra. 2007;211(2):360-373. URL https://doi.org/10.1016/j.jpaa.2007.01.008.
• [5] Ovsienko SA. Integer weakly positive forms. Schurian Matrix problems and quadratic forms. 1978; pp. 3-17.
• [6] Makuracki B, Simson D, Zyglarski B. Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops. Fundamenta Informaticae. 2017;153(4):367-398. doi:10.3233/FI-2017-1545.
• [7] Barot M, De la Peña J. The Dynkin type of a non-negative unit form. Expositiones Mathematicae. 1999;17(4):339-348.
• [8] Barot M. Introduction to the representation theory of algebras. Springer; 2012.
• [9] Ringel CM. Tame Algebras and Integral Quadratic Forms. vol. 1099 of Lecture Notes in Mathematics. Springer-Verlag Berlin Heidelberg; 1984. doi:10.1007/BFb0072870.
• [10] Bourbaki N. Groupes et algebres de Lie. vol. Ch. IV-VI of Paris. Hermann & Co.; 1960.
• [11] Dlab V, Ringel C. Indecomposable representations of graphs and algebras. American Mathematical Society, 1976, 173, vol. 6(3). ISBN: 0-8218-1873-2.
• [12] Kasjan S, Simson D. Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops, I. Mesh Root Systems. Fundamenta Informaticae. 2015;139:153-184. doi:10.3233/FI-2015-1230.
• [13] Kasjan S, Simson D. Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs. Fundamenta Informaticae. 2015;139:249-275. doi:10.3233/FI-2015-1234.
• [14] Kasjan S, Simson D. Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edgebipartite Graphs with Loops, II. Application to Coxeter Spectral Analysis. Fundamenta Informaticae. 2015;139:185-209. doi:10.3233/FI-2015-1231.
• [15] Kosakowska J. Inflation Algorithms for Positive and Principal Edge-bipartite Graphs and Unit Quadratic Forms. Fundamenta Informaticae. 2012;119(2):149-162. URL http://content.iospress.com/articles/fundamenta-informaticae/fi119-2-02.
• [16] Cormen TH. Introduction to algorithms. MIT press; 2009. ISBN: 10:0262033844, 13:978-0262033848.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).