Algorytmy numeryczne w spektralnej analizie Coxetera bigrafów

Celem rozprawy jest rozwiązanie klasy problemów algorytmiczno-obliczeniowych (sformułowanych w pracach [48]–[50], [69]–[76]) występujących w spektralnej klasyfikacji Coxetera-Grama spójnych dodatnich prostych grafów oznakowanych, a także spójnych dodatnich krawędziowo-dwudzielnych grafów ∆ bez pętli (w skrócie bigrafów) zdefiniowanych w [70]. Rozdziały 1 oraz 2 poświęcone są krótkiemu wprowadzeniu do spektralnej analizy Coxetera grafów oznakowych oraz klasy nieujemnych grafów krawędziowo-dwudzielnych ∆ bez pętli a także podaniu motywacji do badań nad problemami spektralnej klasyfikacji Coxetera skończonych bigrafów. Przypomnijmy, że z dowolnym bigrafem ∆ bez pętli o skończonym zbiorze ponumerowanych n >= 1 wierzchołków, stowarzysza się jego zespolone spektrum Coxetera specc_∆ ⊆ C, tj. spektrum Z-odwracalnej macierzy Coxetera Cox_∆ := −Gˇ_∆ · Gˇ_∆^−tr ∈ M_n(Z), gdzie Gˇ_∆ ∈ M_n(Z) jest niesymetryczną macierzą Grama bigrafu ∆. Jednym z celów rozprawy jest podanie klasyfikacji dodatnich grafów krawędziowo-dwudzielnych z dokładnością do silnej Z-kongruencji Grama ∆ ≈z ∆, zdefiniowanej w pracy [70] następująco: “∆ ≈z ∆' ⇐⇒ Gˇ_∆' = B^tr · Gˇ_∆ · B, dla pewnej macierzy B ∈ Gl(n, Z)”. Innym z celów rozprawy jest zbudowanie algorytmów symbolicznych i numerycznych obliczających macierz B ∈ Gl(n, Z) definiującą Z-kongruencję Grama ∆ ≈z ∆', dla dowolnej pary bigrafów spełniających relację ∆ ≈z ∆' (lub takich, dla których zachodzi równość specc_∆ = specc_∆' ich spektrów Coxetera). W rozdziale 3 przedstawiamy narzędzia techniczne i algorytmiczne pozwalające zredukować rozważane problemy spektralnej klasyfikacji Coxetera-Grama do badania analogicznych problemów dla pewnego skończonego zbioru Mor_D ⊆ M_n(Z) wszystkich morsyfikacji macierzowych A (zdefiniowanego w pracach [69]–[71]) dla ustalonego jednorodnego diagramu Dynkina D ∈ {A_n , n >= 1, D_n , n >= 4, E6 , E7, E8}. Zbiór Mor_D jest niezmienniczym podzbiorem zbioru macierzy M_n(Z) względem działania ∗: M_n(Z) × Gl(n, Z)_D → M_n(Z), (A, B) → A ∗ B := B^tr ·A·B ograniczonego do skończonej podgrupy Gl(n, Z)_D grupy liniowej Gl(n, Z), zwanej grupą izotropii diagramu D (zobacz [70]). Jednym z ważniejszych wyników tego rozdziału są autorskie algorytmy obliczające zbiór Mor_D, grupę izotropii Gl(n, Z)_D oraz zbiór Gl(n, Z)_D-orbit w Mor_D, dla dowolnego jednorodnego diagramu Dynkina D, a także wyniki tych obliczeń. Jednym z głównych osiągnięć tej rozprawy jest przedstawiona w rozdziale 4 pełna klasyfikacja spójnych dodatnich grafów krawędziowo-dwudzielnych ∆ o co najwyżej 9-ciu wierzchołkach, z dokładnością do silnej Z-kongruencji Grama ∆ ≈z ∆'. Udowodnione twierdzenie klasyfikacyjne orzeka, że każdy taki bigraf jest Z-kongruentny z jednym z 26 bigrafów klasyfikujących. Rozdział 5 zawiera konstrukcje nieskończonych serii morsyfikacji A ∈ Mor_A_n diagramu Dynkina A_n, o parami różnych spektrach Coxetera, dla n >= 1. W rozdziałach 6 oraz 7 przedstawiamy ideę redukcji badanych problemów klasyfikacyjnych do konstrukcji klasy symbolicznych algorytmów toroidalno-oczkowych konstruujących macierze B definiujące silną Z-kongruencję Grama ∆ ≈z ∆'. W szczególności, dla klasy nieskończonych serii morsyfikacji diagramu Dynkina D = A_n budujemy algorytmy symboliczne konstruujące, dla dowolnej pary morsyfikacji A, A' ∈ Mor_D leżących w tej samej Gl(n, Z)_D-orbicie, pewną macierz B ∈ M_n(Z) taką, że A' = A ∗ B^tr. Główne wyniki rozprawy zostały opublikowane w artykułach [8], [9], [24], [27]–[31].

The aim of this thesis is to solve class of the algorithmic and computing problems (formulated in [48]–[50], [69]–[76]) for Coxeter-Gram spectral classification of the connected positive simple signed graphs and connected positive loop-free edge-bipartite graphs ∆ (bigraphs, in short) defined in [70]. The first and the second chapter are devoted to short introduction to the Coxeter spectral analysis of the signed graphs and the class of the loop-free non-negative edge-bipartite graphs ∆. Moreover, we present a motivation for the study of Coxeter spectral analysis problems of the finite edge-bipartite graphs. Recall that, with any loop-free bigraph ∆ with n >= 1 vertices numbered by the integers, we associate the (complex) Coxetera spectrum specc_∆ ⊆ C, i.e., the spectrum of the Z-invertible Coxeter matrix Cox_∆ := −Gˇ_∆ · Gˇ_∆^−tr ∈ M_n(Z), where Gˇ_∆ ∈ M_n(Z) is the non-symmetric Gram matrix of ∆. One of the aims of this thesis is to classify positive edge-bipartite graphs, up to the Gram Z-bilinear congruence defined in [70] as follows “∆ ≈z ∆' ⇐⇒ Gˇ_∆' = B^tr · Gˇ_∆ · B, for some B ∈ Gl(n, Z)”. Another issue of this thesis is to construct symbolic and numeric algorithms for computing matrix B ∈ Gl(n, Z) defining the Gram Z-bilinear congruence ∆ ≈z ∆', for any pair of edge-bipartite graphs such that ∆ ≈z ∆' (or their Coxeter spectra equality holds specc_∆ = specc_∆'). In the third chapter we present technical and algorithmic tools that allows a reduction of the Coxeter-Gram spectral classification problems to the analogue problems for some finite set Mor_D ⊆ M_n(Z) of matrix morsifications A (defined in [69]–[71]) of the fixed simply laced Dynkin diagram D ∈ {A_n , n >= 1, D_n , n >= 4, E6 , E7, E8}. Set Mor_D is invariant subset of M_n(Z) under the action ∗: M_n(Z) × Gl(n, Z)_D → M_n(Z), (A, B) → A ∗ B := B^tr ·A·B limited to isotropy group Gl(n, Z)_D of the diagram D, that is a finite subgroup of the general linear group Gl(n, Z) (see [70]). Main results of this chapter are our algorithms computing the set Mor_D, isotropy group Gl(n, Z)_D and the set of Gl(n, Z)_D-orbits in Mor_D, for any simply laced Dynkin diagram D. We also present results of these computer calculations. One of the main results of this thesis is a complete classification of positive connected edge-bipartite graphs with at most nine vertices, up to the Gram Z-bilinear congruence ∆ ≈z ∆', presented in the fourth chapter. It follows from our classification theorem that any of those bigraphs are Z-congruent with one of the 26 classifying bigraphs presented in chapter four. The fifth chapter contains constructions of several infinite series of matrix morsification A ∈ Mor_A_n for the diagram A_n, with pairwise different Coxeter spectra, for n >= 1. In the six and the seventh chapter we present an idea of a reduction from studied classification problems to the build class of symbolic toroidal mesh algorithms for computing matrix B ∈ Gl(n, Z)_D defining the Gram Z-bilinear congruence ∆ ≈z ∆'. In particular, for a class of the infinite series of matrix morsification for Dynkin diagram D = A_n we build symbolic algorithms constructing some matrix B ∈ M_n(Z) such that A' = A ∗ B^tr, for any pair of morsifications A, A' ∈ Mor_D, that lie in the same Gl(n, Z)_D-orbit. The main results of this thesis have been published in the articles [8], [9], [24], [27]–[31].