Polynomial-time Classification of Skew-symmetrizable Matrices with a Positive Definite Quasi-Cartan Companion

• Autorzy: Pérez Claudia , Rivera Daniel

Identyfikatory

DOI

10.3233/FI-2021-2061

• Języki publikacji: EN

Abstrakty

EN

Skew-symmetrizable matrices play an essential role in the classification of cluster algebras. We prove that the problem of assigning a positive definite quasi-Cartan companion to a skew-symmetrizable matrix is in polynomial class P. We also present an algorithm to determine the finite type Δ ∈ { {𝔸_n, 𝔻_n, 𝔹_n, ℂ_n, 𝔼₆, 𝔼₇, 𝔼₈, 𝔽₄, 𝔾₂ } of a cluster algebra associated to the mutation-equivalence class of a connected skew-symmetrizable matrix B , if it has one.

Słowa kluczowe

EN

cluster algebra; positive quasi-Cartan companion; polynomial algorithm; biconnected component; triconnected component

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 4
• Strony: 313--337
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Pérez Claudia

• Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

autor

Rivera Daniel

• Centro de Investigación en Ciencias, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Cuernavaca, Mor. Mexico

Bibliografia

• [1] Fomin S, Zelevinsky A. Cluster algebras I: foundations. Journal of the American Mathematical Society, 2002. 15:497-529. arXiv:math/0104151.
• [2] Fomin S, Zelevinsky A. Cluster algebras II: finite type classification. Inventiones Mathematicae, 2003. 154:63-121. doi:10.1007/s00222-003-0302-y.
• [3] 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. doi:10.1112/S0024610706022769.
• [4] Gu W. A Decomposition Algorithm for the Oriented Adjacency Graph of the Triangulations of a Bordered Surface with Marked Points. The Electronic Journal of Combinatorics, 2011. 18:1-45. doi:10.37236/578.
• [5] Silva E, Castonguay D. Polynomial recognition of cluster algebras of finite type. Journal of Algebra, 2016. 1:457-468. doi:10.1016/j.jalgebra.2016.03.027.
• [6] Knapp AW. Lie Groups Beyond an Introduction, volume 140 of Progress in Mathematics. Birkhäuser, 2nd edition, 2002. ISBN:9780817642594. URL http://www.springer.com/book/978-0-8176-4259-4.
• [7] Makuracki B, Mróz A. Coeffcients of non-negative quasi-Cartan matrices, their symmetrizers and Gram matrices. Discrete Applied Mathematics, 2020. doi:10.1016/j.dam.2020.05.022.
• [8] Pérez C, Abarca M, Rivera D. Cubic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix. Fundamenta Informaticae, 2018. 158(4):369-384. doi:10.3233/FI-2018-1653.
• [9] 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.
• [10] Pérez C, Rivera D. Graphical characterization of positive definite non symmetric quasi-Cartan matrices. Discrete Mathematics, 2018. 341(5):1215-1224. doi:10.1016/j.disc.2018.01.013.
• [11] Kasjan S, Simson D. Mesh Algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops,II. Application to Coxeter spectral analysis. Fundamenta Informaticae, 2015. 139:185-209. doi:10.3233/FI-2015-1231.
• [12] Makuracki B, Mróz A. Root systems and inflations of non-negative quasi-Cartan matrices. Linear Algebra and its applications, 2019. 580:128-165. doi:10.1016/j.laa.2019.06.006.
• [13] Simson D. A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices. Linear Algebra and its Applications, 2020. 586:190-238.
• [14] Barot M, de la Peña JA. The Dynkin type of a non-negative unit form. Expositiones Mathematicae, 1999. 17(4):339-348.
• [15] Gabriel P, Roiter AV. Representations of Finite-Dimensional Algebras, volume 73 of Encyclopaedia of Mathematical Sciences. Springer, 1997. ISBN 9783540629900. URL http://www.springer.com/book/978-3-540-53732-8.
• [16] Ovsienko SA. Boundedness of roots of integral weakly positive forms. In: Representations and quadratic forms (Russian), pp. 106-123, 155. Akad. Nauk Ukrain. SSR, Institute of Mathematics, Kiev, 1979.
• [17] Makuracki B, Mróz A. Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix. Mathematics of Computation, 2021. 90:389-412. doi:https://doi.org/10.1090/mcom/3559.
• [18] Seven AI. Mutation classes of skew-symmetrizable 3 x 3 matrices. Proceedings of the American Mathematical Society, 2013. 141(5):1493-1504. URL https://hdl.handle.net/11511/54786.
• [19] Seven AI. Mutation classes of finite type cluster algebras with principal coeffcients. Linear Algebra and its Applications, 2013. 438:4584-4594. doi:10.1016/j.laa.2013.02.025.
• [20] Hopcroft J, Tarjan R. Algorithm 447: Effcient algorithms for graph manipulation. Communications of the ACM, 1973. 16(6):372-378. doi:10.1145/362248.362272.
• [21] Hopcroft JE, Tarjan RE. Finding the Triconected Components of a Graph. Technical Report, Cornell University., 1972. pp. 72-140. AD0746856.
• [22] Barot M. A characterization of positive unit forms. Boletín de la Sociedad Matemática Mexicana, 1999. 5:87-94.
• [23] Hopcroft JE, Tarjan RE. Dividing a graph into Triconected Components. SIAM Journal Computation, 1973. 2(3):135-158. doi:10.1137/0202012.
• [24] Gutwenger C MP. A Linear Time Implementation of SPQR-Tress. Lecture Notes in Computer Science, 2001. 1984:77-90. doi:10.1007/3-540-44541-2_8.
• [25] Vo KP. Finding triconnected components of graphs. Linear and Multilinear Algebra, 1983. 13:143-165.
• [26] Barot M. A characterization of positive unit forms, part II. Boletín de la Sociedad Matemática Mexicana, 2001. 7:13-22. ISSN:0037-8615.
• [27] A V Aho JU J Hopcroft. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN-10:0201000296, 13:978-0201000290.
• [28] Speyer DE. Cyclically orientble graphs. available at http://arxiv.org/pdf/math/0511233v1.pdf, 2005. pp. 1-9.
• [29] Henrich T. Mutation classes of diagrams via infinite graphs. Mathematische Nachrichten, 2011. 284:2184-2205. doi:10.1002/mana.200910224.
• [30] Vatne D. The mutation class of Dn quivers. Communications in Algebra, 2010. 38:1137-1146. doi:10.1080/00927870902897947.