×

zbMATH — the first resource for mathematics

Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix. (English) Zbl 07268664
Summary: 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.
MSC:
68Q25 Analysis of algorithms and problem complexity
68W30 Symbolic computation and algebraic computation
15A21 Canonical forms, reductions, classification
05C22 Signed and weighted graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abarca, M.; Rivera, D., Graph theoretical and algorithmic characterizations of positive definite symmetric quasi-Cartan matrices, Fund. Inform., 149, 3, 241-261 (2016) · Zbl 1374.68235
[2] Assem, Ibrahim; Simson, Daniel; Skowro\'nski, Andrzej, Elements of the Representation Theory of Associative Algebras. Vol. 1, London Mathematical Society Student Texts 65, x+458 pp. (2006), Cambridge University Press, Cambridge · Zbl 1092.16001
[3] Barot, M.; de la Pe\~na, J. A., The Dynkin type of a non-negative unit form, Exposition. Math., 17, 4, 339-348 (1999) · Zbl 1073.15531
[4] Barot, Michael; Geiss, Christof; Zelevinsky, Andrei, Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (2), 73, 3, 545-564 (2006) · Zbl 1093.05070
[5] Bourbaki, N., \'El\'ements de math\'ematique. Fasc. XXXIV. Groupes et alg\`ebres de Lie. Chapitre IV: Groupes de Coxeter et syst\`emes de Tits. Chapitre V: Groupes engendr\'es par des r\'eflexions. Chapitre VI: syst\`emes de racines, Actualit\'es Scientifiques et Industrielles, No. 1337, 288 pp. (loose errata) pp. (1968), Hermann, Paris · Zbl 0186.33001
[6] Dlab, Vlastimil; Ringel, Claus Michael, Indecomposable Representations of Graphs and Algebras, Mem. Amer. Math. Soc., 6, 173, v+57 pp. (1976) · Zbl 0332.16015
[7] Gabriel, P.; Ro\u\iter, A. V., Representations of finite-dimensional algebras. Algebra, VIII, Encyclopaedia Math. Sci. 73, 1-177 (1992), Springer, Berlin · Zbl 0839.16001
[8] Happel, Dieter; Seidel, Uwe, Piecewise hereditary Nakayama algebras, Algebr. Represent. Theory, 13, 6, 693-704 (2010) · Zbl 1217.16015
[9] Humphreys, James E., Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics 9, xii+171 pp. (1978), Springer-Verlag, New York-Berlin · Zbl 0447.17001
[10] Kac, Victor G., Infinite-Dimensional Lie Algebras, xxii+400 pp. (1990), Cambridge University Press, Cambridge · Zbl 0716.17022
[11] Kasjan, Stanis\l aw; Simson, Daniel, Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fund. Inform., 139, 3, 249-275 (2015) · Zbl 1335.05146
[12] Kasjan, Stanis\l aw; Simson, Daniel, Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, Fund. Inform., 139, 2, 153-184 (2015) · Zbl 1335.05144
[13] Kosakowska, Justyna, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform., 119, 2, 149-162 (2012) · Zbl 1247.05241
[14] Kussin, Dirk; Lenzing, Helmut; Meltzer, Hagen, Triangle singularities, ADE-chains, and weighted projective lines, Adv. Math., 237, 194-251 (2013) · Zbl 1273.14075
[15] Makuracki, Bartosz; Mr\'oz, Andrzej, Root systems and inflations of non-negative quasi-Cartan matrices, Linear Algebra Appl., 580, 128-165 (2019) · Zbl 1423.15013
[16] Makuracki, Bartosz; Simson, Daniel, A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm, Discrete Appl. Math., 253, 25-36 (2019) · Zbl 1401.05137
[17] Makuracki, Bartosz; Simson, Daniel; Zyglarski, B\l a\.zej, Inflation algorithm for Cox-regular positive edge-bipartite graphs with loops, Fund. Inform., 153, 4, 367-398 (2017) · Zbl 1377.05078
[18] CIG A. Mr\'oz, \newblock Bigraph Congruences, \newblock Maple packages, documentation, 2015-2019, \newblock \urlhttp://www.mat.umk.pl/ amroz/projects/BigraphCongruences.zip.
[19] Mr\'oz, Andrzej, Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited, Fund. Inform., 146, 2, 121-144 (2016) · Zbl 1367.05106
[20] Mr\'oz, Andrzej, Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study, Fund. Inform., 146, 2, 145-177 (2016) · Zbl 1367.05107
[21] Msynasc2016 A. Mr\'oz, \newblock Effective nondeterministic positive definiteness test for unidiagonal integral matrices, \newblock 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2016, Timisoara, Romania), IEEE Comp. Soc., 2016, pp. 65-71.
[22] Mr\'oz, Andrzej; de la Pe\~na, Jos\'e Antonio, Periodicity in bilinear lattices and the Coxeter formalism, Linear Algebra Appl., 493, 227-260 (2016) · Zbl 1329.15054
[23] Ovsienko S. A. Ovsienko, \newblock Integral weakly positive forms, \newblock Schur Matrix Problems and Quadratic Forms, preprint 78.25, Inst. Mat. Akad. Nauk USSR, Kiev (1978), 3-17.
[24] P\'erez, Claudia; Abarca, Mario; Rivera, Daniel, Cubic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix, Fund. Inform., 158, 4, 369-384 (2018) · Zbl 1442.65082
[25] P\'erez, Claudia; Rivera, Daniel, Graphical characterization of positive definite non symmetric quasi-Cartan matrices, Discrete Math., 341, 5, 1215-1224 (2018) · Zbl 1397.05103
[26] PR.LAA2019 C. P\'erez and D. Rivera, \emph Serre type relations for complex semisimple Lie algebras associated to positive definite quasi-Cartan matrices, Linear Algebra Appl. <span class=”textbf”>5</span>67 (2019), 14-44. · Zbl 07060475
[27] Ringel, Claus Michael, The spectral radius of the Coxeter transformations for a generalized Cartan matrix, Math. Ann., 300, 2, 331-339 (1994) · Zbl 0819.15008
[28] Simson, Daniel, Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra, 215, 1, 13-34 (2011) · Zbl 1202.15030
[29] Simson, Daniel, A Coxeter-Gram classification of positive simply laced edge-bipartite graphs, SIAM J. Discrete Math., 27, 2, 827-854 (2013) · Zbl 1272.05072
[30] Simson, Daniel, Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups, Fund. Inform., 145, 1, 49-80 (2016) · Zbl 1371.05116
[31] Simson, Daniel, A Coxeter spectral classification of positive edge-bipartite graphs I. Dynkin types \(\mathcal{B}_n, \mathcal{C}_n, \mathcal{F}_4, \mathcal{G}_2, \mathbb{E}_6, \mathbb{E}_7, \mathbb{E}_8\), Linear Algebra Appl., 557, 105-133 (2018) · Zbl 1396.05049
[32] Simson, Daniel, Symbolic computation of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops, Linear Algebra Appl., 573, 90-143 (2019) · Zbl 1411.05108
[33] Simson, Daniel, A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices, Linear Algebra Appl., 586, 190-238 (2020) · Zbl 1429.05133
[34] Simson, Daniel; Zaj\polhk ac, Katarzyna, Inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two, Linear Algebra Appl., 524, 109-152 (2017) · Zbl 1361.05061
[35] von H\"ohne, Hans-Joachim, On weakly positive unit forms, Comment. Math. Helv., 63, 2, 312-336 (1988) · Zbl 0662.15014
[36] Zajac.sub2019 K. Zaj\polhk ac, \emph 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.
[37] Zaj\polhk ac, Katarzyna, On the structure of loop-free non-negative edge-bipartite graphs, Linear Algebra Appl., 579, 262-283 (2019) · Zbl 1419.05101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.