Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 1], A Gram Classification

• Autorzy: Simson D.

Identyfikatory

DOI

10.3233/FI-2016-1345

• Języki publikacji: EN

Abstrakty

EN

We continue the Coxeter spectral study of the category UBigr_m of loop-free edge-bipartite (signed) graphs Δ, with m ≥ 2 vertices, we started in [SIAM J. Discr. Math. 27(2013), 827-854] for corank r = 0 and r = 1. Here we study the class of all non-negative edge-bipartite graphs Δ ∈ UBigr_n+r of corank r ≥ 0, up to a pair of the Gram Z-congruences ~ z and ≈z, by means of the non-symmetric Gram matrix G_Δ∈ M_n+r(Z), the symmetric Gram matrix G_Δ:=[formula..]..., the Coxeter matrix Cox_Δ:=[formula...]... and its spectrum speccΔ ⊂ C, called the Coxeter spectrum of Δ. One of the aims in the study of the category UBigr_n+r is to classify the equivalence classes of the non-negative edge-bipartite graphs in UBigr_n+r with respect to each of the Gram congruences ~Z and ≈Z. In particular, the Coxeter spectral analysis question, when the strong congruence Δ≈_ZΔ′ holds (hence also Δ_ZΔ′ holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ UBigr_n+r such that specc_Δ = specc_Δ′, is studied in the paper. One of our main aims is an algorithmic description of a matrix B defining the Gram Z-congruences Δ≈_ZΔ′ and Δ_ZΔ′, that is, a Z-invertible matrix B∈M_n+r(Z) such that ..., respectively. We show that, given a connected non-negative edge-bipartite graph Δ in UBigr_n+r of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension ... of D of corank r (constructed in Section 2) such that Δ_~ZD. We also show that every matrix B defining the strong Gram Z-congruence Δ_≈ZΔ′ in UBigr_n+r has the form [formula...], where C_Δ,C_Δ′∈M_n+r(Z) are fixed Z-invertible matrices defining the weak Gram congruences Δ_~Z ... and Δ′_~ZD with an r-vertex extended graph ..., respectively, and B ∈M_n+r(Z) is Z-invertible matrix lying in the isotropy group ... Moreover, each of the columns k∈Z^n+r of B is a root of Z, i.e., ... Algorithms constructing the set of all such matrices B are presented in case when r = 0. We essentially use our construction of a morsification reduction map ... that reduces (up to ≈Z) the study of the set UBigr... of all connected non-negative edge-bipartite graphs Δ in UBigr_D such that ... to the study of G1(n+r,Z)_D-orbits in the set Mor_D⊆G1(n+r,Z) of all matrix morsifications of the graph D.

Słowa kluczowe

EN

signed graph; Gram congruence; Coxeter spectrum; symbolic algorithms; Coxeter-Dynkin type; isotropy group

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 1
• Strony: 19--48
• Opis fizyczny: Bibliogr. 64 poz., tab.

Twórcy

autor

Simson D.

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

Bibliografia

• [1] Assem I, Simson D, Skowroński A. 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: 10.1017/CBO9780511614309.
• [2] Barot M, de la Peña JA. The Dynkin type of a non-negative unit form. Exposition. Math. 1999; 17(4): 339–348.
• [3] Barot M, de la Peña JA. Root-induced integral quadratic forms. Linear Algebra Appl. 2006; 412: 291-302.
• [4] Bocian R, Felisiak M, Simson D. Numeric and mesh algorithms for the Coxeter spectral study of positive edge-bipartite graphs and their isotropy groups. J. Comput. Appl. Math. 259: 2014; 815–827. doi:10.1016/j.cam.2013.07.013.
• [5] Bocian R, Felisiak M, Simson D. On Coxeter type classification of loop-free edge-bipartite graphs and matrix morsifications. In: Proc. 15th Intern. Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2013, Timi¸ soara, 2013, IEEE Computer Society. IEEE CPS, Tokyo, 2014, pp. 115-118. doi: 10.1109/SYNASC.2013.22
• [6] Brualdi RA. The Mutually Beneficial Relationship of Graphs and Matrices, CBMS. No. 115, 2011.
• [7] Cvetković D, Rowlinson P, Simić S. An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75, Cambridge Univ. Press, Cambridge-New York, 2010.
• [8] Drozd JA. Coxeter transformations and representations of partially ordered sets. Funkc. Anal. i Priložen. 1974: 8; 34–42 (in Russian).
• [9] Felisiak M. Computer algebra technique for Coxeter spectral study of edge-bipartite graphs and matrix morsifications of Dynkin type An. Fund. Inform. 2013: 125; 21-49.
• [10] Felisiak M, Simson D. On computing mesh root systems and the isotropy group for simply laced Dynkin diagrams. In: 14th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, IEEE Computer Society. IEEE CPS, Tokyo, 2012, 91–97. doi: 10.1109/SYNASC.2012.16.
• [11] Felisiak M, Simson D. On combinatorial algorithms computing mesh root systems and matrix morsifications for the Dynkin diagram An. Discrete Math. 2013: 313; 1358-1367. doi: 10.1016/j.disc.2013.02.003.
• [12] Felisiak M, Simson D. Applications of matrix morsifications to Coxeter spectral study of loop-free edgebipartite graphs, Discrete Appl. Math. 2015: 192; 49-64. doi: 10.1016/j.dam.2014.05.002.
• [13] Gabriel P, Roiter AV. Representations of Finite Dimensional Algebras. Algebra VIII, Encyclopaedia of Math. Sc., Vol. 73, Springer-Verlag, Berlin, Heidelberg, New York, 1992.
• [14] Gantmacher P. „Matrizenrechnung", Deutsche Verlag der Wissenschaften, 1959.
• [15] Gąsiorek M. Efficient computation of the isotropy group of a finite graph: a combinatorial approach. In: SYNASC 2013, Timisoara, September 2013, IEEE Computer Society. IEEE CPS, Tokyo, 2014, pp. 104-111. doi: 10.1109/SYNASC.2013.21.
• [16] Gąsiorek M. Obliczenia symboliczne i algorytmy kombinatoryczne w spektralnej klasyfikacji skończonych zbiorów częściowo uporządkowanych. Ph.D. Thesis, University of Warsaw, 2016.
• [17] Gąsiorek M, Simson D. One-peak posets with positive Tits quadratic form, their mesh translation quivers of roots, and programming in Maple and Python. Linear Algebra Appl. 2012: 436; 2240–2272,. doi:10.1016/j.laa. 2011.10.045.
• [18] Gąsiorek M, Simson D. A computation of positive one-peak posets that are Tits-sincere. Colloq. Math. 2012:127; 83–103. DOI: 10.4064/cm127-1-6.
• [19] Gąsiorek M, Simson D. A classification of positive posets using isotropy groups of Dynkin diagrams. In: EuroComb 2013; Centro di Riserca Matematica Series (Edicioni della Normale, Scuola Normale Superiore Pisa), Vol 16, 2013, pp. 599–605.
• [20] Gąsiorek M, Simson D, Zając K. Algorithmic computation of principal posets using Maple and Python. Algebra and Discrete Math. 2014: 17; 33–69.
• [21] Gąsiorek M, Simson D, Zając K. On corank two edge-bipartite graphs and simply extended Euclidean diagrams. In: SYNASC 2014, IEEE Computer Society, IEEE CPS, Tokyo, 2014, pp. 66-73. doi:10.1109/SYNASC.2014.17.
• [22] Gąsiorek M, Simson D, Zając K. Structure and a Coxeter-Dynkin type classification of corank two nonnegative posets. Linear Algebra Appl. 2015: 469; 76-113. doi: 10.1016/j.laa.2014.11.003.
• [23] Gąsiorek M, Simson D, Zając K. On Coxeter type study of non-negative posets using matrix morsifications and isotropy groups of Dynkin and Euclidean diagrams. Europ. J. Comb. 2015: 48; 127-142. doi:10.1016/j.ejc.2015.02.15.
• [24] Gąsiorek M, Simson D, Zając K. A Gram classification of non-negative corank-two loop-free edge-bipartite graphs. Linear Algebra Appl. 2016: to appear.
• [25] Gąsiorek M, Zając K. On algorithmic study of non-negative posets of corank at most two and their Coxeter-Dynkin types. Fund. Inform. 2015: 139; 347-367. doi: 10.3233/FI-2015-1150.
• [26] Gram JP. On Raekkeudviklinger bestemte ved Hjaelp of de mindste Kvadraters Methode, Kopenhavne, 1879.
• [27] Grzecza M, Kasjan S, Mróz A. Tree matrices and a matrix reduction algorithm of Belitskii. Fund. Inform. 2012: 117; 253–279. doi: 10.3233/FI-2012-713.
• [28] Horn RA, Sergeichuk VV. Congruences of a square matrix and its transpose. Linear Algebra Appl. 2004: 389; 347–353.
• [29] Humphreys JE. Introduction to Lie Algebras and Representation Theory. Graduate Texts in Mathematics 9. Springer-Verlag, New York Heidelberg, Berlin, 1972.
• [30] Inohara T. Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments. Applied Math. and Comp. 2002: 133; 93-104.
• [31] Kaniecki M, Kosakowska J, Malicki P, Marczak G. A horizontal mesh algorithm for a class of edge-bipartite graphs and their matrix morsifications. Fund. Inform. 2015: 139; 136; 345-379.
• [32] Kasjan S, Mróz A. Experiences in symbolic computations for matrix problems. In: Proceedings of 14th International Symposium on Symbolic and Numeric Algorithms for Scientic Computing (SYNASC 2012). Timisoara, IEEE Computer Society, 2012, pp. 39-44.
• [33] Kasjan S, Simson D. Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, I. Mesh root systems. Fund. Inform. 2015: 139; 153-184. doi: 10.3233/FI-2015-1230.
• [34] Kasjan S, Simson D. Mesh algorithms for Coxeter spectral classification of Cox-regular edge-bipartite graphs with loops, II. Application to Coxeter spectral analysis. Fund. Inform. 2015: 139; 185-209, doi: 10.3233/FI-2015-1231.
• [35] Kasjan S, Simson D. Algorithms for isotropy groups of Cox-regular edge-bipartite graphs. Fund. Inform. 2015: 139; 249-275. doi: 10.3233/FI-2015-1234.
• [36] Kosakowska J. Inflation algorithms for positive and principal edge-bipartite graphs and unit quadratic forms. Fund. Inform. 2012: 119; 149-162. doi: 10.3233/FI-2012-731.
• [37] Kunegis J. Spectral analysis of signed graphs for clustering, prediction, and visualization. In: SDM SIAM 2010, pp. 559-570.
• [38] Marczak G, Polak A, Simson D. P-critical integral quadratic forms and positive unit forms. An algorithmic approach. Linear Algebra Appl. 2010: 433; 1873–1888; doi: 10.1016/j.laa. 2010.06.052.
• [39] Marczak G, Simson D, Zając K. On computing non-negative loop-free edge-bipartite graphs. SYNASC13, Timisoara, IEEE Computer Society, Tokyo, 2014, pp. 68-75. doi: 10.1109/SYNASC.2013.16.
• [40] Mróz A. On the computational complexity of Bongartz0s algorithm. Fund. Inform. 2013: 123; 317–329.
• [41] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition. Fund. Inform. 2016: to appear.
• [42] Mróz A, de la Peña JA. Tubes in derived categories and cyclotomic factors of Coxeter polynomials of an algebra. J. Algebra. 2014: 420; 242-260.
• [43] Mróz A, de la Peña JA. Periodicity in bilinear lattices and the Coxeter formalism. Linear Algebra Appl. 2016: 493; 227–260. doi: 10.1016/j.laa. 2015.11.021.
• [44] Mróz A, Zwara G. Combinatorial algorithms computing degenerations of modules of finite dimension. Fund. Inform. 2014: 132; 519–532.
• [45] de la Peña JA. Algebras whose Coxeter polynomials are products of cyclotomic polynomials. Algebras and Repr. Theory. 2014: 17; 905-930. doi.10.1007/s10468-013-9424-0.
• [46] Polak A, Simson D. Algorithms computing O(n;Z)-orbits of P-critical edge-bipartite graphs and P-critical unit forms using Maple and C#. Algebra and Discrete Math. 2013: 16; 242–286.
• [47] Polak A, Simson D. Coxeter spectral classification of almost TP-critical one-peak posets using symbolic and numeric computations. Linear Algebra Appl. 2014: 445; 223–255. doi: 10.1016/j.laa.2013.12.018.
• [48] Sato M. Periodic Coxeter matrices and their associated quadratic forms. Linear Algebra Appl. 2005: 406; 99–108. doi: 10.1016/j.laa. 2005.03.036.
• [49] Simson D. A reduction functor, tameness, and Tits form for a class of orders. J. Algebra. 1995: 174; 439–452.
• [50] Simson D. Prinjective modules, propartite modules, representations of bocses and lattices over orders. J. Math. Soc. Japan.1997: 49; 31–68.
• [51] Simson D. Integral bilinear forms, Coxeter transformations and Coxeter polynomials of finite posets. Linear Algebra Appl. 2010: 433; 699–717. doi: 10.1016/j.laa. 2010.03.04.
• [52] Simson D. Mesh geometries of root orbits of integral quadratic forms. J. Pure Appl. Algebra. 2011: 215: 13–34. doi: 10.1016/j.jpaa. 2010.02.029.
• [53] Simson D. Mesh algorithms for solving principal Diophantine equations, sand-glass tubes and tori of roots. Fund. Inform. 2011: 109; 425–462. doi: 10.3233/FI-2011-603.
• [54] Simson D. Algorithms determining matrix morsifications, Weyl orbits, Coxeter polynomials and mesh geometries of roots for Dynkin diagrams. Fund. Inform. 2013: 123; 447-490. doi: 10.3233/FI-2013-820.
• [55] Simson D. A framework for Coxeter spectral analysis of edge-bipartite graphs, their rational morsifications and mesh geometries of root orbits. Fund. Inform. 2013: 124; 309–338. doi: 10.3233/FI-2013-836.
• [56] Simson D. Toroidal algorithms for mesh geometries of root orbits of the Dynkin diagram D4. Fund. Inform. 2013: 124; 339–364. doi: 10.3233/FI-2013-837.
• [57] Simson D. A Coxeter-Gram classification of simply-laced edge-bipartite graphs. SIAM J. Discr. Math. 2013: 27; 827–854.
• [58] Simson D. Symbolic algorithms computing Gram congruences in the Coxeter spectral classification of edgebipartite graphs, II. Isotropy mini-groups. Fund. Inform. 2016: 145; 49-80. this volume. doi: 10.3233/FI-2016-1346.
• [59] Simson D, Skowroński A. 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.
• [60] Simson D, Zając K. 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. http./dx.doi.org/10.1155/2013/743734.
• [61] Zając K. Numeric algorithms for corank-two edge-bipartite graphs and their mesh geometries of roots. Fund. Inform. 2016, to appear.
• [62] Zaslavsky T. Signed graphs. Discrete Appl. Math. 1982: 4; 47–74.
• [63] Zhang Y. Eigenvalues of Coxeter transformations and the structure of the regular components of the Auslander-Reiten quiver. Comm. Algebra. 1998: 17; 2347-2362.
• [64] Zhang Y. The structure of stable components. Canad. J. Math. 1991: 43; 652–672.