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

Abstract

In this two parts article with the same title we continue the Coxeter spectral study of the category 𝒰ℬigr _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 Δ ∈ 𝒰ℬigr_{n + r} of corank r ≥ 0, up to a pair of the Gram ℤ-congruences ∼_ℤ and ≈_ℤ, by means of the non-symmetric Gram matrix ${Ğ}_{\Delta }\in {\mathbb{M}}_{n+r}\left(\mathbb{Z}\right)$ of Δ, the symmetric Gram matrix $G_{\Delta }:=\frac{1}{2}\left[{Ğ}_{\Delta }+{Ğ}_{\Delta }^{tr}\right]\in {\mathbb{M}}_{n+r}\left(\mathbb{Z}\right)$, the Coxeter matrix ${\text{Cox}}_{\Delta }:=-{Ğ}_{\Delta }\cdot {Ğ}_{\Delta }^{-tr}\in {\mathbb{M}}_{n+r}\left(\mathbb{Z}\right)$, its spectrum ${\text{specc}}_{\Delta }\subset ℂ$ , called the Coxeter spectrum of Δ, and the Dynkin type ${\text{Dyn}}_{\Delta }\in \left\{{\mathbb{A}}_n,{\mathbb{D}}_n,{\mathbb{E}}_6,{\mathbb{E}}_7,{\mathbb{E}}_8\right\}$ associated in Part 1 of this paper. One of the aims in the study of the category 𝒰ℬigr_{n + r} is to classify the equivalence classes of the non-negative edge-bipartite graphs in 𝒰ℬigr_{n + r} with respect to each of the Gram congruences ∼_ℤ and ≈_ℤ. In particular, the Coxeter spectral analysis question, when the congruence $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\prime }$ holds (hence also $\Delta {~}_{\mathbb{Z}}{\Delta }^{\prime }$ holds), for a pair of connected non-negative graphs $\Delta ,{\Delta }^{\prime }\in uBig{r}_{n+r}$ such that ${\text{specc}}_{\Delta }={\text{specc}}_{{\Delta }^{\prime }}$ and ${\text{Dyn}}_{\Delta }={\text{Dyn}}_{{\Delta }^{\prime }}$ , 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 $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\prime }$ , that is, a ℤ-invertible matrix $\text{B}\in {\mathbb{M}}_{n+r}\left(\mathbb{Z}\right)$ such that ${Ğ}_{{\Delta }^{\prime }}=B^{tr}\cdot {Ğ}_{\Delta }\cdot B$ . We obtain such a description for a class of non-negative connected edge-bipartite graphs $\Delta \in uBig{r}_{n+r}$ of corank r = 0 and r = 1. In particular, we construct symbolic algorithms for the calculation of the isotropy mini-group $Ğl{\left(n+r,\mathbb{Z}\right)}_{\Delta }:=\left\{B\in {\mathbb{M}}_{n+r}\left(\mathbb{Z}\right);\det B=\pm 1\text{and}{\text{B}}^{\text{tr}}\cdot {Ğ}_{\Delta }\cdot B={Ğ}_{\Delta }\right\}$ , for a class of edge-bipartite graphs $\Delta \in uBig{r}_{n+r}$ . Using the algorithms, we calculate the isotropy mini-group $Ğl{\left(n,\mathbb{Z}\right)}_D$ and $Ğl{\left(n+1,\mathbb{Z}\right)}_{\tilde{D}}$, where D is any of the Dynkin bigraphs ${\mathbb{A}}_n,{ℬ}_n,{𝒞}_n,{\mathbb{D}}_n,{\mathbb{E}}_6,{\mathbb{E}}_7,{\mathbb{E}}_8,{ℱ}_4,{𝒢}_2$ and $\tilde{D}$ is any of the Euclidean graphs ${\tilde{\mathbb{A}}}_n,{\tilde{\mathbb{D}}}_n,{\tilde{\mathbb{E}}}_6,{\tilde{\mathbb{E}}}_7,{\tilde{\mathbb{E}}}_8$.