Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs. [Part 2], Isotropy Mini-groups

• Autorzy: Simson D.

Identyfikatory

DOI

10.3233/FI-2016-1346

• Języki publikacji: EN

Abstrakty

EN

In this two parts article with the same title 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 Ğ_Δ∈M_n+r(Z) of Δ, the symmetric Gram matrix G_Δ:=1/2[Ğ_Δ+Ğ_Δ^-tr]∈M_n+r(Z), the Coxeter matrix Cox_Δ:[formula...], its spectrum specc_Δ⊂C, called the Coxeter spectrum of Δ, and the Dynkin type Dyn_Δ∈{A_n,D_n,E₆,E₇,E₈} associated in Part 1 of this paper. 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 congruence Δ_≈ZΔ′ holds (hence also Δ_~ZΔ′ holds), for a pair of connected non-negative graphs Δ,Δ′∈uBigr_n+rsuch that specc_Δ=specc_Δ′ and Dyn_Δ=Dyn_Δ′, is studied in the paper. One of our main aims in this Part 2 of the paper is to get an algorithmic description of a matrix B defining the strong Gram Z-congruence Δ_≈ZΔ′, that is, a Z-invertible matrix B∈M_n+r(Z) such that [formula...]. We obtain such a description for a class of non-negative connected edge-bipartite graphs Δ∈uBigr_n+r of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group ..., for a class of edge-bipartite graphs Δ∈uBigr_n+r. Using the algorithms, we calculate the isotropy mini-groupGl(n,Z)_D where D is any of the Dynkin bigraphs A_n, B_n, C_n, D_n, E₆, E₇, E₈, F₄, G₂ and .D is any of the Euclidean graphs .[formula...].

Słowa kluczowe

EN

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

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 145, nr 1
• Strony: 49--80
• Opis fizyczny: Bibliogr. 62 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] Barot M, Geiss C, Zelevinsky A. Cluster algebras of finite type and positive symmetrizable matrices. J. London Math. Soc. 2006: 73; 545-564.
• [5] 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.
• [6] 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
• [7] Brualdi RA. The Mutually Beneficial Relationship of Graphs and Matrices. CBMS, No. 115, 2011.
• [8] Cvetkovi´c D, Rowlinson P, Simi´c S. An Introduction to the Theory of Graph Spectra, London Math. Soc. Student Texts 75. Cambridge Univ. Press, Cambridge-New York, 2010.
• [9] Drozd JA. Coxeter transformations and representations of partially ordered sets. Funkc. Anal. i Priložen. 1974: 8; 34–42 (in Russian).
• [10] 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.
• [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, 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.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] 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.
• [22] 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.
• [23] 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.
• [24] Horn RA, Sergeichuk VV. Congruences of a square matrix and its transpose. Linear Algebra Appl. 2004: 389; 347–353.
• [25] Humphreys JE. Introduction to Lie Algebras and Representation Theory. Graduate Texts in Mathematics 9, Springer-Verlag, New York Heidelberg, Berlin, 1972.
• [26] Inohara T. Characterization of clusterability of signed graphs in terms of newcombs balance of sentiments. Applied Math. and Comp. 2002: 133; 93-104.
• [27] Kac V. Infinite root systems, representations of graphs and invariant theory. Invent. Math. 1980: 56; 57-92.
• [28] Kac V, Peterson DH. Unitary structure in representations of infinite-dimensional groups and convexity theorem. Invent. Math. 1984: 76; 1-14.
• [29] 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.
• [30] 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.
• [31] 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.
• [32] 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.
• [33] Klemp B, Simson D. Schurian sp-representation-finite right peak PI-rings and their indecomposable socle projective modules. J. Algebra. 1990: 131; 390–468.
• [34] Kosakowska J, Simson D. Hereditary coalgebras and representations of species. J. Algebra. 2005: 293; 457–505.
• [35] 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.
• [36] 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.
• [37] 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.
• [38] Mróz A. On the computational complexity of Bongartz0s algorithm. Fund. Inform. 2013: 123; 317–329.
• [39] Mróz A. Congruences of edge-bipartite graphs with applications to Grothendieck group recognition. Fund. Inform. 2016: to appear.
• [40] 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.
• [41] 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.
• [42] Mróz A, Zwara G. Combinatorial algorithms computing degenerations of modules of finite dimension. Fund. Inform. 2014: 132; 519–532.
• [43] 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.
• [44] 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.
• [45] 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.
• [46] Sergeichuk VV. Canonical matrices for linear matrix problems. Linear Algebra Appl. 2000: 317; 53–102.
• [47] Simson D. Linear Representations of Partially Ordered Sets and Vector Space Categories. Algebra, Logic and Applications, Vol. 4, Gordon & Breach Science Publishers, 1992.
• [48] Simson D. A reduction functor, tameness, and Tits form for a class of orders. J. Algebra. 1995: 174; 439–452.
• [49] Simson D. Prinjective modules, propartite modules, representations of bocses and lattices over orders. J. Math. Soc. Japan.1997: 49; 31–68.
• [50] 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.
• [51] Simson D. Coalgebras of tame comodule type, comodule categories and tame-wild dichotomy problem. In: Trends in Representation Theory of Algebras and Related Topics. ICRA XIV, Tokyo, August 2010, (eds A. Skowroński and K. Yamagata). Series of Congress Reports, European Math. Soc. Publishing House. Zürich, 2011/12, pp. 561–660.
• [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, I. A Gram classification. Fund. Inform. 2016: 145; 19-48, this volume. doi: 10.3233/FI-2016-1345.
• [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] Zając K. Numeric algorithms for corank-two edge-bipartite graphs and their mesh geometries of roots. Fund. Inform. 2016: to appear.
• [61] Zaslavsky T. Signed graphs. Discrete Appl. Math. 1982: 4; 47–74.
• [62] Zhang Y. The structure of stable components. Canad. J. Math. 1991: 43; 652–672.