Algorithmic computation of principal posets using Maple and Python

We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification problems. One of the main aims of the paper is to study finite posets I that are principal, i.e., the rational symmetric Gram matrix GI : = 1/2[CI+CItr] ∈ MI(Q) of I is positive semi-definite of...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автори:	Gasiorek, M., Simson, D., Zajac, K.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2014
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/152339
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Algorithmic computation of principal posets using Maple and Python / M. Gasiorek, D. Simson, K. Zajac // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 33–69. — Бібліогр.: 56 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-152339
record_format	dspace
spelling	irk-123456789-1523392019-06-11T01:25:16Z Algorithmic computation of principal posets using Maple and Python Gasiorek, M. Simson, D. Zajac, K. We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification problems. One of the main aims of the paper is to study finite posets I that are principal, i.e., the rational symmetric Gram matrix GI : = 1/2[CI+CItr] ∈ MI(Q) of I is positive semi-definite of corank one, where CI ∈ MI(Z) is the incidence matrix of I. With any such a connected poset I, we associate a simply laced Euclidean diagram DI ∈ {A˜n, D˜n, E˜₆, E˜₇, E˜₈}, the Coxeter matrix CoxI := −CI ⋅ C−trI, its complex Coxeter spectrum speccI, and a reduced Coxeter number cI. One of our aims is to show that the spectrum speccI of any such a poset I determines the incidence matrix CI (hence the poset I) uniquely, up to a Z-congruence. By computer calculations, we find a complete list of principal one-peak posets I (i.e., I has a unique maximal element) of cardinality ≤ 15, together with speccI, cI, the incidence defect ∂I : ZI → Z, and the Coxeter-Euclidean type DI. In case when DI ∈ {A˜n, D˜n, E˜₆, E˜₇, E˜₈} and n := \|I\| is relatively small, we show that given such a principal poset I, the incidence matrix CI is Z-congruent with the non-symmetric Gram matrix GˇDI of DI, speccI = speccDI and cˇI = cˇDI. Moreover, given a pair of principal posets I and J, with \|I\| = \|J\| ≤ 15, the matrices CI and CJ are Z-congruent if and only if speccI = speccJ. 2014 Article Algorithmic computation of principal posets using Maple and Python / M. Gasiorek, D. Simson, K. Zajac // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 33–69. — Бібліогр.: 56 назв. — англ. 1726-3255 2010 MSC:06A11, 15A63, 68R05, 68W30. http://dspace.nbuv.gov.ua/handle/123456789/152339 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification problems. One of the main aims of the paper is to study finite posets I that are principal, i.e., the rational symmetric Gram matrix GI : = 1/2[CI+CItr] ∈ MI(Q) of I is positive semi-definite of corank one, where CI ∈ MI(Z) is the incidence matrix of I. With any such a connected poset I, we associate a simply laced Euclidean diagram DI ∈ {A˜n, D˜n, E˜₆, E˜₇, E˜₈}, the Coxeter matrix CoxI := −CI ⋅ C−trI, its complex Coxeter spectrum speccI, and a reduced Coxeter number cI. One of our aims is to show that the spectrum speccI of any such a poset I determines the incidence matrix CI (hence the poset I) uniquely, up to a Z-congruence. By computer calculations, we find a complete list of principal one-peak posets I (i.e., I has a unique maximal element) of cardinality ≤ 15, together with speccI, cI, the incidence defect ∂I : ZI → Z, and the Coxeter-Euclidean type DI. In case when DI ∈ {A˜n, D˜n, E˜₆, E˜₇, E˜₈} and n := \|I\| is relatively small, we show that given such a principal poset I, the incidence matrix CI is Z-congruent with the non-symmetric Gram matrix GˇDI of DI, speccI = speccDI and cˇI = cˇDI. Moreover, given a pair of principal posets I and J, with \|I\| = \|J\| ≤ 15, the matrices CI and CJ are Z-congruent if and only if speccI = speccJ.
format	Article
author	Gasiorek, M. Simson, D. Zajac, K.
spellingShingle	Gasiorek, M. Simson, D. Zajac, K. Algorithmic computation of principal posets using Maple and Python Algebra and Discrete Mathematics
author_facet	Gasiorek, M. Simson, D. Zajac, K.
author_sort	Gasiorek, M.
title	Algorithmic computation of principal posets using Maple and Python
title_short	Algorithmic computation of principal posets using Maple and Python
title_full	Algorithmic computation of principal posets using Maple and Python
title_fullStr	Algorithmic computation of principal posets using Maple and Python
title_full_unstemmed	Algorithmic computation of principal posets using Maple and Python
title_sort	algorithmic computation of principal posets using maple and python
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2014
url	http://dspace.nbuv.gov.ua/handle/123456789/152339
citation_txt	Algorithmic computation of principal posets using Maple and Python / M. Gasiorek, D. Simson, K. Zajac // Algebra and Discrete Mathematics. — 2014. — Vol. 17, № 1. — С. 33–69. — Бібліогр.: 56 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT gasiorekm algorithmiccomputationofprincipalposetsusingmapleandpython AT simsond algorithmiccomputationofprincipalposetsusingmapleandpython AT zajack algorithmiccomputationofprincipalposetsusingmapleandpython
first_indexed	2025-07-13T02:51:25Z
last_indexed	2025-07-13T02:51:25Z
_version_	1837498460787441664
fulltext	Algebra and Discrete Mathematics RESEARCH ARTICLE Volume 17 (2014). Number 1. pp. 33 – 69 c© Journal “Algebra and Discrete Mathematics” Algorithmic computation of principal posets using Maple and Python Marcin Gąsiorek, Daniel Simson and Katarzyna Zając Abstract. We present symbolic and numerical algorithms for a computer search in the Coxeter spectral classification prob- lems. One of the main aims of the paper is to study finite posets I that are principal, i.e., the rational symmetric Gram matrix GI := 1 2 [CI + Ctr I ] ∈MI(Q) of I is positive semi-definite of corank one, where CI ∈MI(Z) is the incidence matrix of I. With any such a connected poset I, we associate a simply laced Euclidean diagram DI ∈ {Ãn, D̃n, Ẽ6, Ẽ7, Ẽ8}, the Coxeter matrix CoxI := −CI ·C −tr I , its complex Coxeter spectrum speccI , and a reduced Coxeter num- ber čI . One of our aims is to show that the spectrum speccI of any such a poset I determines the incidence matrix CI (hence the poset I) uniquely, up to a Z-congruence. By computer calculations, we find a complete list of principal one-peak posets I (i.e., I has a unique maximal element) of cardinality ≤ 15, together with speccI , čI , the incidence defect ∂I : ZI → Z, and the Coxeter-Euclidean type DI. In case when DI ∈ {Ãn, D̃n, Ẽ6, Ẽ7, Ẽ8} and n := \|I\| is relatively small, we show that given such a principal poset I, the incidence matrix CI is Z-congruent with the non-symmetric Gram matrix ǦDI of DI, speccI = speccDI and čI = čDI . Moreover, given a pair of principal posets I and J , with \|I\| = \|J \| ≤ 15, the matrices CI and CJ are Z-congruent if and only if speccI = speccJ . Supported by Polish Research Grant NCN 2011/03/B/ST1/00824. 2010 MSC: 06A11, 15A63, 68R05, 68W30. Key words and phrases: principal poset; edge-bipartite graph; unit quadratic form; computer algorithm; Gram matrix, Coxeter polynomial, Coxeter spectrum. 34 Algorithmic computation of principal posets 1. Introduction Throughout, we freely use the terminology and notation introduced in [45], [47], [50], [51]. We denote by N the set of non-negative integers, by Z the ring of integers, and by Q ⊂ R ⊂ C the field of the rational, the real, and the complex numbers, respectively. We view Zn, with n ≥ 1, as a free abelian group. By e1, . . . , en we denote the standard Z-basis of the group Zn. Given n ≥ 1, we denote by Mn(Z) the Z-algebra of all square n by n matrices A = [aij ], with aij ∈ Z, and by E ∈Mn(Z) the identity matrix. Given a finite set J , we denote by MJ(Z) the Z-algebra of all square J by J matrices. The group Gl(n,Z) := {A ∈Mn(Z), det A ∈ {−1, 1}} ⊆Mn(Z) is called the (integral) general linear group. We say that two square rational matrices A, A′ ∈Mn(Q) are Z-congruent (and denote by A ∼Z A′) if there exists a Z-invertible matrix B ∈ Gl(n,Z) such that A′ = Btr ·A ·B. By a poset J ≡ (J,�) we mean a finite partially ordered set J with respect to a partial order relation �. Following [43], J is called a one- peak poset if it has a unique maximal element ∗. Given a poset J , with m = \|J \|, we denote by CJ = [cij ] ∈MJ(Z) ≡Mm(Z) (1.1) the incidence matrix of J , with cij = 1, for all i � j, and cij = 0 otherwise. The rational matrix GJ := 1 2 [CJ + Ctr J ] ∈MJ(Q) ≡Mm(Q) (1.2) is called the symmetric Gram matrix of J . Following [50] and [51], we call the symmetric matrix AdJ := CJ + Ctr J − 2 · E the adjacency matrix of J , and PJ(t) = det(t · E −AdJ) ∈ Z[t], (1.3) the characteristic polynomial of the poset J . We say that the poset J is Z-bilinear equivalent to a poset J ′ (and we write J ≈Z J ′) if CJ ∼Z CJ ′ . We define J to be non-negative (resp. positive) if the rational symmet- ric Gram matrix GJ (1.2) is positive semi-definite (resp. positive definite). If J is connected and the symmetric Gram matrix GJ is positive semi- definite of rank \|J \| − 1, we call J a principal poset, see [47, Definition 2.1] and [51, Section 3]. In other words, J is principal if and only if the M. Gąsiorek, D. Simson, K. Zając 35 quadratic form qJ(x) = x · CJ · x tr is non-negative and the subgroup Ker qJ := {v ∈ ZJ ; qJ(v) = 0} of ZJ is infinite cyclic. Our study is inspired by important applications of the quadratic forms and edge-bipartite graphs in constructing linear algebra invariants that measure a geometric complexity of Nazarova-Roiter matrix problems over a field K and in the study of module categories and their derived categories, see the monographs [1], [11], [43], [53], and the articles [2]-[9], [12]-[24], [27], [29]-[34], [39]-[42], [45]-[52], and [54], [55]. In particular, our study is inspired by a well-known result of Drozd [10], by the Coxeter spectral analysis of loop-free edge-bipartite graphs developed in [50], and the Coxeter spectral classification technique of finite posets introduced in [44], [45], and [51], see also [26], [28], [36]-[38], and [56]. In the present paper we are mainly interested in the class of non- negative posets J ; in particular, in the class of principal posets. We study them by applying our recent results on the Coxeter spectral classification of loop-free edge-bipartite graphs defined in [50] (see also [51]) as follows. An edge-bipartite graph (bigraph, for short), with n≥2 vertices, is a pair ∆ = (∆0, ∆1 = ∆− 1 ⊔∆+ 1 ), where ∆0 = {a1, . . . , an} is a set of vertices and ∆1 is a finite set of edges such that \|∆− 1 (ai, aj)\| · \|∆ + 1 (ai, aj)\| = 0, for all ai 6= aj ∈ ∆0. Edges in ∆− 1 (ai, aj) and ∆+ 1 (ai, aj) are visualized as continuous ai ——– aj , and dotted ones ai - - - - aj , respectively. We say that ∆ is loop-free if ∆1(ai, ai) is empty, for all ai ∈ ∆0. We denote by UBigrn the set of all connected loop-free edge-bipartite graphs, with n ≥ 2 vertices. We view any finite graph ∆ = (∆0, ∆1) as an edge-bipartite graph by setting ∆− 1 (ai, aj) = ∆1(ai, aj) and ∆+ 1 (ai, aj) = ∅, for ai, aj ∈ ∆0. A non-symmetric Gram matrix of ∆ ∈ UBigrn is the matrix Ǧ∆ =   1 d∆ 12 . . . d∆ 1n 0 1 . . . d∆ 2n . . . . . . . . . . . . 0 0 . . . 1   ∈Mn(Z), where d∆ ij = −\|∆− 1 (ai, aj)\|, if there is an edge ai ——– aj and i ≤ j, d∆ ij = \|∆+ 1 (ai, aj)\|, if there is an edge ai- - - - aj and i ≤ j. We set d∆ ij = 0, if the set ∆1(ai, aj) is empty or j < i. The rational matrix G∆ := 1 2 [Ǧ∆+Ǧtr ∆ ] ∈Mn(Q) 36 Algorithmic computation of principal posets is called the symmetric Gram matrix of ∆. The Gram quadratic form of ∆ ∈ UBigrn is defined by the formula q∆(x) = q∆(x1, . . . , xn)=x2 1+· · ·+x2 n+ ∑ i<j d∆ ijxixj =x·Ǧ∆ ·x tr = x·G∆ ·x tr. We call ∆ ∈ UBigrn, with n ≥ 2 numbered vertices, positive (resp. non- negative of corank s ≥ 1), if its symmetric Gram matrix G∆ ∈Mn(Q) is positive definite (resp. positive semi-definite of rank n− s). Moreover, we call ∆ ∈ UBigrn principal if the matrix G∆ is positive semi-definite of rank n− 1, see [50]. Note that a non-negative loop-free bigraph ∆ is of corank s ≥ 1 if and only if the kernel Ker q∆ := {v ∈ Zn; q∆(v) = v · Ǧ∆ · v tr = 0} ⊆ Zn of q∆ : Zn → Z is a free subgroup of Zn of Z-rank s. Obviously, ∆ is principal if and only if ∆ is non-negative loop-free and Ker q∆ = Z · h, with h 6= 0. The matrix Ad∆ := Ǧ∆ + Ǧtr ∆ − 2 ·E is called the symmetric adja- cency matrix of a loop-free edge-bipartite graph ∆ ∈ UBigrn, and the spectrum of ∆ is the set spec∆ ⊂ R of n real roots of the polynomial P∆(t) = det(t · E −Ad∆) ∈ Z[t], called the characteristic polynomial of the edge-bipartite graph ∆. Following [50], with any principal poset J , we have associated in [51] a loop-free edge-bipartite principal graph ∆J , and a simply laced Euclidean diagram DJ , that is, one of the graphs presented in the following table. Table 1.1. Simply laced Euclidean diagrams Ãn : 1 2 n + 1 n − 1 n n ≥ 1, D̃n : 1 2 3 n + 1 n − 1 n n ≥ 4, Ẽ6 : 1 4 5 2 3 6 7 Ẽ7 : 1 2 5 3 4 6 7 8 Ẽ8 : 1 4 2 3 5 6 7 8 9 M. Gąsiorek, D. Simson, K. Zając 37 We recall that DJ is the simply laced Euclidean diagram D̃∆J obtained from ∆J by applying the inflation algorithm ∆J 7→ D̃∆J presented in [28, Algorithm 5.4] and [50, Algorithm 3.1] (see also [52]). Consequently, we have the passage J 7→ ∆J 7→ DJ := D̃∆J . We study the Coxeter spectral properties of any principal poset J by means of the Coxeter spectral properties of the associated simply laced Euclidean diagram DJ ∈ {Ãn, D̃n, Ẽ6, Ẽ7, Ẽ8}. Following [45], with any poset J , we associate the Coxeter matrix CoxJ := −CJ · C −tr J , with det CoxJ = (−1)m, where m = \|J \| and C−tr J = (Ctr J )−1. The Cox- eter spectrum speccJ ⊆ C of J is defined to be the set of all m = \|J \| complex roots of the Coxeter polynomial coxJ(t) = det(t · E − CoxJ) ∈ Z[t], the Coxeter number cJ ≥ 2 is the minimal integer such that CoxcJ J = E, and the Coxeter transformation of J is the group automorphism ΦJ : ZJ → ZJ , ΦJ(v) := v 7→ v · CoxJ , see [45] and [51] for details. If J is non-negative, the Coxeter spectrum speccJ lies on the unit circle S1 = {z ∈ C; \|z\| = 1}, consists of roots of unity, and 1 /∈ speccJ if and only if J is positive, see [50, Lemma 2.1] and [51]. In this case we have associated with J (see [47] and [51]) a reduced Coxeter number čJ and the incidence defect homomorphism ∂̃J : ZJ → Ker qJ ⊆ ZJ such that ΦčJ J (v) = v + ∂̃J(v), for all v ∈ ZJ , where Ker qJ := {v ∈ ZJ ; qJ(v) = 0} is the kernel of the incidence quadratic form qJ : ZJ → Z defined by the formula qJ(x) = ∑ j∈J x2 j + ∑ i≺j xixj = x · CJ · x tr. Since J is assumed to be non-negative, the quadratic form qJ is non- negative and Ker qJ is a subgroup of ZJ , see [47]. If, in addition, the poset J is principal, the kernel Ker qJ is an infinite cyclic subgroup of 38 Algorithmic computation of principal posets ZJ of the form Ker qJ = Z · hJ , where hJ is a non-zero vector in Ker qJ uniquely determined by J , up to multiplication by −1. In this case, ∂̃J(v) = ∂J(v) · hJ , where ∂J : ZJ → Z is a group homomorphism, called the incidence defect of J , see [51]. The following characterisation of principal posets obtained in [51, Proposition 9] is of importance. Theorem 1.4. Assume that J is a connected poset with m = \|J \| ≥ 2 and let GJ ∈MJ (Q) be the symmetric incidence Gram matrix of J (1.2). The following four conditions are equivalent. (a) The poset J is principal. (b) The incidence symmetric Gram matrix GJ is positive semidefinite of rank m− 1. (c) The incidence quadratic form qJ : ZJ → Z of J is non-negative and Ker qJ = Z · h, for some non-zero vector h ∈ ZJ . (d) There exists a simply laced Euclidean diagram DJ ∈ {Ãs, s ≥ 3, D̃n, n ≥ 4, Ẽ6, Ẽ7, Ẽ8} (uniquely determined by J) such that the incidence symmetric Gram matrix GJ is Z-congruent to the symmetric Gram matrix GDJ ∈MDJ(Q) of the Euclidean diagram DJ , that is, there exists a Z-invertible matrix B ∈ Gl(m,Z) such that GDJ = Btr ·GJ ·B. Proof. Apply [51, Proposition 3.2] and a characterisation of principal loop-free edge-bipartite graphs given in [50]. One of the aims of the Coxeter spectral analysis of finite posets is to study the following problem. Problem 1.5. When the Coxeter spectrum speccJ of a poset J deter- mines the incidence matrix CJ (hence the poset J) uniquely, up to a Z-congruence. In connection with Problem 1.5, and a problem studied by Horn and Sergeichuck in [25], we also consider the problem if for any Z-invertible matrix A ∈ Mn(Z), there exists B ∈ Mn(Z) such that Atr = Btr · A ·B and B2 = E (the identity matrix). We would like to note that the following problem remains unsolved. Problem 1.6. Show that DJ 6= Ãm−1, if J is a one-peak connected principal poset, with m = \|J \| ≥ 5. A partial solution of Problems 1.5 and 1.6 is given in the following three theorems proved in Sections 2 and 3. M. Gąsiorek, D. Simson, K. Zając 39 Theorem 1.7. (a) Assume that I is a poset of the shape D̃ (1) m,s,p, D̃ (2) m,s, D̃ (3) m,s,p, D̃ (4) m,s,p, D̃ (5) m,s,p,r, D̃ (6) m,s,p,r or D̃ (7) m,s listed in Table 1.11, and \|I\| = m ≥ 5. Then I is principal and the associated Euclidean graph DI of I is the diagram D̃m. (b) If I is any of the one-peak posets listed in Tables 4.1 and 4.2 then I is principal and the associated Euclidean graph DI of I is the diagram Ẽm−1, where m = \|I\|. Theorem 1.8. Assume that I is a one-peak principal poset with m := \|I\| ≤ 15 and DI is its associated Euclidean diagram. (a) m ≥ 5 and DI is not the diagram Ãm−1. In particular, for m = 5, we have DI = D̃4 and I is one of the four posets: D̃ (1) 4,0,5 : 2 1 4 3 5 D̃ (2) 4,0 : 1 2 3 4 5 D̃ (4) 4,1,4 : 1 4 2 3 5 D̃ (6) 4,0,4,2 : 3 4 2 1 5 (b) If m ≥ 6 and DI = D̃m−1 then I is one of the 2.115 posets of the shapes presented in Table 1.11. In particular, for m = 6, we have DI = D̃5 and I is one of the 13 posets: D̃ (1) 5,0,5 : 2 1 4 3 5 6 D̃ (1) 5,0,6 : 2 1 5 3 4 6 D̃ (1) 5,1,6 : 1 3 2 5 4 6 D̃ (2) 5,0 : 1 2 3 4 5 6 D̃ (2) 5,1 : 1 2 3 4 5 6 D̃ (3) 5,2,2 : 1 2 3 4 5 6 D̃ (4) 5,1,4 : 1 4 3 2 5 6 D̃ (4) 5,1,5 : 1 2 3 4 5 6 D̃ (4) 5,2,5 : 1 2 5 3 4 6 D̃ (5) 5,0,3,6 : 1 2 3 4 5 6 D̃ (6) 5,0,5,3 : 1 2 3 4 5 6 D̃ (6) 5,0,5,2 : 1 2 3 4 5 6 D̃ (7) 5,3 : 4 1 5 2 3 6 40 Algorithmic computation of principal posets (c) If m = 7 and DI = Ẽ6 then I is one of the 31 posets presented in Table 4.1. (d) If m = 8 and DI = Ẽ7 then I is one of the 132 posets presented in Table 4.2. (e) If m = 9 and DI = Ẽ8 then I is one of the posets J Ẽ8 1 ,. . . , J Ẽ8 422 listed in [21]. In particular, we have J Ẽ8 1 : 1 2 3 4 5 6 7 8 9 J Ẽ8 31 : 1 2 3 5 4 6 7 8 9 J Ẽ8 48 : 1 2 6 7 3 4 5 8 9 J Ẽ8 147 : 1 3 2 4 6 5 7 8 9 J Ẽ8 412 : 1 4 2 6 7 3 5 8 9 J Ẽ8 422 : 2 1 3 7 4 6 5 8 9 (f) The total number of principal posets J (not necessarily one-peak ones), with m = \|J \| ≤ 15, equals 158.448 and the number # J of such posets J of the Coxeter-Euclidean type DJ ∈ {D̃m−1, Ẽm−1} is listed in the following tables. n = \|J \| n = 5 n = 6 n = 7 n = 8 n = 9 n = 10 DJ D̃4 D̃5 D̃6 Ẽ6 D̃7 Ẽ7 D̃8 Ẽ8 D̃9 # J 8 30 92 84 227 470 577 2 102 1.357 n = \|J \| n = 11 n = 12 n = 13 n = 14 n = 15 DJ D̃10 D̃11 D̃12 D̃13 D̃14 # J 3.217 7.371 16.897 38.069 85.561 Theorem 1.9. Assume that I is a one-peak principal poset with 5 ≤ m := \|I\| ≤ 15, DI is its associated Euclidean diagram, ǦDI is the non- symmetric Gram matrix of the graph DI, and ΦI : ZI → ZI is the incidence Coxeter transformation of I. Denote by RI := RqI = {v ∈ ZI ; qI(v) = 1} the set of roots of the incidence quadratic form qI : ZI → Z. (a) There exists a Z-invertible matrix B ∈Mm(Z) such that ǦDI = Btr · CI ·B, M. Gąsiorek, D. Simson, K. Zając 41 (b) The Coxeter number cI of I is infinite, the incidence defect ho- momorphism ∂I : ZI → Z is non-zero and the set ∂0 IRI ∪Ker qI admits a ΦI-mesh translation quiver Γ(∂0 IRI ∪ Ker qI , ΦI) of a sand-glass tube shape (in the sense of [46]-[47]), where ∂0 IRI = {v ∈ ZI ; qI(v) = 1 and ∂I(v) = 0}. (c) There exists a Z-invertible matrix C ∈Mm(Z) such that C2 = E and Ctr I = Ctr · CI · C. The proofs of Theorems 1.7-1.9 are given in Sections 2 and 3. We finish this section by a result that relates the Coxeter spectrum speccI with the usual spectrum specI of a poset I, compare with [50, Proposition 2.4(c)]. Theorem 1.10. Assume that I = {1, . . . , m} is an arbitrary poset and P I(t) := det(t · E − AdI) is the characteristic polynomial of the Euler adjacency matrix AdI := C tr I + CI − 2E of I, where CI := C−1 I is the Euler matrix of I, see [45]. (a) If the Hasse quiver of I (see [43]) is a tree then coxI(t2) = tm · P I(t + 1 t ). (b) Assume that I is a one-peak poset and m := \|I\| ≤ 15. If I is positive or I is principal then coxI(t2) = tm · P I(t + 1 t ) if and only if the Hasse quiver of I is a tree. Proof. Since det CI = 1, the Euler matrix CI := C−1 I lies in Mm(Z) and Ctr I = Ctr I · CI · CI . (a) Assume that the Hasse quiver of I is a tree. Without loss of gen- erality, we may assume that the points of I = {a1, . . . , am} are numbered in such a way that ai � aj implies i ≤ j in the natural order. Let ∆I be the Euler edge-bipartite graph associated with I, see [51, (33)]. By the definition of ∆I , the non-symmetric Gram matrix of the edge- bipartite graph ∆I coincides with the Euler matrix CI . Hence, Cox∆I = CoxI = −C−tr I · CI and cox∆I (t) = det(t · E − CoxI) = coxI(t), see [50] and [51, Corollary 6]. Since the Hasse quiver of I is a tree then, by [44, Proposition 2.12], the Euler matrix CI := C−1 I of I has the form CI := C−1 I =   1 c− 12 . . . c− 1m 0 1 . . . c− 2m ... . . . ... 0 0 . . . 1   ∈Mm(Z), 42 Algorithmic computation of principal posets with • c− 11 = . . . = c− mm = 1, • c− ab = −1, if there is an arrow a→ b in the Hasse quiver QI of I, • c− ab = 0, if a 6≺ b or there is a path a ≺ j1 ≺ . . . ≺ js−1 ≺ js = b of length s ≥ 2 in the Hasse quiver QI . It follows from [51, (33)] that the Euler edge-bipartite graph ∆I is a tree and, by [50, Proposition 2.4(c)], we get coxI(t2) = cox∆I (t2) = tm · P ∆I (t + 1 t ) = tm · P I(t + 1 t ). (b) Assume that I is a one-peak poset, m := \|I\| ≤ 15, and I is positive or I is principal. If the Hasse quiver QI of I is a tree, the statement (a) applies. To prove the converse implication, assume to the contrary that the Hasse quiver QI of I is not a tree. If I is positive, I is one of the non-tree shape posets described in [18, Theorem 5.2(e)], see also [19]. If I is principal, I is one of the non-tree shape poset described in Theorem 1.8. By a case by case inspection of the posets from our lists, a straightforward computer calculations show that coxI(t2) 6= tm · P I(t + 1 t ). For example, if I, I ′, I ′′, and J , J ′, J ′′ are the positive and principal posets I = 1 2 3 4 5 6 ∗ I ′ = 1 2 3 4 5 6 7 ∗ I ′′ = 1 2 3 4 5 6 7 ∗ J = 1 2 3 4 5 6 7 ∗ J ′ = 1 2 3 4 5 6 ∗ J ′′ = 1 2 3 4 5 6 7 8 ∗ then we have L coxL(t2) tm · P L(t + 1 t ) I t14 + t12 − t8 − t6 t14 − 3t12 − 8t11 − 13t10 − 18t9 − 21t8 − 22t7 − 21t6 − 18t5 +t2 + 1 −13t4 − 8t3 − 3t2 + 1 I ′ t16 + t14 + t2 + 1 t16 − t14 − 2t13 − 3t12 − 6t11 − 7t10 − 8t9 − 8t8 − 8t7 − 7t6 −6t5 − 3t4 − 2t3 − t2 + 1 I ′′ t16 + t14 − t10 − t8 t16 − 3t14 − 6t13 − 10t12 − 14t11 − 16t10 − 18t9 − 19t8 − 18t7 −t6 + t2 + 1 −16t6 − 14t5 − 10t4 − 6t3 − 3t2 + 1 M. Gąsiorek, D. Simson, K. Zając 43 J t14 + t12 − 2t8 − 2t6 t14 − 5t12 − 12t11 − 20t10 − 28t9 − 36t8 − 40t7 − 36t6 − 28t5 +t2 + 1 −20t4 − 12t3 − 5t2 + 1 J ′ t16 + t14 − t10 − 2t8 t16 − 3t14 − 8t13 − 14t12 − 20t11 − 25t10 − 28t9 − 30t8 − 28t7 −t6 + t2 + 1 −25t6 − 20t5 − 14t4 − 8t3 − 3t2 + 1 J ′′ t18 + t16 − t14 − t12 t18 − 7t16 − 24t15 − 53t14 − 88t13 − 121t12 − 144t11 − 156t10 −t6 − t4 + t2 + 1 −160t9 − 156t8 − 144t7 − 121t6 − 88t5 − 53t4 − 24t3 − 7t2 + 1 This finishes the proof of Theorem 1.10. Table 1.11. Seven infinite series of principal one-peak posets of Coxeter-Euclidean type D̃m D̃ (1) m,s,p : 1 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1s + 5 0 ≤ s, s + 5 ≤ p ≤ m + 1, 4 ≤ m D̃ (2) m,s : 1 s s + 1 s + 2 s + 4 m − 1 ∗ m + 1m s + 3 0 ≤ s, 4 ≤ m, s + 4 ≤ m D̃ (3) m,s,p : p + 1 s s + 1 s + 2 s + 3 m − 1 ∗ m + 1 m 1 p 1 < p ≤ s ≤ m − 3, 5 ≤ m, delete •s if s = p D̃ (4) m,s,p : 1 s s + 1 s + 2 p + 1 ∗ m + 1m ps + 3 1 ≤ s, s + 3 ≤ p ≤ m, 4 ≤ m D̃ (5) m,s,p,r : 1 s s + 1 s + 2 s + 3 ∗ m + 1 p p + 1 p + 2 r m r − 1p + 3 0 ≤ s, s + 3 ≤ p, 6 ≤ p + 3 ≤ r ≤ m + 1, delete •p+3 if p + 3 = r D̃ (6) m,s,p,r : 1 s s + 1 s + 2 p + 1 ∗ m + 1 r r + 2 r + 1 r + 3 ps + 3 m 0 ≤ s, s + 2 ≤ r, 4 ≤ r + 2 ≤ p ≤ m, delete •r if r = s + 2 D̃ (7) m,s : 1 s s + 1 ∗ m + 1 m 2 m − 1 5 ≤ m, 1 < s < m − 2 Convention 1.12. In Table 1.11, the following convention is used: we delete the vertex •a if a = 0. 44 Algorithmic computation of principal posets Remark 1.13. Let I be a one-peak principal poset I such that \|I\| ≤ 15. It follows from Theorem 1.9 that the Coxeter polynomial coxI(t) ∈ Z[t] coincides with the Coxeter polynomial coxDI(t) of the simply laced Euclidean diagram DI ∈ {D̃n, n ≥ 4, Ẽ6, Ẽ7, Ẽ8} associated with I, where coxDI(t)=    tn+1+tn − tn−1 − tn−2 − t3 − t2+t+1, if DI = D̃n, t7 + t6 − 2t4 − 2t3 + t + 1, if DI = Ẽ6, t8 + t7 − t5 − 2t4 − t3 + t + 1, if DI = Ẽ7, t9 + t8 − t6 − t5 − t4 − t3 + t + 1, if DI = Ẽ8, (1.13) see [33] and [45]. In particular, for n = 4 and n = 5, we have cox D̃4 (t) = t5 + t4 − 2t3 − 2t2 + t + 1, cox D̃5 (t) = t6 + t5 − t4 − 2t3 − t2 + t + 1. 2. Proof of Theorems 1.7 and 1.8 In this section we present the proof of Theorems 1.7 and 1.8 that are main results of the paper. First, we note that every poset J = ({1, . . . , m},�) is Z-bilinear equivalent to a poset J ′ with vertices numbered in such a way that i � j implies i ≤ j in a natural order and the matrix CJ ′ is upper triangular. Therefore, without loss of generality, we can assume that the matrix CJ ∈MJ (Z) of any poset J has an upper triangular form. Following [51], we identify a poset J = (J,�) with its acyclic edge- bipartite graph ∆J (usually viewed as a signed graph in the sense of [56]) without continuous edges, and with the dotted edges •i- - - -•j , for all i ≺ j. We recall from [51] that ∆J is uniquely determined by its non-symmetric Gram matrix Ǧ∆J ≡ CJ . One of our main tools is the second step ∆ 7→ ∆′ := t− ab∆ of the inflation algorithm [28, Algorithm 5.4] and [50, Algorithm 3.1] (see also [52]) that associates to any loop-free principal edge-bipartite graph ∆, with a fixed dotted edge •a- - - -•b in ∆1(a, b), a 6= b, the loop-free principal edge-bipartite graph ∆′ := t− ab∆ as follows: • we set ∆0 = ∆′ 0 and replace the dotted edge •a- - - -•b in ∆ by a continuous one •a——– •b in ∆′, • given c 6= a in ∆0 = ∆′ 0 such that ∆1(a, c) 6= ∅, we define ∆′ 1(b, c) to be the set with exactly d∆′ bc dotted edges if d∆′ bc > 0, and exactly −d∆′ bc continuous edges if d∆′ bc ≤ 0, where d∆′ bc := d∆ bc − d∆ ac · d ∆′ ab , • each of the remaining edges of ∆1 becomes an edge in ∆′ 1, i.e., we set ∆′+ 1 (a′, b′) = ∆+ 1 (a′, b′) and ∆′− 1 (a′, b′) = ∆− 1 (a′, b′), if (a′, b′) 6= (a, b) or (a′, b′) 6= (b, c). M. Gąsiorek, D. Simson, K. Zając 45 The main idea of the inflation algorithm is to reduce the number of dotted edges in ∆. It is shown in [50] that Ǧ∆′ = ∇((T − ab) tr · Ǧ∆ · T − ab), where T − ab = [tij ], with tij =    1, if i = j or (i, j) 6= (a, b), −1, if (i, j) = (a, b), 0, otherwise, and the operation C 7→ ∇(C) = [c▽ij ] (introduced in [47, (4.5)]) associates to any square matrix C = [cij ] ∈Mm(R) the upper triangular matrix ∇(C) = [c▽ij ] =   c▽11 c▽12 . . . c▽1m 0 c▽22 . . . c▽1m ... ... . . . ... 0 0 . . . c▽mm   ∈Mm(R) by setting c▽ij = cij + cji, for i < j, c▽ij = 0, for i > j, and c▽jj = cjj , for j = 1, . . . , m. Note that the inflation matrix T − ab = [tij ] ∈ Mm(Z) is the identity matrix with an element tab changed to −1. Proof of Theorem 1.7. (a) Assume that I ∈ {D̃(1) m,s,p, D̃(2) m,s, D̃(3) m,s,p, D̃(4) m,s,p, D̃(5) m,s,p,r, D̃(6) m,s,p,r, D̃(7) m,s} with \|I\| = m + 1 ≥ 5, as listed in Table 1.11. Our aim is to construct a matrix BI ∈Mm+1(Z) such that (Ǧtr D̃m + Ǧ D̃m ) = Btr I · (C tr I + CI) ·BI . Since det CI = 1, the matrix CI is Z-invertible and C−1 I = C−1 I ·Ctr I · C−tr I . Note that, for B′′ I := C−tr I , we have (C−tr I + C−1 I ) = B′′tr I · (Ctr I + CI) · B′′ I . Therefore, it is sufficient to construct a Z-invertible matrix B′ I ∈ Gl(m + 1,Z) such that B′tr I · (C −tr I + C−1 I ) ·B′ I = (Ǧtr D̃m + Ǧ D̃m ), because then, for BI := B′′ I ·B ′ I ∈Mm+1(Z), we have (Ǧtr D̃m + Ǧ D̃m ) = B′tr I · (C −tr I + C−1 I ) ·B′ I = B′tr I · (B ′′tr I · (Ctr I + CI) ·B′′ I ) ·B′ I = (B′′ I ·B ′ I)tr · (Ctr I + CI) · (B′′ I ·B ′ I) = Btr I · (C tr I + CI) ·BI . 46 Algorithmic computation of principal posets We construct the matrix B′ I ∈Mm+1(Z) in six cases considered below, in the form of the product of inflation matrices T − ab = [t′ ij ] ∈ Mm+1(Z), by applying the inflation algorithm procedure. First, we note that our assumptions imply that the matrix C−1 I is upper triangular and coincides with the non-symmetric Gram matrix Ǧ∆I that defines the Euler acyclic edge-bipartite graph ∆I of I, see [51]. Case 1◦ Assume that I = D̃ (1) m,s,p. The Euler bigraph ∆I of I, with Ǧ∆I = C−1 I , has the shape ∆I = 1 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1s + 5 To simplify the notation, we set t (1) j := t− j s+3 ◦ t− j s+4, t (2) j := t− j s+1 ◦ t− j s+2, T (1) j := T − j s+3 · T − j s+4 and T (2) j := T − j s+1 · T − j s+2. The passage ∆I 7→D∆I and the construction of the matrix B′ I ∈Mm+1(Z) can be illustrated as follows. ∆I t(1) s=⇒ 1 s − 1 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1s + 5 t (1) s−1 =⇒ 1 s − 2 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1s + 5 t (1) s−2 =⇒ · · · t (1) 1=⇒ 1 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1s + 5 t(2) p =⇒ · · · t (2) m+1 =⇒ · · · t (2) s+5 =⇒ 1 s s + 1 s + 2 s + 3 s + 4 p m ∗ m + 1 p − 1 s + 5 Summing up, D∆I = D̃m and we define B′ I ∈ Gl(m + 1,Z) to be the matrix B′ I := T (2) s+5 · · ·T (2) p−1 · T (2) m+1 · T (2) m · · ·T (2) p · T (1) 1 · · ·T (1) s−1 · T (1) s M. Gąsiorek, D. Simson, K. Zając 47 Case 2◦ Assume that I = D̃ (2) m,s. The Euler bigraph ∆I of I, with Ǧ∆I = C−1 I , has the shape ∆I = 1 s s + 1 s + 2 s + 4 m − 1 ∗ m + 1m s + 3 We set t (1) j = t− j s+4 and T (1) j = T − j s+4. The passage ∆I 7→ D∆I and the construction of the matrix B′ I ∈Mm+1(Z) can be illustrated as follows: ∆I t(1) s=⇒ 1 s − 1 s s + 1 s + 2 s + 4 m − 1 ∗ m + 1m s + 3 t (1) s−2 =⇒ · · · t (1) 1=⇒ 1 s s + 1 s + 2 s + 4 m − 1 ∗ m + 1m s + 3 We have D∆I = D̃m and we define B′ I to be the matrix B′ I := T (1) 1 · T (1) 2 · · ·T (1) s−1 · T (1) s Case 3◦ Assume that I is one of the posets I1 = D̃ (3) m,s,p and I2 = D̃ (4) m,s,p. Then D∆I = D̃m and B′ I is defined to be the matrix B′ I1 :=T (3) p−1 · · ·T (3) 2 · T (3) 1 · T (1) p+1 · T (1) p+2 · · ·T (1) s−1 · T (1) s , if I = I1 and B′ I2 :=T (2) s+3 · · ·T (2) p−1 · T (2) p · T (2) 1 · · ·T (2) s · T (3) m−1 · · ·T (3) 2 · T (3) 1 , if I = I2, where T (1) j = T − j s+3, T (2) j = T − j p+1 and T (3) j = T − j m+1. Case 4◦ If I = D̃ (5) m,s,p,r, then D∆I = D̃m and B′ I is defined to be the matrix B′ I := T (2) p+3 · · ·T (2) r−1 · T (2) m+1 · T (2) m · · ·T (2) r+1 · T (2) r · T (1) 1 · · ·T (1) s−1 · T (1) s , where T (1) j = T − j s+3 and T (2) j = T − j r. Case 5◦ If I = D̃ (6) m,s,p,r, then D∆I = D̃m and B′ I is defined to be the matrix B′ I := T (2) s+3 · · ·T (2) r−1 · T (2) r · T (1) 1 · · ·T (1) s−1 · T (1) s , where T (1) j = T − j p+1 and T (2) j = T − j r+3. 48 Algorithmic computation of principal posets Case 6◦ If I = D̃ (7) m,s, then D∆I = D̃m and B′ I is defined to be the matrix B′ I := T (1) s−2 · · ·T (1) 2 · T (1) 1 · T (2) s+3 · · ·T (2) m · T (2) m+1 · T − m+1 1, where T (1) j = T − j s and T (2) j = T − j s+1. To finish the proof of (a), we recall from [50] that the Euclidean diagrams are principal and the existence of a Z-equivalence of a finite poset I with a Euclidean diagram D̃m implies that I is principal. (b) The proof is a computational one and we proceed similarly as in the proof of (a). As earlier, we identify the poset I with its acyclic edge-bipartite graph ∆I and apply the inflation algorithm to ∆I . In this way we obtain a matrix BI defining the Z-equivalence of the poset I with the Euclidean diagram Ẽm, where m = \|I\| − 1. Hence I is principal and the proof is complete. Proof of Theorem 1.8. Assume that m ≤ 15 and I is a principal one- peak poset. We compute a complete list of such posets I, with \|I\| = m ≤ 15, and their Coxeter-Euclidean types DI by applying the inflation algorithm [50] and Algorithm 3.1 described in Section 3. In particular, the computations show that: (a) there is no such a poset I that DI = Ãm−1, (b) if DI = D̃m−1, then I is one of the posets listed in Theorem 1.7, (c) if 7 ≤ m ≤ 9 and DI = Ẽm−1, then I is one of the posets listed in (c), (d), and (e) of Theorem 1.8. 3. Algorithms In this section, we outline a description of computational algorithms we use in the proofs of Theorems 1.8 and 1.9. First, we discuss an algorithm used in computation of all principal posets with at most 15 elements, compare with [37] and [38]. Algorithm 3.1. Input: An integer 1 ≤ n ≤ 15. Output: Finite sets princ[1], . . . , princ[n] of all connected non-negative posets of corank 1 encoded in the form of their incidence matrices. That is, the set princ[i] contains the principal posets with i vertices. Step 1◦ Initialize the set princ[1] with the matrix [ 1 ] ∈M1(Z). Step 2◦ For every m from 2 to n: Step 2.1◦ Initialize an empty list candidatem. M. Gąsiorek, D. Simson, K. Zając 49 Step 2.2◦ For every poset J ∈ princ[m − 1], generate a list of all possible extensions of J to a poset with m vertices. In other words, generate a list WJ ∋ w of all vectors w = [w2, . . . , wm] ∈ {0, 1}m−1 such that the matrix CJw = [ 1 w 0 CJ ] = [cij ] ∈Mm(Z) is an incidence matrix of a poset Jw (matrix with the following transitivity property: cij = 1 and cjs = 1 implies cis = 1, for 1 ≤ i, j, s ≤ m). Step 2.3◦ For every poset J ∈ princ[m − 1] and for every vector w ∈ WJ , construct the matrix CJw ∈ Mm(Z) and add the poset Jw to the list candidatem if the symmetric matrix CJw + Ctr Jw is non-negative of corank at most 1, (by checking, for example, if all diagonal minors of the matrix are non-negative - the extended Sylvester criterion, see [16]). Step 2.4◦ Construct the set princ[m] by selecting non isomorphic posets from the list candidatem (using the Hasse digraph representation in order to test poset isomorphism). Step 3◦ Remove from the sets princ[1], . . . , princ[n] the matrices of posets Jw that are not connected (using a graph search algorithm, such as breadth-first search – BFS) or have the symmetric matrix CJw + Ctr Jw positive definite (for example, by checking if all principal minors of CJw + Ctr Jw are positive - Sylvester criterion). Step 4◦ Return the sets princ[1], . . . , princ[n] as a result. Remark 3.2. (a) Note that posets J , with \|J \| ≤ 3, need not to be checked, because any such a poset has the shape ( ◦ ) , ( ◦ ◦ ) , ( ◦ → ◦ ) ,( ◦ ◦ ◦ ) , ( ◦ ◦→◦ ) , ( ◦→◦→◦ ) , ( ◦→◦←◦ ) or ( ◦←◦→◦ ) and is positive. (b) Note that Step 2.3◦ and Step 2.4◦ can be done simultaneously by adding to the set princ[m] only these non-negative posets that have Hasse digraphs not isomorphic to the posets that are already in the set princ[m]. (c) In our implementation of the algorithm we use the igraph pack- age (http://igraph.sourceforge.net/) to test digraph isomorphism in step 2.4◦. (d) A simple check of the equivalence of the degrees of vertices to detect non-isomorphic digraphs before the usage of more advance algorithm in the step 2.4◦ gave us a considerable speed up. 50 Algorithmic computation of principal posets (e) It is easy to efficiently implement the algorithm in a parallel environment (for example, Step 3◦ can be executed in parallel without need of any synchronisation). In the proof of Theorem 1.9 we determine the Z-congruence CI∼ZǦDI , for any principal poset I, \|I\| ≤ 15, of the Coxeter-Euclidean type DI∈{D̃m, m ≥ 4, Ẽ6, Ẽ7, Ẽ8}. We do it by constructing a matrix B ∈Mn(Z) with n = \|I\|, such that CI = Btr · ǦDI ·B. We essentially use the following theorem and Procedure 3.6. Theorem 3.3. (a) Let D be one of the Euclidean diagrams D̃m, m ≥ 4, Ẽ6, Ẽ7, Ẽ8, with vertices numbered as in Introduction. Let RD be the set of roots of the Euler quadratic form qD of D. Then there exists a unique ΦD- mesh translation quiver Γ(RD, ΦD) of ΦD-orbits of the set RD (called a ΦD-mesh geometry of roots of D) such that Γ(RD, ΦD) admits a principal Coxeter Φ∆-orbit configuration ΓǦD D of simple roots of the form presented below (see also [47] and [48, Table 4.7]). (b) If I is a connected principal poset, with n ≥ 5 elements, of the Coxeter-Euclidean type DI and B ∈ Gl(n,Z) is such a matrix that ǦDI = B · ǦI ·B tr, then the following diagram is commutative Zn ΦD−−−−−→ Zn h y≃ h y≃ Zn ΦI−−−−−→ Zn (3.4) where h = hB is the group isomorphism defined by hB(x) = x ·B. If RI := RqI is the set of roots of the unit quadratic form qI : ZI → Z and Γ(RDI , ΦDI) is ΦDI-mesh geometry of roots of DI (with princi- pal Coxeter ΦDI-orbit configuration ΓǦDI DI ), then the group isomorphism h = hB carries it to the ΦI-mesh geometry Γ(RI , ΦI) (with a principal Coxeter ΦI-orbit configuration ΓCI I ), induces the mesh translation quiver isomorphism h : Γ(RDI , ΦDI) ≃ −→Γ(RI , ΦI) and the quiver isomorphism h : ΓǦDI DI ≃ −→ΓCI I . Moreover, the matrix B has the form B =   h(e1) h(e2) . . . h(en)  . (3.5) M. Gąsiorek, D. Simson, K. Zając 51 Proof. Apply [46, Section 5], [46, Theorems 4.7 and Proposition 4.8] and their proofs, see also [47], [48, Lemma 4.3], and [50]. Γ G Ẽ6 Γ G Ẽ7 ê3 ê2 ê1 e4 e6e7 e5 e8 e7 e6 e5 ê4 ê3 ê2 ê1 Γ G Ẽ8 Γ G D̃6 ê3 ê2 ê1 e4 e9 e8 e7 e6 e5 ê1 ẽ3 ê2 ẽ4 ẽ5 e7 e6 êj = −ej ẽj = ê1 + · · · + êj Procedure 3.6. Assume that I is a poset of the Coxeter-Euclidean type DI∈{D̃n−1, Ẽ6, Ẽ7, Ẽ8}, with n = \|I\|. To construct a matrix B that defines a Z-equivalence CI ∼Z ǦDI , we proceed as follows. 1◦ First, by applying the mesh toroidal algorithm described in [46, Proposition 4.5] and [47] (see also [48, Lemma 4.6 and Algorithm 4.8.2]), we construct the ΦI -mesh translation quiver Γ(RI , ΦI), with a principal Coxeter ΦI -orbit configuration ΓCI I of simple roots of qI , together with a mesh quiver isomorphism h : ΓǦDI DI → ΓCI I . 2◦ Next, we define the matrix B by setting B =   h(e1) h(e2) ... h(en)  , as in (3.5) and [48, Lemma 4.3]. 3◦ Finally, we check the matrix equality ǦDI = B · CI ·B tr. 52 Algorithmic computation of principal posets Remark 3.7. Procedure 3.6 has implementations in Maple and Python, with an assistance of programming and graphics in Java. Algorithm 3.8. Input: A non-negative poset I, with n elements, encoded in the form of incidence matrix CI ∈Mn(Z). Output: Reduced Coxeter number čI ∈ Z. Step 1◦ Initialize the symbolic vector v := [v1, . . . , vn]. Step 2◦ Calculate the Coxeter matrix CoxI := −CI · C −tr I . Step 3◦ For r = 1, 2, 3, . . . Step 3.1◦ Calculate w := v · Coxr I − v. Step 3.2◦ If qI(w) := w ·CI ·w tr equals zero then stop the calculations and return čI as a result. Remark 3.9. By [51, Theorem 18], Algorithm 3.8 returns čI in a finite number of steps. We use the following algorithm computing the incidence defect of any principal poset. Algorithm 3.10. Input: A principal poset I, with n elements, encoded in the form of incidence matrix CI ∈Mn(Z). Output: The incidence defect ∂I : Zn → Z. Step 1◦ Initialize the symbolic vector v := [v1, . . . , vn] and calculate the Coxeter matrix CoxI := −CI · C −tr I . Step 2◦ Using Algorithm 3.8, compute the reduced Coxeter number čI ∈ Z and calculate the vector w = [w1, . . . , wn] := v · Coxč I − v. Step 3◦ Compute the vector h ∈ Zn such that Ker qI = Z ·h by solving in Z the system of Z-linear equations (CI + Ctr I ) · vtr = 0 (for example, using the procedure isolve of the LinearAlgebra package in MAPLE). Step 4◦ Solve the symbolic system of linear equations λ · hI = w (in Z), for the unknown λ, and return computed λ as a result. Outline of proof of Theorem 1.9. Assume that I is a one-peak prin- cipal poset with m := \|I\| ≤ 15. By Theorem 1.8, I is one of the four five elements posets listed in 1.8(a), one of the 2.115 posets with 6 ≤ m ≤ 15 of the shape listed in Table 1.11, one of the 31 posets listed in Table 4.1, one of the 132 posets listed in Table 4.2, or one of the 422 posets listed in [21]. By applying Algorithms 3.8 and 3.10, for each of the posets I from this finite list, we calculate its reduced Coxeter number čI and the incidence defect ∂I : ZI → Z. In particular, we show that ∂I is non-zero. It follows from [51, Theorem 1.18 (c)] that the Coxeter number cI of I is infinite, see also [47, Corollary 4.15 (c)] and [49, Proposition 3.12]. M. Gąsiorek, D. Simson, K. Zając 53 (a) By applying Procedure 3.6 as in [17, Section 7], for each of the posets I from the finite list described above, we construct a Z-invertible matrix BI such that ǦDI = BI ·CI ·B tr I . By setting B := Btr I we get the required equality ǦDI = Btr · CI ·B. The proof is long and a computational one. Here we do not present a complete proof, but we illustrate its idea on examples of several posets. The proof for the remaining posets of the list is analogous. First we illustrate an application of Procedure 3.6 for the posets D̃ (7) 5,3 and J Ẽ6 29 presented in Theorem 1.8 (b) and Table 4.1, respectively. 1◦ If we enumerate the elements of the poset J := D̃ (7) 5,3 from Theorem 1.8 (b) as follows J = 1 2 3 4 5 6 then the incidence matrix CJ ∈ M6(Z), the Coxeter matrix and the incidence quadratic form qJ : Z6 → Z are given as follows CJ =   1 1 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1   , CoxJ =   0 0 0 1 0 −1 0 0 0 0 1 −1 −1 1 0 0 1 −1 0 1 0 0 0 −1 0 0 1 0 0 −1 −1 0 1 −1 1 −1   , qJ(x) = x2 1 + x2 2 + x2 3 + x2 4 + x2 5 + x2 6 + x1x2 + x3(x1 + x2 + x4) +(x1 + x4)x5 + (x1 + x2 + x3 + x4 + x5)x6 = ( x1 + 1 2x2 + 1 2x3 + 1 2x5 + 1 2x6 )2 +3 4 ( x2 + 1 3x3 − 1 3x5 + 1 3x6 )2 +2 3 ( x3 + 3 4x4 − 1 4x5 + 1 4x6 )2 + 5 8 ( x4 + x5 + 3 5x6 )2 + 2 5x2 6. It follows that qJ : Z6 → Z is non-negative and Ker qJ = Z · hJ , where hJ = [1, 0,−1, 1,−1, 0]; hence J is principal. By Theorem 1.7, the poset J is of Euclidean type DJ = D̃5. A routine calculations show that • coxJ(t) = t6 + t5 − t4 − 2t3 − t2 + t + 1 = cox D̃5 (t), • čJ = 6, cJ =∞, • ∂̃J (v) = 2(v1 +v2 +v3 +v4 +v5) ·hJ , ∂J (v) = 2(v1 +v2 +v3 +v4 +v5), and the set RJ of roots of qJ has the decomposition RJ = Rred J + Z · hJ , 54 Algorithmic computation of principal posets where the finite set Rred J = {v ∈ Z6; v1 = 0 and qJ(v) = 1} is a reducer of RJ in the sense of [47]. One shows that \|Rred J \| = 40, \|∂0 JR red J \| = 10, \|∂− J R red J \| = \|∂ + J R red J \| = 15, where ∂0 JR red J , ∂− J R red J , and ∂+ J R red J is the subset of Rred J consisting of the zero-defect vectors, negative-defect vectors, and positive-defect vectors, respectively. It is easy to see that the negative-defect part ∂− J RJ of RJ is the set ∂− J RJ = ∂− J R red J + Z · hJ and admits the following ΦJ -translation quiver structure Γ(∂− J RJ , ΦJ): 00̂1001 0000̂10 1̂1̂11̂11 10̂10̂10 0̂10̂101 000̂100 00̂10̂11 00̂11̂11 1̂1̂11̂21 1̂100̂10 2̂1̂21̂21 10̂21̂11 1̂00000 0̂100̂11 1̂100̂11 1̂1̂10̂11 00̂1000 10̂21̂21 10̂11̂21 2̂1̂22̂31 0000̂11 0̂10000 10̂10̂11 00̂11̂10 O1 O2, O3 O4, O5 O6 Hence, by applying Procedure 3.6 and using the vectors in Γ(∂− J RJ , ΦJ) marked by the framed boxes, we obtain the Z-invertible matrix BJ =   0 0 0 0 1 0 0 0 1 −1 1 −1 0 0 0 1 −1 0 0 1 −1 0 0 0 0 −1 0 0 0 0 1 −1 0 0 −1 1   such that ǦDJ = Ǧ D̃5 = BJ · ǦJ ·B tr J . 2◦ If we enumerate the points of the poset I := J Ẽ6 29 from Table 4.1 as follows I = 1 2 3 4 5 6 7 , M. Gąsiorek, D. Simson, K. Zając 55 then the incidence matrix CI ∈ M7(Z), the Coxeter matrix and the incidence quadratic form qI : Z7 → Z have the forms CI =   1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1   , CoxI =   0 0 1 0 1 0 −1 −1 0 0 1 0 1 −1 −1 1 0 0 0 1 −1 −1 1 1 0 0 1 −1 −1 1 0 1 0 0 −1 −1 1 0 1 1 0 −1 −2 1 0 1 0 1 −1   , qI(x) = x2 1 + x2 2 + x2 3 + x2 4 + x2 5 + x2 6 + x2 7 + x1x2 + (x1 + x3)x4 + (x1 + x5)x6 + (x1 + x2 + x3 + x4 + x5 + x6)x7 = ( x1 + 1 2x2 + 1 2x4 + 1 2x6 + 1 2x7 )2 + 3 4 ( x2 − 1 3x4 − 1 3x6 + 1 3x7 )2 + ( x3 + 1 2x4 + 1 2x7 )2 + 5 12 ( x4 − 4 5x6 + 1 5x7 )2 + ( x5 + 1 2x6 + 1 2x7 )2 + 3 20 (x6 + x7)2 . It follows that qI : Z7 → Z is non-negative and Ker qI = Z · hI , where hI = [1,−1, 0,−1, 0,−1, 1]; hence I is principal. By theorem 1.7 the poset I is of Euclidean type DI = Ẽ6. A routine calculations show that • coxI(t) = t7 + t6 − 2t4 − 2t3 + t + 1 = cox Ẽ6 (t), • čI = 6, cI =∞, • ∂̃I(v) = (v1 − v7) · hI , ∂I(v) = v1 − v7, and the set RI of roots of qI has the decomposition RI = Rred I + Z · hI , where the finite set Rred I = {v ∈ Z7; v1 = 0 and qJ(v) = 1} is a reducer of RI in the sense of [47]. One shows that \|Rred I \| = 72, \|∂0 IR red I \| = 14, \|∂− I R red I \| = \|∂ + I R red I \| = 29, where ∂0 IR red I , ∂− I R red I , and ∂+ I R red I is the subset of Rred I consisting of the zero-defect vectors, negative-defect vectors, and positive-defect vectors, respectively. It is easy to see that the negative-defect part ∂− I RI of RI is the set ∂− I RI = ∂− I R red I + Z · hI and admits the following ΦI -translation quiver structure Γ(∂− I RI , ΦI): 56 Algorithmic computation of principal posets 1̂0̂11̂110 1̂100000 0̂100001 00̂10̂101 1̂0̂11̂111 2̂1̂11̂110 1̂000001 0̂1̂10̂102 1̂000010 0000̂101 1̂0̂11000 000̂1001 2̂1̂11010 1̂000̂111 1̂0̂11̂101 1̂0̂10001 2̂1̂11̂111 2̂0̂11̂111 1̂0̂10̂102 1̂̂1̂10̂102 2̂101̂110 1̂0̂11001 1̂0̂10̂111 1̂000̂101 1̂001000 00̂10001 1̂000̂110 00000̂11 O1 O2 O3 O4 O5 O6 O7 Hence, by applying Procedure 3.6 and using the vectors in Γ(∂− I RI , ΦI) distinguished by the framed boxes, we obtain the Z-invertible matrix BI =   1 0 0 0 1 −1 0 0 0 1 0 0 0 −1 1 0 0 −1 0 0 0 −1 0 −1 1 0 0 0 0 0 0 0 −1 0 1 0 −1 0 0 0 0 1 −1 1 0 0 0 0 0   such that ǦDI = Ǧ Ẽ6 = BI · ǦI ·B tr I . Now we collect a final effect of the computational Procedure 3.13 (presented below) applied to principal posets of type Ẽ8. For example, consider the principal posets I1 := J Ẽ8 1 , I2 := J Ẽ8 31 , I3 := J Ẽ8 48 , I4 := J Ẽ8 147, I5 := J Ẽ8 412, I6 := J Ẽ8 422 from Theorem 1.8 (e). Using Procedure 3.13, computer calculations yield the following Z-invertible matrices B1, . . . , B6 ∈M9(Z): B1 =   5 3 4 −2 −1 −2 −2 −1 −2 5 4 3 −1 −2 −2 −1 −2 −2 6 3 4 −2 −2 −1 −2 −2 −2 −8 −5 −5 2 3 2 3 2 3 −3 −1 −2 1 1 1 0 1 1 −2 −2 −2 1 1 0 1 1 1 −3 −2 −1 1 0 1 1 1 1 −2 −1 −2 0 1 1 1 1 1 −3 −2 −2 1 1 1 1 1 0   , B2 =   1 1 0 −2 −2 −1 1 1 0 1 1 −1 −1 −2 −1 1 0 1 1 1 −1 −2 −1 −1 0 1 1 −2 −1 1 2 2 2 −1 −1 −1 0 −1 1 1 0 0 0 0 0 −1 0 0 1 1 0 0 0 −1 0 0 0 0 1 1 0 −1 0 0 −1 0 1 1 1 −1 0 −1 −1 −1 1 1 1 0 0 −1 0   , M. Gąsiorek, D. Simson, K. Zając 57 B3 =   0 0 1 0 0 0 1 0 −1 0 0 0 0 1 1 1 −1 −1 0 0 0 1 0 0 0 0 −1 0 0 0 −1 0 −1 −1 0 2 0 0 0 0 −1 0 0 0 1 0 0 0 −1 0 0 −1 1 0 0 1 −1 0 0 −1 0 0 1 1 −1 0 0 0 0 0 0 0 −1 0 0 0 0 0 0 0 0   , B4 =   0 2 2 −1 −1 −2 −1 0 0 1 1 1 0 0 −2 −2 0 1 0 1 2 0 −1 −2 −2 1 0 −1 −2 −2 0 1 3 3 −1 0 0 0 −1 0 0 1 1 0 0 0 −1 −1 0 1 1 1 0 −1 0 −1 −1 0 0 2 1 −1 0 0 −1 −1 1 0 0 1 0 0 −1 0 −1 0 1 1 0 0 0   , B5 =   2 2 2 1 −1 −1 −2 −1 −1 1 3 1 1 −1 −1 −2 −1 −1 1 3 2 2 −1 −1 −3 −2 0 −2 −4 −2 −2 1 1 4 2 1 0 −1 −1 −1 0 1 1 1 0 −1 −2 −1 0 1 0 1 1 0 0 −1 −1 −1 1 0 1 0 1 −1 −1 0 −1 0 1 1 1 0 −1 −2 −1 −1 1 1 2 0 0   , B6 =   1 1 1 0 1 −1 0 −1 −1 1 2 1 0 0 0 −1 −1 −1 1 1 1 1 1 −1 −1 −1 −1 −1 −2 −1 −1 −1 1 1 1 2 −1 −1 0 0 −1 0 1 1 0 0 0 −1 0 0 0 0 0 1 0 −1 −1 −1 0 1 0 1 0 −1 0 0 0 0 0 0 0 1 −1 −1 −1 0 0 1 1 0 0   , for the poset I1, I2, I3, I4, I5, and I6, respectively. One checks that ǦDI = Ǧ Ẽ8 = Bj · ǦIj ·Btr j , for j = 1, . . . , 6. (b) By (a) and [46, Theorems 4.7 and 4.8], for each of the posets I from the finite list described above, there is a Z-invertible matrix B such that ǦDI = B · ǦI ·B tr and, by [46, Proposition 4.8], we have the commutative diagram (3.4), with D = DI and h = hB . Hence, in view of our remarks made in the first part of proof, (b) is a consequence of the results in [46, Section 5]. (c) Given a principal poset I such that m := \|I\| ≤ 15, fix a matrix BI ∈ Gl(m,Z) such that ǦDI = Btr I · CI ·BI , as in (a). By applying the technique used in [17, Section 7], one can construct a matrix C ∈ Gl(m,Z) such that Ǧtr DI = Ctr · ǦDI · C and C2 = E. Then Ǧtr DI = Btr I · C tr I ·BI and Ǧtr DI = Ctr · ǦDI · C = Ctr ·Btr I · CI ·BI · C. Hence we get Ctr I = B−tr I · Ctr ·Btr I · CI ·BI · C ·B −1 I = C tr · CI · C, where C = BI · C ·B −1 I . It follows that C ∈ Gl(m,Z) and C 2 = E. This finishes the proof of (c) and of Theorem 1.9. Corollary 3.11. Assume that I is a principal one-peak poset such that m = \|I\| ≤ 15. Then there exists a ΦI-mesh translation quiver of roots Γ(RI , ΦI) satisfying the conditions stated in Theorem 3.3 (b). Proof. Let DI be the Coxeter-Euclidean type of I. By Theorem 1.9 (a), there exists a matrix B ∈ Gl(m,Z) such that ǦDI = B · ǦI ·B tr and the diagram (3.4) is commutative, where h = hB is the group isomorphism defined by hB(x) = x · B. Therefore the corollary is a consequence of Theorem 1.9 (b). 58 Algorithmic computation of principal posets We recall from [50] that a Z-invertible matrix B ∈ Mn(Z) defines a Z-congruence ∆ ≈Z ∆′ between edge-bipartite graphs ∆, ∆′ in UBigrn if the equality Ǧ∆′ = B · Ǧ∆ ·B tr holds. Now we outline an alternative, more general heuristic algorithm con- structing a Z-invertible matrix B ∈ Mn(Z) defining the Z-congruence Ǧ∆∼Z Ǧ∆′ between the non-symmetric Gram matrices Ǧ∆, Ǧ∆′ ∈Mn(Z) of non-negative edge-bipartite graphs ∆ and ∆′, that is, satisfying the equality Ǧ∆′ = B · Ǧ∆ ·B tr. Its idea uses the following observations made in [45, Proposition 2.8]. Lemma 3.12. Assume that ∆ ≈Z ∆′ are loop-free edge-bipartite graphs in UBigrn and B ∈Mn(Z) is a Z-invertible matrix satisfying the equality Ǧ∆′ = B · Ǧ∆ ·B tr, that is, B defines the Z-congruence ∆ ≈Z ∆′. (a) Cox∆′ = B · Cox∆ ·B −1 and cox∆′(t) = cox∆(t). (b) Each of the rows w of the matrix B is a root of the unit form q∆ : Zn → Z of ∆, that is, we have q∆(w) = 1. (c) Each of the rows of the matrix B−1 is a root of the unit form q∆′ : Zn → Z of ∆′. Proof. (a) Apply [45, Proposition 2.8]. (b) Denote by w(1), . . . , w(n) the rows of the matrix B. Then B has the form B = [w(1), . . . , w(n)]tr and, given j ∈ {1, . . . , n}, we have ej ·B = w(j) and 1 = q∆′(ej) = ej · Ǧ∆′ · etr j = ej · (B · Ǧ∆ ·B tr) · etr j = (ej ·B) · Ǧ∆ · (ej ·B)tr = w(j) · Ǧ∆ · w (j)tr = q∆(w(j)). (c) The equality Ǧ∆′ = B · Ǧ∆ ·B tr yields Ǧ∆ = B−1 · Ǧ∆′ ·B−tr and (b) applies. This finishes the proof. It follows from Lemma 3.12, that in the situation we are interested in, the unknown matrix B ∈ Mn(Z) defining a Z-congruence ∆ ≈Z ∆′ (that is, the equality Ǧ∆′ = B · Ǧ∆ · B tr holds) satisfies the equation Cox∆′ ·B−B ·Cox∆ = 0. Moreover, the rows w(1), . . . , w(n) of the matrix B = [w(1), . . . , w(n)]tr are roots of the quadratic form q∆(v) = v · Ǧ∆ · v tr. Using these two observations we obtain the following heuristic proce- dure used already in its "positive version" [18, Algorithm 7.5] for positive edge-bipatite graphs. M. Gąsiorek, D. Simson, K. Zając 59 Procedure 3.13. Input: The non-symmetric Gram matrices Ǧ∆, Ǧ∆′ ∈Mn(Z) of a pair of non-negative loop-free edge-bipartite graphs ∆ and ∆′ such that cox∆′(t) = cox∆(t). Output: A Z-invertible matrix B ∈Mn(Z) such that Ǧ∆′ = B · Ǧ∆ · Btr, or error, if the matrix B has not been found. Step 1◦ Compute the Coxeter matrices Cox∆ := −Ǧ∆ · Ǧ −tr ∆ and Cox∆′ := −Ǧ∆′ · Ǧ−tr ∆′ . Step 2◦ By applying [47, Algorithm 3.9] compute a finite root reducer Rred ∆ ⊆ R∆ = {v ∈ Zn; q∆(v) = 1} ⊆ Zn, that is, a finite set of roots of the non-negative quadratic form q∆ : Zn −→ Z, q∆(v) = v · Ǧ∆ · v tr, such that R∆ = Rred ∆ + Kerq∆ . Step 3◦ Construct an n× n square matrix B = [bij ]=[w(1), . . . ,w(n)]tr, with n2 symbolic variables bij , i, j ∈ {1, . . . , n}, and compute the matrix B̃ := [b̃ij ] = Cox∆′ ·B −B · Cox∆. Solve the system b̃ij = 0, for i, j ∈ {1, . . . , n} of n2 linear equations and update the matrix B = [w(1), . . . , w(n)]tr with calculated values. Step 4◦ Find a row w(k) in the matrix B that contains any of the variables bij and proceed to Step 5◦. If there is no such a row then proceed to Step 6◦. Step 5◦ For every root w ∈ Rred ∆ , replace the row w(k) in the matrix B by the vector w, update the matrix B accordingly and proceed recursively with Step 4◦. Step 6◦ If det B = ±1 and Ǧ∆′ = B · Ǧ∆ ·B tr, stop with B as a result. Otherwise continue the search. Step 7◦ If the search is completed and no matrix B has been found return the error. Remark 3.14. Our heuristic Procedure 3.13 is a backtracking algorithm that incrementally checks all possible Z-invertible matrices B =[w(1), . . . ,w(n)]tr, with w(1), . . . , w(n) lying in the finite set Rred ∆ ∪ [Rred ∆ + h] ∪ [Rred ∆ − h], where h ∈ Zn is a generator of Ker q∆, if we assume that ∆ and ∆′ are principal edge-bipartite graphs. Although we have not proved yet any theoretical result that would guarantee the existence of a Z-invertible matrix B of such a form and 60 Algorithmic computation of principal posets satisfying Ǧ∆′ = B · Ǧ∆ ·B tr (assuming that there exists a Z-congruence ∆ ≈Z ∆′), in our experience Procedure 3.13 finds a required matrix in less than a minute, if n ≤ 15. For instance, each of the matrices B1, . . . , B6 listed in the outline of proof of Theorem 1.9 has been computed in several seconds. The following corollary announced in [51, Corollary 11] contains a partial solution of Problem 1.5. Corollary 3.15. Assume that I and J are principal one-peak posets, DI and DJ are their Coxeter-Eulidean types, m = \|I\| = \|J \| and 2 ≤ m ≤ 15. Let Γ(RI , ΦI) and Γ(RJ , ΦJ ) be the ΦJ -mesh translation quivers of roots (see Corollary 3.11). The following conditions are equivalent. (a) DI ∼= DJ . (b) speccI = speccJ . (c) CI ≈Z CJ (i.e., the incidence matrices CI and CJ of I and J are Z-congruent). (d) There exists a group isomorphism h : ZJ → ZI that induces the mesh translation quiver isomorphism h : Γ(RJ , ΦJ) ≃ −→Γ(RI , ΦI). Proof. (a)⇔(c) By Theorem 1.9 (a), we have CI ≈Z ǦDI and CJ ≈Z ǦDJ . Therefore CI ≈Z CJ if and only if DI ∼= DJ . (c)⇒(b) Note that the equality CI = Btr · CJ · B, with a matrix B ∈ Gl(m,Z) implies that CoxI = Btr ·CoxJ ·B −tr, see Lemma 3.12 (a). Hence, coxI(t) = coxJ(t) and speccI = speccJ . (c)⇒(d) Note that the equality CI = B · CJ · B tr, with a matrix B ∈ Gl(m,Z) implies the commutativity of the diagram (3.4), with D and J interchanged. It follows that the group isomorphism h : ZJ → ZI in (3.4) induces the mesh translation quiver isomorphism h : Γ(RJ , ΦJ) ≃ −→Γ(RI , ΦI) see [47], [48, Lemma 4.3], and [50]. (b)⇒(c) Assume that speccI = speccJ , that is, coxI(t) = coxJ(t). Since, by Theorem 1.9 (a), speccDI = speccI = speccJ = speccDJ , the simple analysis of possible Coxeter polynomials (1.13) proves that DI ∼= DJ . Hence, by applying Theorem 1.9 (a) again, we conclude that CI ≈Z CJ . (d)⇒(a) Assume that there exists a mesh translation quiver isomor- phism h : Γ(RJ , ΦJ) ≃ −→Γ(RI , ΦI) induced by a group isomorphism h : ZJ → ZI . By Theorem 1.9 (a), we have the isomorphisms M. Gąsiorek, D. Simson, K. Zając 61 Γ(RDJ , ΦDJ) ∼= Γ(RJ , ΦJ) ∼= Γ(RI , ΦI) ∼= Γ(RDI , ΦDI). Hence, in view of [46, Corollary 5.7], we get the graph isomorphism DI ∼= DJ . The following example shows that the implication (b)⇒(c) in Corol- lary 3.15 does not hold for an arbitrary pair of non-negative posets I and J . We present such a pair that I is principal and J is non-negative of corank two. Example 3.16. Consider the following pair of one-peak posets I and J , with m = 7 vertices. I = 1 2 3 4 5 6 7 J = 1 2 3 4 5 6 7 One easily checks that (a) each of the posets I, J is non-negative, I is principal, J is not principal, and coxI(t) = coxJ(t) = t7 + t6 − t5 − t4 − t3 − t2 + t + 1 = cox D̃6 (t), (b) speccI = speccJ = specc D̃6 , (c) cI =∞, čI = čJ = cJ = 4, (d) Ker qI = Z · [1, 1,−1,−1, 0, 0, 0], (e) Ker qJ = Z · [1, 1,−1,−1, 0, 0, 0]⊕ Z · [1, 1, 0, 0, 1, 1,−2], (f) ∂̃I : Z7 −→ Ker qI , ∂̃I(v) = (v1 + v2 + v3 + v4) · [1, 1,−1,−1, 0, 0, 0], (g) ∂̃J : Z7 −→ Ker qJ is zero. The matrices CI and CJ are not Z-congruent, because the poset I is principal and the poset J is not. 4. Tables of one-peak principal posets of Coxeter-Euclidean types Ẽ6, Ẽ7, and Ẽ8 In this section we present two tables containing all one-peak principal posets of Coxeter-Euclidean types Ẽ6 and Ẽ7, respectively. A correspond- ing table containing all one-peak principal posets J Ẽ8 1 ,. . . , J Ẽ8 422 of the Coxeter-Euclidean type Ẽ8 can be found in [21]. 62 Algorithmic computation of principal posets Table 4.1. Principal one-peak posets of Coxeter-Euclidean type Ẽ6 J Ẽ6 1 J Ẽ6 2 J Ẽ6 3 J Ẽ6 4 J Ẽ6 5 J Ẽ6 6 J Ẽ6 7 1 2 3 4 5 6 ∗ ∗ ∗ ∗ ∗ ∗ 1 2 34 5 6 ∗ J Ẽ6 8 J Ẽ6 9 J Ẽ6 10 J Ẽ6 11 J Ẽ6 12 J Ẽ6 13 J Ẽ6 14 ∗ ∗ ∗ 12 3 4 5 6 ∗ ∗ ∗ ∗ J Ẽ6 15 J Ẽ6 16 J Ẽ6 17 J Ẽ6 18 J Ẽ6 19 J Ẽ6 20 J Ẽ6 21∗ ∗ ∗ ∗ 1 2 3 4 5 6 ∗ ∗ ∗ J Ẽ6 22 J Ẽ6 23 J Ẽ6 24 J Ẽ6 25 J Ẽ6 26 J Ẽ6 27 J Ẽ6 28 ∗ ∗ 12 3 4 5 6 ∗ ∗ ∗ 1 2 3 45 6 ∗ ∗ J Ẽ6 29 J Ẽ6 30 J Ẽ6 31 1 2 3 4 5 6 ∗ ∗ 1 2 3 4 56 ∗ Table 4.2. Principal one-peak posets of Coxeter-Euclidean type Ẽ7 J Ẽ7 1 J Ẽ7 2 J Ẽ7 3 J Ẽ7 4 J Ẽ7 5 J Ẽ7 6 J Ẽ7 7 1 2 3 4 5 6 7 ∗ ∗ ∗ ∗ ∗ ∗ ∗ M. Gąsiorek, D. Simson, K. Zając 63 J Ẽ7 8 J Ẽ7 9 J Ẽ7 10 J Ẽ7 11 J Ẽ7 12 J Ẽ7 13 J Ẽ7 14 ∗ ∗ ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ ∗ J Ẽ7 15 J Ẽ7 16 J Ẽ7 17 J Ẽ7 18 J Ẽ7 19 J Ẽ7 20 J Ẽ7 21 ∗ ∗ ∗ ∗ ∗ ∗ ∗ J Ẽ7 22 J Ẽ7 23 J Ẽ7 24 J Ẽ7 25 J Ẽ7 26 J Ẽ7 27 J Ẽ7 28 ∗ ∗ ∗ ∗ ∗ ∗ ∗ J Ẽ7 29 J Ẽ7 30 J Ẽ7 31 J Ẽ7 32 J Ẽ7 33 J Ẽ7 34 J Ẽ7 35∗ ∗ 1 2 34 5 6 7 ∗ ∗ ∗ ∗ ∗ J Ẽ7 36 J Ẽ7 37 J Ẽ7 38 J Ẽ7 39 J Ẽ7 40 J Ẽ7 41 J Ẽ7 42 ∗ ∗ ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ ∗ J Ẽ7 43 J Ẽ7 44 J Ẽ7 45 J Ẽ7 46 J Ẽ7 47 J Ẽ7 48 J Ẽ7 49∗ ∗ ∗ ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ 64 Algorithmic computation of principal posets J Ẽ7 50 J Ẽ7 51 J Ẽ7 52 J Ẽ7 53 J Ẽ7 54 J Ẽ7 55 J Ẽ7 56 ∗ ∗ ∗ ∗ ∗ ∗ ∗ J Ẽ7 57 J Ẽ7 58 J Ẽ7 59 J Ẽ7 60 J Ẽ7 61 J Ẽ7 62 J Ẽ7 63 ∗ 12 3 4 5 6 7 ∗ ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ ∗ J Ẽ7 64 J Ẽ7 65 J Ẽ7 66 J Ẽ7 67 J Ẽ7 68 J Ẽ7 69 J Ẽ7 70 ∗ ∗ ∗ ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ J Ẽ7 71 J Ẽ7 72 J Ẽ7 73 J Ẽ7 74 J Ẽ7 75 J Ẽ7 76 J Ẽ7 77 ∗ ∗ ∗ ∗ 12 3 4 5 6 7 ∗ ∗ ∗ J Ẽ7 78 J Ẽ7 79 J Ẽ7 80 J Ẽ7 81 J Ẽ7 82 J Ẽ7 83 J Ẽ7 84 1 2 3 4 5 6 7 ∗ ∗ ∗ ∗ 12 3 45 6 7 ∗ ∗ ∗ J Ẽ7 85 J Ẽ7 86 J Ẽ7 87 J Ẽ7 88 J Ẽ7 89 J Ẽ7 90 J Ẽ7 91 ∗ ∗ ∗ ∗ ∗ ∗ ∗ J Ẽ7 92 J Ẽ7 93 J Ẽ7 94 J Ẽ7 95 J Ẽ7 96 J Ẽ7 97 J Ẽ7 98 1 2 3 45 6 7 ∗ ∗ ∗ ∗ ∗ ∗ 12 3 4 5 6 7 ∗ M. Gąsiorek, D. Simson, K. Zając 65 J Ẽ7 99 J Ẽ7 100 J Ẽ7 101 J Ẽ7 102 J Ẽ7 103 J Ẽ7 104 J Ẽ7 105 ∗ ∗ 1 2 34 5 6 7 ∗ ∗ ∗ ∗ 12 3 4 5 6 7 ∗ J Ẽ7 106 J Ẽ7 107 J Ẽ7 108 J Ẽ7 109 J Ẽ7 110 J Ẽ7 111 J Ẽ7 112 ∗ ∗ ∗ 1 2 3 4 5 6 7 ∗ ∗ ∗ 1 2 3 45 6 7 ∗ J Ẽ7 113 J Ẽ7 114 J Ẽ7 115 J Ẽ7 116 J Ẽ7 117 J Ẽ7 118 J Ẽ7 119 ∗ 1 2 3 4 5 6 7 ∗ ∗ 12 3 4 5 6 7 ∗ ∗ ∗ ∗ J Ẽ7 120 J Ẽ7 121 J Ẽ7 122 J Ẽ7 123 J Ẽ7 124 J Ẽ7 125 J Ẽ7 126 1 2 3 4 5 6 7 ∗ ∗ 1 23 4 5 6 7 ∗ ∗ 1 2 3 4 5 6 7 ∗ 1 2 34 56 7 ∗ ∗ J Ẽ7 127 J Ẽ7 128 J Ẽ7 129 J Ẽ7 130 J Ẽ7 131 J Ẽ7 132 12 3 4 5 6 7 ∗ ∗ 1 2 3 4 5 6 7 ∗ ∗ 1 2 3 4 5 6 7 ∗ 1 23 4 56 7 ∗ Remark 4.3. The computational technique introduced in this paper is applied and developed in [22] for non-negative posets of corank two. References [1] I. Assem, D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, Volume 1. Techniques of Representation Theory, London Math. Soc. Student Texts 65, Cambridge Univ. Press, Cambridge-New York, 2006, doi: d10.1017/CBO9780511614309. [2] M. Barot and J.A. de la Peña, The Dynkin type of a non-negative unit form, Expo. Math. 17(1999), 339–348. [3] V. M. Bondarenko, V. Futorny, T. Klimchuk, V.V. Sergeichuk and K. Yusenko, Systems of subspaces of a unitary space, Linear Algebra Appl. 438(2013), 2561-2573, doi: 10.1016/j.laa.2012.10.038. [4] V. M. Bondarenko and M. V. Stepochkina, On posets of width two with positive Tits form, Algebra and Discrete Math. 2(2005), no. 2, 20–35. 66 Algorithmic computation of principal posets [5] V. M. Bondarenko and M. V. Stepochkina, On finite posets of inj-finite type and their Tits form, Algebra and Discrete Math. 2(2006), 17–21. [6] V. M. Bondarenko and M. V. Stepochkina, (Min, max)-equivalency of posets and nonnegative Tits forms, Ukrain. Mat. Zh. 60(2008), pp. 1157–1167, doi: 10.1007/s11253-009-0147-7. [7] V. M. Bondarenko and M. V. Stepochkina, Description of posets critical with respect to the nonnegativity of the quadratic Tits form, Ukrain. Mat. Zh. 61(2009), 611–624, doi: 10.1007/s11253-009-0245-6. [8] D. M. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75, Cambridge Univ. Press, Cambridge-New York, 2010, doi: 10.1017/CBO9780511801518. [9] P. Dräxler, J. A. Drozd, N. S. Golovachtchuk, S. A. Ovsienko, M. Zeldych, Towards the classification of sincere weakly positive unit forms, Europ. J. Combinat. 16 (1995), 1-16. [10] J. A. Drozd, Coxeter transformations and representations of partially ordered sets, Funkc. Anal. i Priložen. 8(1974), 34–42 (in Russian). [11] Ju. A. Drozd and V. V. Kirichenko, Finite Dimensional Algebras, Springer-Verlag, Berlin, 1994. [12] M. Felisiak, Computer algebra technique for Coxeter spectral study of edge-bipartite graphs and matrix morsifications of Dynkin type An, Fund. Inform. 125(2013), 21-49; doi: 10.3233/FI-2013-851. [13] M. Felisiak and D. Simson, Experiences in computing mesh root systems for Dynkin diagrams using Maple and C++, 13th Intern. Symposium on Sym- bolic and Numeric Algorithms for Scientific Computing, SYNASC11, Timisoara, September 2011, IEEE Computer Society, IEEE CPS, Tokyo, 2011, pp.83–86, doi: 10.1109/SYNASC.2011.41. [14] M. Felisiak and D. Simson, On computing mesh root systems and the isotropy group for simply-laced Dynkin diagrams, Proc. 14th Intern. Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC12, Timisoara, 2012, IEEE CPS Computer Society, IEEE CPS, Tokyo, 2012, pp. 91-98, Washington-Tokyo, 2012, doi: 10.1109/SYNASC.2012.16. [15] M. Felisiak and D. Simson, On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram An, Discrete Math. 313(2013), 1358–1367, doi: 10.1016/j.disc.2013.02.003. [16] F. R. Gantmacher, The Theory of Matrices, Vol.1, Chelsea Publishing Company, New York, 1984. [17] M. Gąsiorek, and D. Simson, Programming in PYTHON and an algorithmic description of positive wandering on one-peak posets, Electronic Notes in Discrete Mathematics 38(2011), 419-424, doi: 10.1016/j.endm.2011.09.068. [18] M. Gąsiorek and D. Simson, One-peak posets with positive Tits quadratic form, their mesh translation quivers of roots, and programming in Maple and Python, Linear Algebra Appl. 436(2012), 2240–2272, doi: 10.1016/j.laa. 2011.10.045. [19] M. Gąsiorek and D. Simson, A computation of positive one-peak posets that are Tits sincere, Colloq. Math. 127(2012), 83–103. M. Gąsiorek, D. Simson, K. Zając 67 [20] M. Gąsiorek, D. Simson and K. Zając, On Coxeter spectral study of posets and a digraph isomorphism problem, Proc. 14th Intern. Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC12, Timisoara, 2012, IEEE CPS Computer Society, IEEE CPS, Tokyo, 2012, pp. 369-375, Washington-Tokyo, 2012, doi: 10.1109/SYNASC.2012.56. [21] M. Gąsiorek, D. Simson and K. Zając, Tables of one-peak princi- pal posets of Coxeter-Euclidean type Ẽ8, http://mg.mat.umk.pl/pdf/ OnePeakPrincipalPosetsE8Tables.pdf. [22] M. Gąsiorek, D. Simson and K. Zając, Experimental computation of non-negative posets of corank two and their Coxeter polynomials, Algebra and Discrete Mathe- matics, submitted. [23] Y. Han and D. Zhao, Superspecies and their representations, J. Algebra 321(2009), 3668–3680, doi: 10.1016/j.jalgebra.2009.03.028. [24] D. Happel, Triangulated categories in the representation theory of finite dimen- sional algebras, London Math. Soc. Lecture Notes Series, Vol. 119, 1988, doi: 10.1017/CBO9780511629228. [25] R.A. Horn and V. V. Sergeichuk, Congruences of a square matrix and its transpose, Linear Algebra Appl. 389(2004), 347–353, doi: 10.1016/j.laa.2004.03.010. [26] A. Kisielewicz and M. Szykuła, Rainbow induced subgraphs in proper vertex colorings, Fund. Inform. 111(2011), 437–451, doi: 10.3233/FI-2011-572. [27] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and Discrete Math. 4(2008), 49-79. [28] J. Kosakowska, Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms, Fund. Inform. 119(2012), 149-162, doi: 10.3233/FI-2012- 731. [29] S. Ladkani, On the periodicity of Coxeter transformations and the non- negativity of their Euler forms, Linear Algebra Appl. 428(2008), 742–753, doi: 10.1016/j.laa.2007.08.002. [30] P. Lakatos, On the Coxeter polynomials of wild stars, Linear Algebra Appl. 293(1999), 159–170, doi: 10.1016/S0024-3795(99)00033-6. [31] P. Lakatos, On spectral radius of Coxeter transformation of trees, Public. Math. 54(1999), 181–187. [32] P. Lakatos, Additive functions on trees, Colloq. Math. 89(2001), 135–145, doi: 10.4064/cm89-1-10. [33] H. Lenzing and J.A de la Peña, Spectral analysis of finite dimensional algebras and singularities, In: Trends in Representation Theory of Algebras and Related Topics, ICRA XII, (ed. A. Skowroński), Series of Congress Reports, European Math. Soc. Publishing House, Zürich, 2008, pp. 541–588. [34] G. Marczak, A. Polak and D. Simson, P -critical integral quadratic forms and positive unit forms. An algorithmic approach, Linear Algebra Appl. 433(2010), 1873–1888; doi: 10.1016/j.laa.2010.06.052. [35] S. A. Ovsienko, Integral weakly positive forms, in Schur Matrix Problems and Quadratic Forms, Inst. Mat. Akad. Nauk USSR, Preprint 78.25 (1978), pp. 3–17 (in Russian). 68 Algorithmic computation of principal posets [36] A. Polak and D. Simson, Symbolic and numerical computation in determining P -critical unit forms and Tits P -critical posets, Electronic Notes in Discrete Mathematics 38(2011), 723-730, doi: 10.1016/j.endm.2011.10.021. [37] A. Polak and D. Simson, Algorithms computing O(n,Z)-orbits of P -critical edge- bipartite graphs and P -critical unit forms using Maple and C#, Algebra and Discrete Mathematics, 16(2013), No. 2, 242-286. [38] A. Polak and D. Simson, Coxeter spectral classification of almost T P -critical one-peak posets using symbolic and numeric computations, Linear Algebra Appl. 445 (2014), 223-255, doi: 10.1016/j.laa. 2013.12.018. [39] Pu Zhang and C. Xiao-Wu, Comodules of Uq(sl2) and modules of SLq(2) via quiver methods, J. Pure Appl. Algebra 211(2007), 862–876, doi: 10.1016/j.jpaa.2007.03.010. [40] Yu. Samoilemko and K. Yusenko, Kleiner’s theorem for unitary representations of posets, Linear Algebra Appl. 437(2012), 581–588; doi: 10.1016/j.laa.2012.02.030. . [41] M. Sato, Periodic Coxeter matrices and their associated quadratic forms, Linear Algebra Appl. 406(2005), 99–108, doi: 10.1016//j.laa. 2005.03.036. [42] V. V. Sergeichuk, Canonical matrices for linear matrix problems, Linear Algebra Appl. 317(2000), 53–102, doi: 10.1016/S0024-3795(00)00150-6. [43] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space Categories, Algebra, Logic and Applications, Vol. 4, Gordon & Breach Science Publishers, 1992. [44] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories, Colloq. Math. 115(2009), 259–295, doi: 10.4064/cm115-2-9. [45] D. Simson, Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets, Linear Algebra Appl. 433(2010), 699–717; doi: 10.1016/j.laa.2010.03.04. [46] D. Simson, Mesh geometries of root orbits of integral quadratic forms, J. Pure Appl. Algebra, 215(2011), 13–34, doi: 10.1016/j.jpaa.2010.02.029. [47] D. Simson, Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots, Fund. Inform. 109(2011), 425–462, doi: 10.3233/FI-2011- 603. [48] D. Simson, Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams, Fund. Inform. 123(2013), 447–490, doi: 10.3233/FI-2013-820. [49] D. Simson, A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits, Fund. Inform. 124(2013), 309-338, doi: 10.3233/FI-2013-836. [50] D. Simson, A Coxeter-Gram classification of positive simply laced edge-bipartite graphs, SIAM J. Discrete Math. 27(2013), 827–854, doi: 10.1137/110843721. [51] D. Simson and K. Zając, A framework for Coxeter spectral classification of finite posets and their mesh geometries of roots, Intern. J. Math. Mathematical Sciences, Volume 2013, Article ID 743734, 22 pages, doi: 10.1155/2013/743734. M. Gąsiorek, D. Simson, K. Zając 69 [52] D. Simson and K. Zając, An inflation algorithm and a toroidal mesh algorithm for edge-bipartite graphs, Electronic Notes in Discrete Mathematics 40(2013), 377–383, doi: 10.1016/j.endm.2013.05.066. [53] D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, Volume 2. Tubes and Concealed Algebras of Euclidean Type, London Math. Soc. Student Texts 71, Cambridge Univ. Press, Cambridge-New York, 2007, doi: 10.1017/CBO9780511619212. [54] D. Simson and M. Wojewódzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83(2008), 389–410. [55] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17(1989), 2347-2362, doi: 10.1080/00927878908823853. [56] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4(1982), 47–74, doi: 10.1016/0166-218X(82)90033-6. Contact information M. Gąsiorek Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, 87-100 Toruń, Poland E-Mail: mgasiorek@mat.uni.torun.pl D. Simson Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, 87-100 Toruń, Poland E-Mail: simson@mat.uni.torun.pl K. Zając Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, 87-100 Toruń, Poland E-Mail: zajac@mat.uni.torun.pl Received by the editors: 08.08.2013 and in final form 08.08.2013.

Algorithmic computation of principal posets using Maple and Python

Репозитарії

Схожі ресурси