Symbolic Algorithms Computing Gram Congruences in the Coxeter Spectral Classification of Edge-bipartite Graphs,I. A Gram Classification

Abstract

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 ${\check{G}}_{\Delta }\in {𝕄}_{n+r}(\mathbb{Z})$ of Δ, the symmetric Gram matrix $G_{\Delta }:=\frac{1}{2}\left[{\check{G}}_{\Delta }+{\check{G}}_{\Delta }^{tr}\right]\in {𝕄}_{n+r}(\mathbb{Z})$, the Coxeter matrix ${\text{Cox}}_{\Delta }:=-{\check{G}}_{\Delta }\cdot {\check{G}}_{\Delta }^{-tr}\in {𝕄}_{n+r}(\mathbb{Z})$ and its spectrum specc_Δ ⊂ ℂ, called the Coxeter spectrum of Δ. 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 strong congruence $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\prime }$ holds (hence also $\Delta {\sim }_{\mathbb{Z}}{\Delta }^{\prime }$ holds), for a pair of connected non-negative graphs Δ, Δ′ ∈ 𝒰ℬigr_{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 ℤ-congruences $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\prime }$ and $\Delta {\sim }_{\mathbb{Z}}{\Delta }^{\prime }$ , that is, a ℤ-invertible matrix $B\in {𝕄}_{n+r}(\mathbb{Z})$ such that ${\check{G}}_{{\Delta }^{\prime }}=B^{tr}\cdot {\check{G}}_{\Delta }\cdot B$ and $G_{{\Delta }^{\prime }}=B^{tr}\cdot G_{\Delta }\cdot B$ , respectively. We show that, given a connected non-negative edge-bipartite graph Δ in 𝒰ℬigr_{n + r} of corank r ≥ 0 there exists a simply laced Dynkin diagram D, with n vertices, and a connected canonical r-vertex extension $\widehat{D}:={\widehat{D}}^{(r)}$ of D of corank r (constructed in Section 2) such that $\Delta {~}_{\mathbb{Z}}\widehat{D}$. We also show that every matrix B defining the strong Gram ℤ-congruence $\Delta {\approx }_{\mathbb{Z}}{\Delta }^{\prime }$ in 𝒰ℬigr_{n + r} has the form $B=C_{\Delta }\cdot \overline{B}\cdot C_{{\Delta }^{\prime }}^{-1}$, where $C_{\Delta },C_{{\Delta }^{\prime }}\in M_{n+r}(\mathbb{Z})$ are fixed ℤ-invertible matrices defining the weak Gram congruences $\Delta {~}_{\mathbb{Z}}\widehat{D}$ and ${\Delta }^{\prime }{~}_{\mathbb{Z}}\widehat{D}$ with an r-vertex extended graph $\widehat{D}$, respectively, and $\overline{B}\in {𝕄}_{n+r}(\mathbb{Z})$ is ℤ-invertible matrix lying in the isotropy group $\text{G1(}n+r,\mathbb{Z}{\text{)}}_{\widehat{D}}$ of $\widehat{D}$. Moreover, each of the columns $k\in {\mathbb{Z}}^{n+r}$ of B is a root of ℤ, i.e., $k\cdot {\check{G}}_{\Delta }\cdot k^{tr}=1$. 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 ${\varphi }_{\widehat{D}}:UBig{r}_{\widehat{D}}\to {\text{Mor}}_{\widehat{D}}$ that reduces (up to ≈_ℤ) the study of the set 𝒰ℬigr _{$\widehat{D}$} of all connected non-negative edge-bipartite graphs Δ in 𝒰ℬigr_{n + r} such that $\Delta {~}_{\mathbb{Z}}\widehat{D}$ to the study of $\text{G1(}n+r,\mathbb{Z}{\text{)}}_{\widehat{D}}$-orbits in the set ${\text{Mor}}_{\widehat{D}}\subseteq \text{G1(}n+r,\mathbb{Z}\text{)}$ of all matrix morsifications of the graph $\widehat{D}$.