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

Article type: Research Article

Authors: Pérez, Claudia | Abarca, Mario | Rivera, Daniel^{; *}

Affiliations: 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. darivera@uaem.mx

Correspondence: [*] Address for correspondence: 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.

Abstract: 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(n6) 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(n3) operations taking an integer matrix as input.

Keywords: quasi-Cartan matrix, Dynkin diagram, integral quadratic form, root system, inflations algorithm

DOI: 10.3233/FI-2018-1653

Journal: Fundamenta Informaticae, vol. 158, no. 4, pp. 369-384, 2018