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

Article type: Research Article

Authors: Simson, Daniel^{1; *}

Affiliations: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland. simson@mat.umk.pl

Correspondence: [*] Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland.

Note: [1] Supported by Polish Research Grant NCN 2011/03/B/ST1/00824.

Abstract: In this two parts article with the same title we continue the Coxeter spectral study of the category 𝒰ℬigrm 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 Δ ∈ 𝒰ℬigrn + r of corank r ≥ 0, up to a pair of the Gram ℤ-congruences ∼ℤ and ≈ℤ, by means of the non-symmetric Gram matrix ĞΔ∈Mn+r(ℤ) of Δ, the symmetric Gram matrix GΔ:=12[ĞΔ+ĞΔtr]∈Mn+r(ℤ), the Coxeter matrix CoxΔ:=−ĞΔ⋅ĞΔ-tr∈Mn+r(ℤ), its spectrum speccΔ⊂ℂ , called the Coxeter spectrum of Δ, and the Dynkin type DynΔ∈{An,Dn,E6,E7,E8} associated in Part 1 of this paper. One of the aims in the study of the category 𝒰ℬigrn + r is to classify the equivalence classes of the non-negative edge-bipartite graphs in 𝒰ℬigrn + r with respect to each of the Gram congruences ∼ℤ and ≈ℤ. In particular, the Coxeter spectral analysis question, when the congruence Δ≈ℤΔ′ holds (hence also Δ~ℤΔ′ holds), for a pair of connected non-negative graphs Δ,Δ′∈uBigrn+r such 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 ℤ-congruence Δ≈ℤΔ′ , that is, a ℤ-invertible matrix B∈Mn+r(ℤ) such that ĞΔ′=Btr⋅ĞΔ⋅B . We obtain such a description for a class of non-negative connected edge-bipartite graphs Δ∈uBigrn+r of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group Ğl(n+r,ℤ)Δ:={B∈Mn+r(ℤ); det B=±1 and Btr⋅ĞΔ⋅B=ĞΔ} , for a class of edge-bipartite graphs Δ∈uBigrn+r . Using the algorithms, we calculate the isotropy mini-group Ğl(n,ℤ)D and Ğl(n+1,ℤ)D˜, where D is any of the Dynkin bigraphs An,ℬn,𝒞n,Dn,E6,E7,E8,ℱ4,𝒢2 and D˜ is any of the Euclidean graphs A˜n,D˜n,E˜6,E˜7,E˜8.

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

DOI: 10.3233/FI-2016-1346

Journal: Fundamenta Informaticae, vol. 145, no. 1, pp. 49-80, 2016