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

Makuracki, Bartosz; Mróz, Andrzej

doi:10.1090/mcom/3559

Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix
HTML articles powered by AMS MathViewer

by Bartosz Makuracki and Andrzej Mróz HTML | PDF

Math. Comp. 90 (2021), 389-412 Request permission

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

M. Abarca and D. Rivera, Graph theoretical and algorithmic characterizations of positive definite symmetric quasi-Cartan matrices, Fund. Inform. 149 (2016), no. 3, 241–261. MR 3595017, DOI 10.3233/FI-2016-1448
Ibrahim Assem, Daniel Simson, and Andrzej Skowroński, Elements of the representation theory of associative algebras. Vol. 1, London Mathematical Society Student Texts, vol. 65, Cambridge University Press, Cambridge, 2006. Techniques of representation theory. MR 2197389, DOI 10.1017/CBO9780511614309
M. Barot and J. A. de la Peña, The Dynkin type of a non-negative unit form, Exposition. Math. 17 (1999), no. 4, 339–348. MR 1734251
Michael Barot, Christof Geiss, and Andrei Zelevinsky, Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (2) 73 (2006), no. 3, 545–564. MR 2241966, DOI 10.1112/S0024610706022769
N. Bourbaki, Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines, Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1337, Hermann, Paris, 1968 (French). MR 0240238
Vlastimil Dlab and Claus Michael Ringel, Indecomposable representations of graphs and algebras, Mem. Amer. Math. Soc. 6 (1976), no. 173, v+57. MR 447344, DOI 10.1090/memo/0173
P. Gabriel and A. V. Roĭter, Representations of finite-dimensional algebras, Algebra, VIII, Encyclopaedia Math. Sci., vol. 73, Springer, Berlin, 1992, pp. 1–177. With a chapter by B. Keller. MR 1239447
Dieter Happel and Uwe Seidel, Piecewise hereditary Nakayama algebras, Algebr. Represent. Theory 13 (2010), no. 6, 693–704. MR 2736030, DOI 10.1007/s10468-009-9169-y
James E. Humphreys, Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, vol. 9, Springer-Verlag, New York-Berlin, 1978. Second printing, revised. MR 499562
Victor G. Kac, Infinite-dimensional Lie algebras, 3rd ed., Cambridge University Press, Cambridge, 1990. MR 1104219, DOI 10.1017/CBO9780511626234
Stanisław Kasjan and Daniel Simson, Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fund. Inform. 139 (2015), no. 3, 249–275. MR 3383587, DOI 10.3233/FI-2015-1234
Stanisław Kasjan and Daniel Simson, Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, Fund. Inform. 139 (2015), no. 2, 153–184. MR 3383583, DOI 10.3233/FI-2015-1230
Justyna Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 119 (2012), no. 2, 149–162. MR 2977486, DOI 10.3233/FI-2012-731
Dirk Kussin, Helmut Lenzing, and Hagen Meltzer, Triangle singularities, ADE-chains, and weighted projective lines, Adv. Math. 237 (2013), 194–251. MR 3028577, DOI 10.1016/j.aim.2013.01.006
Bartosz Makuracki and Andrzej Mróz, Root systems and inflations of non-negative quasi-Cartan matrices, Linear Algebra Appl. 580 (2019), 128–165. MR 3979176, DOI 10.1016/j.laa.2019.06.006
Bartosz Makuracki and Daniel Simson, A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm, Discrete Appl. Math. 253 (2019), 25–36. MR 3906726, DOI 10.1016/j.dam.2017.10.033
Bartosz Makuracki, Daniel Simson, and Błażej Zyglarski, Inflation algorithm for Cox-regular positive edge-bipartite graphs with loops, Fund. Inform. 153 (2017), no. 4, 367–398. MR 3684797, DOI 10.3233/FI-2017-1545
A. Mróz, Bigraph Congruences, Maple packages, documentation, 2015-2019, http://www.mat.umk.pl/~amroz/projects/BigraphCongruences.zip.
Andrzej Mróz, Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited, Fund. Inform. 146 (2016), no. 2, 121–144. MR 3552385, DOI 10.3233/FI-2016-1377
Andrzej Mróz, Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study, Fund. Inform. 146 (2016), no. 2, 145–177. MR 3552386, DOI 10.3233/FI-2016-1378
A. Mróz, Effective nondeterministic positive definiteness test for unidiagonal integral matrices, 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2016, Timisoara, Romania), IEEE Comp. Soc., 2016, pp. 65–71.
Andrzej Mróz and José Antonio de la Peña, Periodicity in bilinear lattices and the Coxeter formalism, Linear Algebra Appl. 493 (2016), 227–260. MR 3452736, DOI 10.1016/j.laa.2015.11.021
S. A. Ovsienko, Integral weakly positive forms, Schur Matrix Problems and Quadratic Forms, preprint 78.25, Inst. Mat. Akad. Nauk USSR, Kiev (1978), 3–17.
Claudia Pérez, Mario Abarca, and Daniel Rivera, Cubic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix, Fund. Inform. 158 (2018), no. 4, 369–384. MR 3767124, DOI 10.3233/fi-2018-1653
Claudia Pérez and Daniel Rivera, Graphical characterization of positive definite non symmetric quasi-Cartan matrices, Discrete Math. 341 (2018), no. 5, 1215–1224. MR 3777036, DOI 10.1016/j.disc.2018.01.013
C. Pérez and D. Rivera, Serre type relations for complex semisimple Lie algebras associated to positive definite quasi-Cartan matrices, Linear Algebra Appl. 567 (2019), 14–44.
Claus Michael Ringel, The spectral radius of the Coxeter transformations for a generalized Cartan matrix, Math. Ann. 300 (1994), no. 2, 331–339. MR 1299066, DOI 10.1007/BF01450490
Daniel Simson, Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra 215 (2011), no. 1, 13–34. MR 2678696, DOI 10.1016/j.jpaa.2010.02.029
Daniel Simson, A Coxeter-Gram classification of positive simply laced edge-bipartite graphs, SIAM J. Discrete Math. 27 (2013), no. 2, 827–854. MR 3048204, DOI 10.1137/110843721
Daniel Simson, Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups, Fund. Inform. 145 (2016), no. 1, 49–80. MR 3501055, DOI 10.3233/FI-2016-1346
Daniel Simson, A Coxeter spectral classification of positive edge-bipartite graphs I. Dynkin types $\mathcal {B}_n$, $\mathcal {C}_n$, $\mathcal {F}_4$, $\mathcal {G}_2$, $\Bbb {E}_6$, $\Bbb {E}_7$, $\Bbb {E}_8$, Linear Algebra Appl. 557 (2018), 105–133. MR 3848264, DOI 10.1016/j.laa.2018.07.013
Daniel Simson, Symbolic computation of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops, Linear Algebra Appl. 573 (2019), 90–143. MR 3933293, DOI 10.1016/j.laa.2019.02.023
Daniel Simson, A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices, Linear Algebra Appl. 586 (2020), 190–238. MR 4024974, DOI 10.1016/j.laa.2019.10.015
Daniel Simson and Katarzyna Zając, Inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two, Linear Algebra Appl. 524 (2017), 109–152. MR 3630181, DOI 10.1016/j.laa.2017.02.021
Hans-Joachim von Höhne, On weakly positive unit forms, Comment. Math. Helv. 63 (1988), no. 2, 312–336. MR 948786, DOI 10.1007/BF02566771
K. Zając, On polynomial time inflation algorithm for loop-free non-negative edge-bipartite graphs, Discrete Appl. Math., available online, doi: 10.1016/j.dam.2019.12.002, 2019.
Katarzyna Zając, On the structure of loop-free non-negative edge-bipartite graphs, Linear Algebra Appl. 579 (2019), 262–283. MR 3959735, DOI 10.1016/j.laa.2019.06.002