×

A Coxeter spectral classification of positive edge-bipartite graphs. II: Dynkin type \(\mathbb{D}_n\). (English) Zbl 1459.05113

Summary: We continue the Coxeter spectral study of finite positive edge-bipartite signed (multi)graphs \(\Delta\) (bigraphs, for short), with \(n\geq 2\) vertices started in [the author, SIAM J. Discrete Math. 27, No. 2, 827–854 (2013; Zbl 1272.05072)] and developed in [the author, Linear Algebra Appl. 557, 105–133 (2018; Zbl 1396.05049)]. We do it by means of the non-symmetric Gram matrix \(\check{G}_{\Delta}\in \mathbb{M}_n(\mathbb{Z})\) defining \(\Delta\), its Gram quadratic form \(q_{\Delta}:\mathbb{Z}^n\to\mathbb{Z}\), \(v\mapsto v\cdot\check{G}_{\Delta}\cdot v^{tr}\) (that is positive definite, by definition), the complex spectrum \(\operatorname{specc}_{\Delta}\subset\mathcal{S}^1:=\{z\in\mathbb{C},|z|=1\}\) of the Coxeter matrix \(\operatorname{Cox}_{\Delta}:=-\check{G}_{\Delta}\cdot \check{G}_{\Delta}^{-tr}\in\mathbb{M}_n(\mathbb{Z})\), called the Coxeter spectrum of \(\Delta\), and the Coxeter polynomial \(\operatorname{cox}_{\Delta}(t):=\det(t\cdot E-\operatorname{Cox}_{\Delta})\in\mathbb{Z} [t]\). One of the aims of the Coxeter spectral analysis is to classify the connected bigraphs \(\Delta\) with \(n\geq 2\) vertices up to the \(\ell\)-weak Gram \(\mathbb{Z}\)-congruence \(\Delta\sim_{\ell\mathbb{Z}} \Delta^\prime\) and up to the strong Gram \(\mathbb{Z}\)-congruence \(\Delta\approx_{\mathbb{Z}}\Delta^\prime\), where \(\Delta\sim_{\ell\mathbb{Z}}\Delta^\prime\) (resp. \(\Delta\approx_{\mathbb{Z}}\Delta^\prime)\) means that \(\det \check{G}_{\Delta}=\det \check{G}_{\Delta^\prime}\) and \(G_{\Delta^\prime}=B^{tr}\cdot G_{\Delta}\cdot B\) (resp. \(\check{G}_{\Delta^\prime}=B^{tr}\cdot \check{G}_{\Delta}\cdot B)\), for some \(B\in\mathbb{M}_n(\mathbb{Z})\) with \(\det B=\pm 1\), where \(G_{\Delta}:=\frac{1}{2}[\check{G}_{\Delta}+\check{G}_{\Delta}^{tr}]\in \mathbb{M}_n(\frac{1}{2}\mathbb{Z})\).
Here we study connected signed simple graphs \(\Delta\), with \(n\geq 2\) vertices, that are positive, i.e., the symmetric Gram matrix \(G_{\Delta}\in\mathbb{M}_n(\frac{1}{2}\mathbb{Z})\) of \(\Delta\) is positive definite. It is known that every such a signed graph is \(\ell\)-weak Gram \(\mathbb{Z}\)-congruent with a unique simply laced Dynkin graph \(\operatorname{Dyn}_{\Delta} \in\{\mathbb{A}_n,\mathbb{D}_n,n\geq 4,\mathbb{E}_6, \mathbb{E}_7,\mathbb{E}_8\}\), called the Dynkin type of \(\Delta\). A classification up to the strong Gram \(\mathbb{Z}\)-congruence \(\Delta\approx_{\mathbb{Z}}\Delta^\prime\) is still an open problem and only partial results are known. In this paper, we obtain such a classification for the positive signed simple graphs \(\Delta\) of Dynkin type \(\mathbb{D}_n\) by means of the family of the signed graphs \(\mathcal{D}_n^{(1)}=\mathbb{D}_n, \mathcal{D}_n^{(2)},\dots,\mathcal{D}_n^{(r_n)}\) constructed in Section 2, for any \(n\geq 4\), where \(r_n=\llcorner n/2\lrcorner\). More precisely, we prove that any connected signed simple graph of Dynkin type \(\mathbb{D}_n\), with \(n\geq 4\) vertices, is strongly \(\mathbb{Z}\)-congruent with a signed graph \(\mathcal{D}_n^{(s)}\), for some \(s\leq r_n\), and its Coxeter polynomial \(\operatorname{cox}_{\Delta}(t)\) is of the form \((t^s+1)(t^{n-s}+1)\). We do it by a matrix morsification type reduction to the classification of the conjugacy classes in the integral orthogonal group \(\operatorname{O}(n, \mathbb{Z})\) of the integer orthogonal matrices \(C\), with \(\det(E-C)=4\).

MSC:

05C22 Signed and weighted graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
11E04 Quadratic forms over general fields
15A63 Quadratic and bilinear forms, inner products
68R05 Combinatorics in computer science
68W30 Symbolic computation and algebraic computation

Software:

TUBULAR
Full Text: DOI

References:

[1] Abarca, M.; Rivera, D., Theoretical and algorithmic characterizations of positive definite symmetric quasi-Cartan matrices, Fundam. Inform., 149, 241-261 (2016) · Zbl 1374.68235
[2] Alves, J.; Castongay, D.; Brüstle, T., A polynomial recognition of unit forms using graph-based strategies, Discrete Appl. Math., 253, 61-72 (2019) · Zbl 1404.16011
[3] Assem, I.; Simson, D.; Skowroński, A., Elements of the Representation Theory of Associative Algebras. Techniques of Representation Theory, London Math. Soc. Student Texts, vol. 65 (2006), Cambridge Univ. Press: Cambridge Univ. Press Cambridge-New York · Zbl 1092.16001
[4] Barot, M., A characterization of positive unit forms, part II, Bol. Soc. Mat. Mexicana (3), 7, 13-22 (2001) · Zbl 1012.11056
[5] Barot, M.; Geiss, C.; Zelevinsky, A., Cluster algebras of finite type and positive symmetrizable matrices, J. Lond. Math. Soc., 73, 545-564 (2006) · Zbl 1093.05070
[6] Barot, M.; de la Peña, J. A., The Dynkin type of a non-negative unit form, Expo. Math., 17, 339-348 (1999) · Zbl 1073.15531
[7] Bocian, R.; Felisiak, M.; Simson, D., Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups, J. Comput. Appl. Math., 259, 815-827 (2014) · Zbl 1314.05196
[8] Bourbaki, N., Grupes et algébres de Lie, Ch. IV-VI (1960), Hermann & Co.: Hermann & Co. Paris · Zbl 0199.35203
[9] Brüstle, T.; Dupont, G.; Perotin, M., On maximal Green sequences, Int. Math. Res. Not., 2014, 16, 4547-4586 (2014) · Zbl 1346.16009
[10] Cameron, P. J.; Seidel, J. J.; Tsaranov, S. V., Signed graphs, root lattices and Coxeter groups, J. Algebra, 164, 173-209 (1994) · Zbl 0802.05043
[11] Dowbor, P.; Hübner, T., A computer algebra approach to sheaves over weighted projective lines, (Progress Math., vol. 173 (1999), Birkhäuser), 187-200 · Zbl 0951.16019
[12] Dowbor, P.; Simson, D., Quasi-Artin species and rings of finite representation type, J. Algebra, 63, 435-443 (1980) · Zbl 0428.16031
[13] Felisiak, M.; Simson, D., Applications of matrix morsifications to Coxeter spectral study of loop-free edge-bipartite graphs, Discrete Appl. Math., 192, 49-64 (2015) · Zbl 1319.05142
[14] Felisiak, M., Algorytmy numeryczne w spektralnej analizie Coxetera bigrafów (November 2017), University of Warsaw, Doctoral Thesis
[15] Gąsiorek, M.; Simson, D., A computation of positive one-peak posets that are Tits-sincere, Colloq. Math., 127, 83-103 (2012) · Zbl 1260.06005
[16] Gąsiorek, M.; Simson, D.; Zając, K., On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams, Eur. J. Comb., 48, 127-142 (2015) · Zbl 1318.06004
[17] Gąsiorek, M.; Simson, D.; Zając, K., A Gram classification of non-negative corank-two loop-free edge-bipartite graphs, Linear Algebra Appl., 500, 88-118 (2016) · Zbl 1334.05053
[18] Gąsiorek, M.; Zając, K., On algorithmic study of non-negative posets of corank at most two and their Coxeter-Dynkin types, Fundam. Inform., 139, 347-367 (2015) · Zbl 1335.05171
[19] Humphreys, J. E., Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics, vol. 9 (1972), Springer-Verlag: Springer-Verlag New York, Heidelberg, Berlin · Zbl 0254.17004
[20] Kasjan, S.; Simson, D., Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems, Fundam. Inform., 139, 153-184 (2015) · Zbl 1335.05144
[21] Kasjan, S.; Simson, D., Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, II. Application to Coxeter spectral analysis, Fundam. Inform., 139, 185-209 (2015) · Zbl 1335.05145
[22] Kasjan, S.; Simson, D., Algorithms for isotropy groups of Cox-regular edge-bipartite graphs, Fundam. Inform., 139, 249-275 (2015) · Zbl 1335.05146
[23] Klemp, B.; Simson, D., Schurian sp-representation-finite right peak PI-rings and their indecomposable socle projective modules, J. Algebra, 131, 390-468 (1990) · Zbl 0729.16004
[24] Kosakowska, J., Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fundam. Inform., 119, 149-162 (2012) · Zbl 1247.05241
[25] Kronecker, L., Zwei Zätze über Gleichungen mit ganzzahligen Coefficienten, J. Reine Angew. Math., 105-108 (1857)
[26] Leites, D.; Lozhenchnyk, O., Inverses of Cartan matrices of Lie algebras and Lie superalgebras, Linear Algebra Appl., 583, 195-256 (2019) · Zbl 1464.17023
[27] Makuracki, B.; Mróz, A., Root systems and inflations of non-negative quasi-Cartan matrices, Linear Algebra Appl., 580, 128-165 (2019) · Zbl 1423.15013
[28] Makuracki, B.; Mróz, A., Quadratic algorithm to compute the Dynkin type of a positive definite quasi-Cartan matrix, Math. Comput., 90, 389-412 (2021) · Zbl 1468.15019
[29] Makuracki, B.; Mróz, A., Coefficients of non-negative quasi-Cartan matrices, their symmetrizers and Gram matrices, Discrete Appl. Math. (2020), in press
[30] Makuracki, B.; Simson, D.; Zyglarski, B., Inflation algorithm for Cox-regular positive edge-bipartite graphs with loops, Fundam. Inform., 153, 367-398 (2017) · Zbl 1377.05078
[31] Makuracki, B.; Simson, D., A Gram classification of principal Cox-regular edge-bipartite graphs via inflation algorithm, Discrete Appl. Math., 253, 25-36 (2019) · Zbl 1401.05137
[32] Marczak, G.; Polak, A.; Simson, D., P-critical integral quadratic forms and positive unit forms. An algorithmic approach, Linear Algebra Appl., 433, 1873-1888 (2010) · Zbl 1206.15020
[33] Mróz, A., Congruences of edge-bipartite graphs with applications to Grothendieck group recognition I. Inflation algorithm revisited, Fundam. Inform., 146, 121-144 (2016) · Zbl 1367.05106
[34] Mróz, A., Congruences of edge-bipartite graphs with applications to Grothendieck group recognition II. Coxeter type study, Fundam. Inform., 146, 145-177 (2016) · Zbl 1367.05107
[35] Mróz, A.; de la Peña, J. A., Tubes in derived categories and cyclotomic factors of the Coxeter polynomial of an algebra, J. Algebra, 420, 242-260 (2014) · Zbl 1318.16017
[36] Mróz, A.; de la Peña, J. A., Periodicity in bilinear lattices and the Coxeter formalism, Linear Algebra Appl., 493, 227-260 (2016) · Zbl 1329.15054
[37] Ovsienko, S. A., Integral weakly positive forms, (Schur Matrix Problems and Quadratic Forms (1978), Inst. Mat. Akad. Nauk USSR), 3-17, (in Russian), Preprint 78.25
[38] Perez, C.; Abarca, M.; Rivera, D., Cubic algorithm to compute the Dynkin type of positive definite quasi-Cartan matrices, Fundam. Inform., 158, 369-384 (2018) · Zbl 1442.65082
[39] Perez, C.; Rivera, D., Graphical characterization of positive definite non-symmetric quasi-Cartan matrices, Discrete Math., 341, 1215-1224 (2018) · Zbl 1397.05103
[40] Perez, C.; Rivera, D., Serre type relations for complex semisimple Lie algebras associated to positive definite quasi-Cartan matrices, Linear Algebra Appl., 567, 14-44 (2019) · Zbl 1462.17016
[41] Simson, D., A reduction functor, tameness and Tits form for a class of orders, J. Algebra, 174, 430-452 (1995) · Zbl 0831.16011
[42] Simson, D., Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra, 215, 13-34 (2011) · Zbl 1202.15030
[43] Simson, D., Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fundam. Inform., 109, 425-462 (2011) · Zbl 1257.11109
[44] Simson, D., A Coxeter-Gram classification of simply laced edge-bipartite graphs, SIAM J. Discrete Math., 27, 827-854 (2013) · Zbl 1272.05072
[45] Simson, D., Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fundam. Inform., 123, 447-490 (2013) · Zbl 1290.68138
[46] Simson, D., A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fundam. Inform., 124, 309-338 (2013) · Zbl 1269.05073
[47] Simson, D., Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, I. A Gram classification, Fundam. Inform., 145, 19-48 (2016) · Zbl 1371.05115
[48] Simson, D., Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edge-bipartite graphs, II. Isotropy mini-groups, Fundam. Inform., 145, 49-80 (2016) · Zbl 1371.05116
[49] Simson, D., 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
[50] Simson, D., Symbolic computations of strong Gram congruences for Cox-regular positive edge-bipartite graphs with loops, Linear Algebra Appl., 573, 90-143 (2019) · Zbl 1411.05108
[51] Simson, D., A computational technique in Coxeter spectral study of symmetrizable integer Cartan matrices, Linear Algebra Appl., 586, 190-238 (2020) · Zbl 1429.05133
[52] Simson, D.; Zając, K., 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
[53] Simson, D.; Zając, K., On mesh geometries of root Coxeter orbits and mesh algorithms for corank two edge-bipartite signed graphs, Linear Algebra Appl., 610, 698-765 (2021) · Zbl 1460.05080
[54] Zając, K., Numeric algorithms for corank two edge-bipartite graphs and their mesh geometries of roots, Fundam. Inform., 152, 185-222 (2017) · Zbl 1375.05167
[55] Zając, K., On polynomial time inflation algorithm for loop-free non-negative edge-bipartite graphs, Discrete Appl. Math., 283, 28-43 (2020) · Zbl 1442.05228
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.