Computer Algebra Technique for Coxeter Spectral Study of Edge-bipartite Graphs and Matrix Morsifications of Dynkin Type A_n

• Autorzy: Felisiak M.
• Języki publikacji: EN

Abstrakty

EN

By applying computer algebra tools (mainly, Maple and C++), given the Dynkin diagram ∆ = An, with n > 2 vertices and the Euler quadratic form q_∆ : Zn → Z, we study the problem of classifying mesh root systems and the mesh geometries of roots of A (see Section 1 for details). The problem reduces to the computation of the Weyl orbits in the set Mor_∆ ⊆ Mn(Z) of all matrix modifications A of q_∆, i.e., the non-singular matrices A ∈ Mn(Z) such that (i) q_∆ (v) = v A vtr, for all v ∈ Zn, and (ii) the Coxeter matrix CoxA := —A A-tr lies in Gl(n, Z). The Weyl group W_∆ ⊆ Gl(n, Z) acts on MorA and the determinant det A ∈ Z, the order cA > 2 of CoxA (i.e. the Coxeter number), and the Coxeter polynomial coxA(t) := det(t E — CoxA) ∈ Z[t] are W_∆ -invariant. The problem of determining the W_∆ -orbits Orb(A) of MorA and the Coxeter polynomials coxA(t), with A e MorA, is studied in the paper and we get its solution for n < 8, and A = [a_ij] ∈ MorAn, with [a_ij] | < 1. In this case, we prove that the number of the W_∆ - orbits Orb(A) and the number of the Coxeter polynomials coxA(t) equals two or three, and the following three conditions are equivalent: (i) Orb(A) = Orb(A'), (ii) coxA(t) = coxA> (t), (iii) cA det A = cA det A!. We also construct: (a) three pairwise different W_∆ -orbits in Mor_∆, with pairwise different Coxeter polynomials, if ∆ = A2m-i and m > 3; and (b) two pairwise different W_∆ -orbits in Mor_∆, with pairwise different Coxeter polynomials, if ∆ = A2m and m > 1.

Słowa kluczowe

EN

algebra; spectral geometry; bipartite graphs; graph theory; singularities mathematics; polynomials

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 1
• Strony: 21--49
• Opis fizyczny: Bibliogr. 45 poz.

Twórcy

autor

Felisiak M.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland

Bibliografia

• [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.
• [2] M. Barot, A characterization of positive unit forms, II, Bol. Soc. Mat. Mexicana (3) 7 (2001), 13-22.
• [3] M. Barot, D. Kussin and H. Lenzing, The Lie algebra associated to a unit form, J. Algebra 296 (2007), 1-17.
• [4] M. Barot and J.A. de la Pena, The Dynkin type of a non-negative unit form, Expo. Math. 17 (1999), 339-348.
• [5] 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.
• [6] V. M. Bondarenko and M. V. Styopochkina, On posets of width two with positive Tits form, Algebra and Discrete Math. 2 (2005), 20-35.
• [7] 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.
• [8] V. M. Bondarenko and M. V. Stepochkina, (Min, max)-equivalency of posets and nonnegative Tits forms, Ukrain. Mat. Zh. 60 (2008), pp. 1157-1167.
• [9] N. Bourbaki, Grupes et algebres de Lie, Ch. IV-VI, Hermann & Co. Paris, 1960.
• [10] M. Broersma, A. Capponi and G. Paulusma, A new algorithm for on-line coloring bipartite graphs, SIAM J. Discrete Math. 22 (2008), 72-91.
• [11] R.A. Brualdi and D. M. Cvetkovic, A Combinatorial Approach to Matrix Theory and its Application, CRS Press (Boca Raton), 2008.
• [12] D. M. Cvetkovic, P. Rowlinson and S. Simic, An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75, Cambridge Univ. Press, Cambridge-New York, 2010.
• [13] M. Felisiak and D. Simson, On combinatorial algorithms computing mesh root systems and matrix morsifi-cations for the Dynkin diagram An, Discrete Math. 313 (2013), 1358-1367, doi: 10.1016/j.disc.2013.02.003.
• [14] M. Gasiorek and D. Simson, One-peak posets with positive Tits quadratic form, their mesh translation quiv-ers of roots, and programming in Maple and Python, Linear Algebra Appl. 436 (2012), 2240-2272, doi: 10.1016/j.laa. 2011.10.045.
• [15] M. Gasiorek and D. Simson, A computation of positive one-peak posets that are Tits sincere, Colloq. Math. 127 (2012), 83-103, doi:10.4064/cm127-1-6.
• [16] D. Happel, Tilting sets on cylinders, Proc. London Math. Soc. 51 (1985), 21-55.
• [17] J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advances Mathematics 29, Cambridge University Press, 1990.
• [18] 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.
• [19] J. Kosakowska, Lie algebras associated with quadratic forms and their applications to Ringel-Hall algebras, Algebra and Discrete Math. 4 (2008), 49-79.
• [20] 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.
• [21] S. Ladkani, On the periodicity of Coxeter transformations and the non-negativity of their Euler forms, Linear Algebra Appl. 428 (2008), 742-753.
• [22] P. Lakatos, Additive functions on trees, Colloq. Math. 89 (2001), 135-145.
• [23] G. Marczak, A. Polak and D. Simson, P-critical integral quadratic forms and positive forms. An algorithmic approach, Linear Algebra Appl. 433 (2010), 1873-1888, doi: 10.1016/j.laa. 2010.06.052.
• [24] J. V. Matijasevich, Enumerable sets are Diophantine, Doklady Akad. Nauk SSSR. 191 (1970), 279-282, (in Russian).
• [25] S. Nowak and D. Simson, Locally Dynkin quivers and hereditary coalgebras whose left comodules are direct sums of finite-dimensional comodules, Comm. Algebra 30 (2002), 455-476.
• [26] A. Polak and D. Simson, One-peak posets with almost P-critical Tits form and a spectral Coxeter classifica-tion using computer algebra tools, Europ. J. Combin. 2013, to appear.
• [27] 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.
• [28] J.P. Serre, Algebres de Lie simples-complexes, Benjamin, 1966.
• [29] D. Simson, Linear Representations of Partially Ordered Sets and Vector Space Categories, Algebra, Logic and Applications, Vol. 4, Gordon & Breach Science Publishers, 1992.
• [30] D. Simson, A reduction functor, tameness, and Tits form for a class of orders, J. Algebra 174 (1995), 439-452.
• [31] D. Simson, An Artin problem for division ring extensions and the pure semisimplicity conjecture, I, Arch. Math. 66 (1996), 114-122. 227(2000), 670-705.
• [32] D. Simson, Incidence coalgebras of intervally finite posets, their integral quadratic forms and comodule categories, Colloq. Math. 115 (2009), 259-295.
• [33] 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.
• [34] D. Simson, Coalgebras of tame comodule type, comodule categories, and a tame-wild dichotomy problem, Proc. Conf. „Representation Theory and Related Topics” (ICRA-XIV Tokyo), (eds: A. Skowromki and K. Yamagata), Series of Congress Reports, European Math. Soc. Publishing House, Zurich, 2011, pp. 561-660.
• [35] 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.
• [36] 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.
• [37] D. Simson, Algorithms determining matrix modifications, Weyl orbits, Coxeter polynomials and mesh ge-ometries of roots for Dynkin diagrams, Fund. Inform. 123 (2013), 447-490, doi: 10.3233/FI-2012-820.
• [38] D. Simson, A Coxeter-Gram classification of positive simply-laced edge-bipartite graphs, SIAM J. Discrete Math. 27 (2013), in press.
• [39] D. Simson, A framework for Coxeter spectral analysis of loop-free edge-bipartite graphs, their rational mor- sifications and mesh geometries of root orbits, Fund. Inform. 124 (2013), 59-88, doi: 10.3233/FI-2013-835.
• [40] D. Simson, Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4, Fund. Inform. 124 (2013), 89-114, doi: 10.3233/FI-2013-836.
• [41] D. Simson and A. Skowromki, Elements of the Representation Theory of Associative Algebras, Volume 3. Representation-Infinite Tilted Algebras, London Math. Soc. Student Texts 72, Cambridge Univ.Press, Cambridge-New York, 2007.
• [42] D. Simson and M. Wojewodzki, An algorithmic solution of a Birkhoff type problem, Fund. Inform. 83 (2008), 389-410.
• [43] Y. Zhang, Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver, Comm. Algebra 17 (1989), 2347-2362.
• [44] Y. Zhang, Unified tame theorem, Sci. China Ser. A 52 (2009), 2036-2068.
• [45] http://www.gap-system.org/Gap3/gap3.html