Wyniki wyszukiwania - BazTech

1

Cubic Algorithm to Compute the Dynkin Type of a Positive Definite Quasi-Cartan Matrix

Pérez C., Abarca M., Rivera D.

Fundamenta Informaticae

|

2018

|

Vol. 158, nr 4

369--384

EN

Inflations algorithm is a procedure that appears implicitly in Ovsienko’s classical proof for the classification of positive definite integral quadratic forms. The best known upper asymptotic bound for its time complexity is an exponential one. In this paper we show that this bound can be tightened to O(n6) for the naive implementation. Also, we propose a new approach to show how to decide whether an admissible quasi-Cartan matrix is positive definite and compute the Dynkin type in just O(n3) operations taking an integer matrix as input.

2

Inflation Agorithm for Cox-regular Postive Edge-bipartite Graphs with Loops

Makuracki B., Simson D., Zyglarski B.

Fundamenta Informaticae

|

2017

|

Vol. 153, nr 4

367--398

EN

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix ĞΔ ∊ Mn(Z) defining Δ, its symmetric Gram matrix GΔ:=1/2[ĞΔ+ĞtrΔ]∊ Mn(1/2Z), and the Gram quadratic form qΔ : Zn → Z. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix GΔ∊ Mn(Z) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram Z-congruence Δ ~Z Δ', where Δ ~ZΔ' means that GΔ' = Btr.GΔ .B, for some B ∊ Mn(Z) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph Dn ∊ {Bn, Cn, F4, G2} with loops and a suitably chosen sequence t-• of the inflation operators of one of the types Δ'↦t-aΔ' and Δ'↦t-abΔ' such that the composite operator Δ↦t-•Δ reduces Δ to the bigraph Dn such that Δ ~Z Dn and the bigraphs Δ, Dn have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∊ Mn(Z), with det B = ±1, defining the weak Gram Z-congruence Δ ~Z Dn, that is, satisfying the equation GDn= Btr.GΔ.B.

3

Toroidal Algorithms for Mesh Geometries of Root Orbits of the Dynkin Diagram D4

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 3

339--364

EN

By applying symbolic and numerical computation and the spectral Coxeter analysis technique of matrix morsifications introduced in our previous paper [Fund. Inform. 124(2013)], we present a complete algorithmic classification of the rational morsifications and their mesh geometries of root orbits for the Dynkin diagram 4 The structure of the isotropy group Gl(4, {Z})D4 of D 4 is also studied. As a byproduct of our technique we show that, given a connected loop-free positive edge-bipartite graph Δ, with n ≥ 4 vertices (in the sense of our paper [SIAM J. Discrete Math. 27(2013)]) and the positive definite Gram unit formqΔ ; Zn→Z, any positive integer d ≥ 1 can be presented as d = qΔ(v), with v Є Zn In case n = 3, a positive integer d ≥ 1 can be presented as d = qΔ(v), with v Є Zn , if and only if d is not of the form 4a(16 · b + 14), where a and b are non-negative integers.

4

A Framework for Coxeter Spectral Analysis of Edge-bipartite Graphs, their Rational Morsifications and Mesh Geometries of Root Orbits

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 3

309--338

EN

Following the spectral Coxeter analysis of matrix morsifications for Dynkin diagrams, the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we continue our study of the category UBigrn of loop-free edge-bipartite (signed) graphs ∆, with n > 2 vertices, by means of the Coxeter number oa, the Coxeter spectrum specc∆ of ∆, that is, the spectrum of the Coxeter polynomial cox∆(t) ∈ Z[t] and the Z-bilinear Gram form b∆ : Zn x Zn →Z of ∆ [SIAM J. Discrete Math. 27(2013)]. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. We show that the Coxeter spectral classification of connected edge-bipartite graphs A in UBigrn reduces to the Coxeter spectral classification of rational matrix morsifications A ∈ MorD∆ for a simply-laced Dynkin diagram D∆ associated with ∆. Given ∆ in UBigrn, we study the isotropy subgroup Gl(n, Z)∆ of Gl(n, Z) that contains the Weyl group W∆. and acts on the set Mor∆ of rational matrix morsifications A of ∆ in such a way that the map A → (speccA, det A, c∆) is Gl(n, Z)∆-invariant. It is shown that, for n < 6, specc∆ is the spectrum of one of the Coxeter polynomials listed in Tables 3.11-3.11(a) (we determine them by computer search using symbolic and numeric computation). The question, if two connected positive edge-bipartite graphs ∆, ∆' in UBigrn, with specc∆= specc∆,, are Z-bilinear equivalent, is studied in the paper. The problem if any Z-invertible matrix A ∈ Mn(Z) is Z-congruent with its transpose Atr is also discussed.