Search

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 ∈ Mn(Z) is 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 O(n2), 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. [ABSTRACT FROM AUTHOR]