{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T04:49:26Z","timestamp":1776833366849,"version":"3.51.2"},"reference-count":37,"publisher":"American Mathematical Society (AMS)","issue":"327","license":[{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    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\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A element-of double-struck upper M Subscript n Baseline left-parenthesis double-struck upper Z right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:msub>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"double-struck\">M<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msub>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">Z<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">A\\in \\mathbb {M}_n(\\mathbb {Z})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper Z\">\n                        <mml:semantics>\n                          <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                            <mml:mi mathvariant=\"double-struck\">Z<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {Z}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -equivalent with the Cartan matrix of a Dynkin diagram, called the Dynkin type of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A\">\n                        <mml:semantics>\n                          <mml:mi>A<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">A<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . We present a symbolic, graph-theoretic algorithm to compute the Dynkin type of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper A\">\n                        <mml:semantics>\n                          <mml:mi>A<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">A<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , of the pessimistic arithmetic (word) complexity\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script upper O left-parenthesis n squared right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi class=\"MJX-tex-caligraphic\" mathvariant=\"script\">O<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathcal {O}(n^2)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , 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.\n                  <\/p>","DOI":"10.1090\/mcom\/3559","type":"journal-article","created":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T14:42:12Z","timestamp":1589985732000},"page":"389-412","source":"Crossref","is-referenced-by-count":7,"title":["Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix"],"prefix":"10.1090","volume":"90","author":[{"given":"Bartosz","family":"Makuracki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Mr\u00f3z","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2020,8,1]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"241","DOI":"10.3233\/FI-2016-1448","article-title":"Graph theoretical and algorithmic characterizations of positive definite symmetric quasi-Cartan matrices","volume":"149","author":"Abarca, M.","year":"2016","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"key":"2","series-title":"London Mathematical Society Student Texts","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511614309","volume-title":"Elements of the representation theory of associative algebras. Vol. 1","volume":"65","author":"Assem, Ibrahim","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521584234"},{"issue":"4","key":"3","first-page":"339","article-title":"The Dynkin type of a non-negative unit form","volume":"17","author":"Barot, M.","year":"1999","journal-title":"Exposition. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0723-0869","issn-type":"print"},{"issue":"3","key":"4","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1112\/S0024610706022769","article-title":"Cluster algebras of finite type and positive symmetrizable matrices","volume":"73","author":"Barot, Michael","year":"2006","journal-title":"J. London Math. Soc. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0024-6107","issn-type":"print"},{"key":"5","series-title":"Actualit\\'{e}s Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1337","volume-title":"\\'{E}l\\'{e}ments de math\\'{e}matique. Fasc. XXXIV. Groupes et alg\\`ebres de Lie. Chapitre IV: Groupes de Coxeter et syst\\`emes de Tits. Chapitre V: Groupes engendr\\'{e}s par des r\\'{e}flexions. Chapitre VI: syst\\`emes de racines","author":"Bourbaki, N.","year":"1968"},{"issue":"173","key":"6","doi-asserted-by":"publisher","first-page":"v+57","DOI":"10.1090\/memo\/0173","article-title":"Indecomposable representations of graphs and algebras","volume":"6","author":"Dlab, Vlastimil","year":"1976","journal-title":"Mem. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-9266","issn-type":"print"},{"key":"7","isbn-type":"print","first-page":"1","article-title":"Representations of finite-dimensional algebras","author":"Gabriel, P.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3540537325"},{"issue":"6","key":"8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/s10468-009-9169-y","article-title":"Piecewise hereditary Nakayama algebras","volume":"13","author":"Happel, Dieter","year":"2010","journal-title":"Algebr. Represent. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1386-923X","issn-type":"print"},{"key":"9","series-title":"Graduate Texts in Mathematics","isbn-type":"print","volume-title":"Introduction to Lie algebras and representation theory","volume":"9","author":"Humphreys, James E.","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0387900535"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626234","volume-title":"Infinite-dimensional Lie algebras","author":"Kac, Victor G.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0521372151","edition":"3"},{"issue":"3","key":"11","doi-asserted-by":"publisher","first-page":"249","DOI":"10.3233\/FI-2015-1234","article-title":"Algorithms for isotropy groups of Cox-regular edge-bipartite graphs","volume":"139","author":"Kasjan, Stanis\u0142aw","year":"2015","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"153","DOI":"10.3233\/FI-2015-1230","article-title":"Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems","volume":"139","author":"Kasjan, Stanis\u0142aw","year":"2015","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"issue":"2","key":"13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.3233\/fi-2012-731","article-title":"Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms","volume":"119","author":"Kosakowska, Justyna","year":"2012","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"key":"14","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1016\/j.aim.2013.01.006","article-title":"Triangle singularities, ADE-chains, and weighted projective lines","volume":"237","author":"Kussin, Dirk","year":"2013","journal-title":"Adv. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-8708","issn-type":"print"},{"key":"15","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.laa.2019.06.006","article-title":"Root systems and inflations of non-negative quasi-Cartan matrices","volume":"580","author":"Makuracki, Bartosz","year":"2019","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2017.10.033","article-title":"A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm","volume":"253","author":"Makuracki, Bartosz","year":"2019","journal-title":"Discrete Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0166-218X","issn-type":"print"},{"issue":"4","key":"17","doi-asserted-by":"publisher","first-page":"367","DOI":"10.3233\/FI-2017-1545","article-title":"Inflation algorithm for Cox-regular positive edge-bipartite graphs with loops","volume":"153","author":"Makuracki, Bartosz","year":"2017","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"key":"18","unstructured":"A. Mr\u00f3z, Bigraph Congruences, Maple packages, documentation, 2015-2019, \\url{http:\/\/www.mat.umk.pl\/ amroz\/projects\/BigraphCongruences.zip}."},{"issue":"2","key":"19","doi-asserted-by":"publisher","first-page":"121","DOI":"10.3233\/FI-2016-1377","article-title":"Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited","volume":"146","author":"Mr\u00f3z, Andrzej","year":"2016","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"issue":"2","key":"20","doi-asserted-by":"publisher","first-page":"145","DOI":"10.3233\/FI-2016-1378","article-title":"Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study","volume":"146","author":"Mr\u00f3z, Andrzej","year":"2016","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"A. Mr\u00f3z, 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\u201371.","DOI":"10.1109\/SYNASC.2016.023"},{"key":"22","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/j.laa.2015.11.021","article-title":"Periodicity in bilinear lattices and the Coxeter formalism","volume":"493","author":"Mr\u00f3z, Andrzej","year":"2016","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"23","unstructured":"S. A. Ovsienko, Integral weakly positive forms, Schur Matrix Problems and Quadratic Forms, preprint 78.25, Inst. Mat. Akad. Nauk USSR, Kiev (1978), 3\u201317."},{"issue":"4","key":"24","doi-asserted-by":"publisher","first-page":"369","DOI":"10.3233\/fi-2018-1653","article-title":"Cubic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix","volume":"158","author":"P\u00e9rez, Claudia","year":"2018","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"issue":"5","key":"25","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1016\/j.disc.2018.01.013","article-title":"Graphical characterization of positive definite non symmetric quasi-Cartan matrices","volume":"341","author":"P\u00e9rez, Claudia","year":"2018","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"26","doi-asserted-by":"crossref","unstructured":"C. P\u00e9rez and D. Rivera, Serre type relations for complex semisimple Lie algebras associated to positive definite quasi-Cartan matrices, Linear Algebra Appl. 567 (2019), 14\u201344.","DOI":"10.1016\/j.laa.2018.12.032"},{"issue":"2","key":"27","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01450490","article-title":"The spectral radius of the Coxeter transformations for a generalized Cartan matrix","volume":"300","author":"Ringel, Claus Michael","year":"1994","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"issue":"1","key":"28","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.jpaa.2010.02.029","article-title":"Mesh geometries of root orbits of integral quadratic forms","volume":"215","author":"Simson, Daniel","year":"2011","journal-title":"J. Pure Appl. Algebra","ISSN":"https:\/\/id.crossref.org\/issn\/0022-4049","issn-type":"print"},{"issue":"2","key":"29","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1137\/110843721","article-title":"A Coxeter-Gram classification of positive simply laced edge-bipartite graphs","volume":"27","author":"Simson, Daniel","year":"2013","journal-title":"SIAM J. Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4801","issn-type":"print"},{"issue":"1","key":"30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.3233\/FI-2016-1346","article-title":"Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups","volume":"145","author":"Simson, Daniel","year":"2016","journal-title":"Fund. Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0169-2968","issn-type":"print"},{"key":"31","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.laa.2018.07.013","article-title":"A Coxeter spectral classification of positive edge-bipartite graphs I. Dynkin types \u212c_{\ud835\udcc3}, \ud835\udc9e_{\ud835\udcc3}, \u2131\u2084, \ud835\udca2\u2082, \ud835\udd3c\u2086, \ud835\udd3c\u2087, \ud835\udd3c\u2088","volume":"557","author":"Simson, Daniel","year":"2018","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"32","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.laa.2019.02.023","article-title":"Symbolic computation of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops","volume":"573","author":"Simson, Daniel","year":"2019","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"33","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.laa.2019.10.015","article-title":"A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices","volume":"586","author":"Simson, Daniel","year":"2020","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"34","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.laa.2017.02.021","article-title":"Inflation algorithm for loop-free non-negative edge-bipartite graphs of corank at least two","volume":"524","author":"Simson, Daniel","year":"2017","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"2","key":"35","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF02566771","article-title":"On weakly positive unit forms","volume":"63","author":"von H\u00f6hne, Hans-Joachim","year":"1988","journal-title":"Comment. Math. Helv.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-2571","issn-type":"print"},{"key":"36","doi-asserted-by":"crossref","unstructured":"K. Zaj\u0105c, 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.","DOI":"10.1016\/j.dam.2019.12.002"},{"key":"37","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/j.laa.2019.06.002","article-title":"On the structure of loop-free non-negative edge-bipartite graphs","volume":"579","author":"Zaj\u0105c, Katarzyna","year":"2019","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/earlyview\/#mcom3559\/.pdf","content-type":"unspecified","content-version":"am","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2021-90-327\/S0025-5718-2020-03559-5\/S0025-5718-2020-03559-5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T03:54:46Z","timestamp":1776830086000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2021-90-327\/S0025-5718-2020-03559-5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,1]]},"references-count":37,"journal-issue":{"issue":"327","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["S0025-5718-2020-03559-5"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3559","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2020,8,1]]}}}