Algorithmic computation of principal posets using Maple and Python

Marcin Gąsiorek ; Daniel Simson ; Katarzyna Zając

Algebra and discrete mathematics, Tome 17 (2014) no. 1, pp. 33-69.

Résumé

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 $G_I : = \frac{1}{2}[C_I+ C^{tr}_I]\in\mathbb{M}_I(\mathbb{Q})$ of $I$ is positive semi-definite of corank one, where $C_I\in\mathbb{M}_I(\mathbb{Z})$ is the incidence matrix of $I$. With any such a connected poset $I$, we associate a simply laced Euclidean diagram $DI\in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n, \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$, the Coxeter matrix ${\rm Cox}_I:= - C_I\cdot C^{-tr}_I$, its complex Coxeter spectrum ${\mathbf{specc}}_I$, and a reduced Coxeter number $\check {\mathbf{c}}_I$. One of our aims is to show that the spectrum ${\mathbf{specc}}_I$ of any such a poset $I$ determines the incidence matrix $C_I$ (hence the poset $I$) uniquely, up to a $\mathbb{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 $\leq 15$, together with ${\mathbf{specc}}_I$, $\check {\mathbf{c}}_I$, the incidence defect $\partial_I:\mathbb{Z}^I \to\mathbb{Z}$, and the Coxeter-Euclidean type $DI$. In case when $DI \in \{\widetilde{\mathbb{A}}_n, \widetilde{\mathbb{D}}_n , \widetilde{\mathbb{E}}_6, \widetilde{\mathbb{E}}_7, \widetilde{\mathbb{E}}_8\}$ and $n:=|I|$ is relatively small, we show that given such a principal poset $I$, the incidence matrix $ C_I$ is $\mathbb{Z}$-congruent with the non-symmetric Gram matrix $ \check G_{DI}$ of $DI$, ${\mathbf{specc}}_I = {\mathbf{specc}}_{DI}$ and $\check {\mathbf{c}}_I= \check {\mathbf{c}}_{DI}$. Moreover, given a pair of principal posets $I$ and $J$, with $|I|= |J| \leq 15$, the matrices $C_I$ and $C_J$ are $\mathbb{Z}$-congruent if and only if ${\mathbf{specc}}_I= {\mathbf{specc}}_J$.

Détail

Keywords: principal poset; edge-bipartite graph; unit quadratic form; computer algorithm; Gram matrix, Coxeter spectrum.
Mots-clés : Coxeter polynomial

Bibliographie

[1] I. Assem, D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, v. 1, London Math. Soc. Student Texts, 65, Techniques of Representation Theory, Cambridge Univ. Press, Cambridge–New York, 2006 | DOI | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[4] V. M. Bondarenko and M. V. Stepochkina, “On posets of width two with positive Tits form”, Algebra and Discrete Math., 2005, no. 2, 20–35 | MR | Zbl

[5] V. M. Bondarenko and M. V. Stepochkina, “On finite posets of inj-finite type and their Tits form”, Algebra and Discrete Math., 2006, no. 2, 17–21 | MR | Zbl

[6] V. M. Bondarenko and M. V. Stepochkina, “(Min, max)-equivalency of posets and nonnegative Tits forms”, Ukrain. Mat. Zh., 60 (2008), 1157–1167 | DOI | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[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 | DOI | MR | Zbl

[10] J. A. Drozd, “Coxeter transformations and representations of partially ordered sets,”, Funkc. Anal. i Priložen., 8 (1974), 34–42 (in Russian) | MR | Zbl

[11] Ju. A. Drozd and V. V. Kirichenko, Finite Dimensional Algebras, 1994, Springer-Verlag, Berlin | DOI | MR | Zbl

[12] M. Felisiak, “Computer algebra technique for Coxeter spectral study of edge-bipartite graphs and matrix morsifications of Dynkin type $\mathbb{A}_n$”, Fund. Inform., 125 (2013), 21–49 | DOI | MR | Zbl

[13] M. Felisiak and D. Simson, “Experiences in computing mesh root systems for Dynkin diagrams using Maple and C++”, 13th Intern. Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC11 (Timisoara, September 2011), IEEE Computer Society, IEEE CPS, Tokyo, 2011, 83–86 | DOI

[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, 91–98

[15] M. Felisiak and D. Simson, “On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram $\mathbb{A}_n$”, Discrete Math., 313 (2013), 1358–1367 | DOI | MR | Zbl

[16] F. R. Gantmacher, The Theory of Matrices, v. 1, Chelsea Publishing Company, New York, 1984 | MR

[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

[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 | MR

[19] M. Gąsiorek and D. Simson, “A computation of positive one-peak posets that are Tits sincere”, Colloq. Math., 127 (2012), 83–103 | DOI | MR

[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, 369–375

[21] M. G{ą}siorek, D. Simson and K. Zaj{ą}c, Tables of one-peak principal posets of Coxeter-Euclidean type $\widetilde{\mathbb{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 Mathematics, submitted

[23] Y. Han and D. Zhao, “Superspecies and their representations”, J. Algebra, 321 (2009), 3668–3680 | DOI | MR | Zbl

[24] D. Happel, Triangulated categories in the representation theory of finite dimensional algebras, London Math. Soc. Lecture Notes Series, 119, 1988 | DOI | MR | Zbl

[25] R. A. Horn and V. V. Sergeichuk, “Congruences of a square matrix and its transpose”, Linear Algebra Appl., 389 (2004), 347–353 | DOI | MR | Zbl

[26] A. Kisielewicz and M. Szykuła, “Rainbow induced subgraphs in proper vertex colorings”, Fund. Inform., 111 (2011), 437–451 | DOI | MR | Zbl

[27] J. Kosakowska, “Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras”, Algebra and Discrete Math., 2008, no. 4, 49–79 | MR | Zbl

[28] J. Kosakowska, “Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms”, Fund. Inform., 119 (2012), 149–162 | DOI | MR | Zbl

[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 | MR | Zbl

[30] P. Lakatos, “On the Coxeter polynomials of wild stars”, Linear Algebra Appl., 293 (1999), 159–170 | DOI | MR | Zbl

[31] P. Lakatos, “On spectral radius of Coxeter transformation of trees”, Public. Math., 54 (1999), 181–187 | MR | Zbl

[32] P. Lakatos, “Additive functions on trees”, Colloq. Math., 89 (2001), 135–145 | DOI | MR | Zbl

[33] H. Lenzing and J.A de la Peña, “Spectral analysis of finite dimensional algebras and singularities”, Trends in Representation Theory of Algebras and Related Topics, ICRA XII, Series of Congress Reports, ed. A. Skowroński, European Math. Soc. Publishing House, Zürich, 2008, 541–588 | MR | Zbl

[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 | MR | Zbl

[35] S. A. Ovsienko, “Integral weakly positive forms”, Schur Matrix Problems and Quadratic Forms, Inst. Mat. Akad. Nauk USSR, 1978, 3–17, Preprint 78.25 (in Russian) | MR

[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 | Zbl

[37] A. Polak and D. Simson, “Algorithms computing ${\rm O}(n, \mathbb{Z})$-orbits of $P$-critical edge-bipartite graphs and $P$-critical unit forms using Maple and C#”, Algebra and Discrete Mathematics, 16:2 (2013), 242–286 | MR

[38] A. Polak and D. Simson, “Coxeter spectral classification of almost $TP$-critical one-peak posets using symbolic and numeric computations”, Linear Algebra Appl., 445 (2014), 223–255 | DOI | MR | Zbl

[39] Pu Zhang and C. Xiao-Wu, “Comodules of $U_q({\rm sl}_2)$ and modules of $SL_q(2)$ via quiver methods”, J. Pure Appl. Algebra, 211 (2007), 862–876 | DOI | MR | Zbl

[40] Yu. Samoilemko and K. Yusenko, “Kleiner's theorem for unitary representations of posets”, Linear Algebra Appl., 437 (2012), 581–588 | DOI | MR

[41] M. Sato, “Periodic Coxeter matrices and their associated quadratic forms”, Linear Algebra Appl., 406 (2005), 99–108 | DOI | MR | Zbl

[42] V. V. Sergeichuk, “Canonical matrices for linear matrix problems”, Linear Algebra Appl., 317 (2000), 53–102 | DOI | MR | Zbl

[43] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space Categories, Algebra Logic and Applications, 4, Gordon Breach Science Publishers, 1992 | MR | Zbl

[44] D. Simson, “Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories”, Colloq. Math., 115 (2009), 259–295 | DOI | MR | Zbl

[45] D. Simson, “Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets”, Linear Algebra Appl., 433 (2010), 699–717 | DOI | MR | Zbl

[46] D. Simson, “Mesh geometries of root orbits of integral quadratic forms”, J. Pure Appl. Algebra, 215 (2011), 13–34 | DOI | MR | Zbl

[47] D. Simson, “Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots”, Fund. Inform., 109 (2011), 425–462 | DOI | MR | Zbl

[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 | MR | Zbl

[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 | MR | Zbl

[50] D. Simson, “A Coxeter-Gram classification of positive simply laced edge-bipartite graphs”, SIAM J. Discrete Math., 27 (2013), 827–854 | DOI | MR | Zbl

[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, 2013, Article ID 743734, 22 pp. | DOI | MR | Zbl

[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

[53] D. Simson and A. Skowroński, Elements of the Representation Theory of Associative Algebras, v. 2, London Math. Soc. Student Texts, 71, Tubes and Concealed Algebras of Euclidean Type, Cambridge Univ. Press, Cambridge-New York, 2007 | DOI | MR | Zbl

[54] D. Simson and M. Wojewódzki, “An algorithmic solution of a Birkhoff type problem”, Fund. Inform., 83 (2008), 389–410 | MR | Zbl

[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 | MR | Zbl

[56] T. Zaslavsky, “Signed graphs”, Discrete Appl. Math., 4 (1982), 47–74 | DOI | MR | Zbl