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

On Algorithmic Study of Non-negative Posets of Corank at Most Two and their Coxeter-Dynkin Types

Gąsiorek M., Zając K.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 4

347--367

EN

Here we study the connected posets I that are non-negative of corank one or two, in the sense that the symmetric Gram matrix 1/2 (CI + Citr) ∊ Mn(Q) is positive semi-definite of corank one or two, where CII ∊ Mn(Z) is the incidence matrix of I. We study such posets I by means of the Dynkin type DynI and the Coxeter polynomial coxI (t) := det(t.E - CoxI) ∊ Z[t], where CoxI := CI + CItr ∊ Mn(Z) is the Coxeter matrix of I. Among other results, we develop an algorithmic technique that allows us to compute a complete list of such posets I, with |I| ≤ 16, their Dynkin types DynI, and the Coxeter polynomials coxI(t) ∊Z[t]. We prove that, given a pair of such connected posets I and J, the incidence matrices CI and CJ are Z-congruent if and only if coxI (t) = coxJ (t) and DynI = DynJ

3

Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops. [Part] 1, Mesh Root Systems

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 2

153--184

EN

This is the first part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827- 854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study here the larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ C C, the irreducible mesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group Gl(n;Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure A ppl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of the paper is to study the Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' hold, for any pair of connected positive graphs Δ;Δ' ∊ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ0 coincide?" We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In particular, we construct in the second part of the paper numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigrn, for a fixed n ≥ 2, mesh algorithms for computing the set of all Z-invertible matrices B ∊ Gl(n;Z) definining the Z-congruence Δ ≈Z Δ', for positive graphs Δ;Δ' ∊ RBigrn, with n ≥ 2 fixed, and mesh-type algorithms for the mesh root systems Γ(RD Δ(RΔФΔ). In the first part of the paper we present an introduction to the study of Cox-regular edge-bipartite graphs Δ with dotted loops in relation with the irreducible reduced root systems and the Dynkin diagrams Bn, n ≥ 2, Cn, n ≥ 3, F4, G2. Moreover, we construct a unique ФD-mesh root system (RD,ФD) for each of the Cox-regular edge-bipartite graphs Bn, n ≥ 2, Cn, n ≥ 3, F4, calG2 of the type Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, respectively. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems.

4

Mesh Algorithms for Coxeter Spectral Classification of Cox-regular Edge-bipartite Graphs with Loops [Part] 2. Application to Coxeter Spectral Analysis

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 2

185--209

EN

This is a second part of our two part paper with the same title. Following our Coxeter spectral study in [Fund. Inform. [123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827- 854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n = 2 vertices, we study here the larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ C, the irreducible mesh root systems of Dynkin types Bn, n = 2, Cn, n = 3, F4, G2, the isotropy group Gl(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24] and [Fund. Inform. [123(2013), 447-490]. One of our aims of our two part paper is to study the Coxeter spectral analysis question: "Does the congruence Δ Z Δ' hold, for any pair of connected positive graphs Δ,Δ' ∊ RBigrn such that speccΔ = speccΔ' and the numbers of loops in ΔandΔ' coincide?"We do it by a reduction to the Coxeter spectral study of the Gl(n, Z)D-orbits in the set MorD C Mn(Z) of matrix morsifications of a Dynkin diagram D = DΔ ∊ UBigrn associated with Δ. In this second part, we construct numeric algorithms for computing the connected positive edge-bipartite graphs Δ in RBigrn, for a fixed n = 2, mesh algorithms for computing the set of all Z-invertible matrices B ∊ Gl(n, Z) definining the Z-congruenceΔ Z Δ', for positive graphsΔ,Δ' ∊ RBigrn, with n geq2 fixed, and mesh-type algorithms for the mesh root systems Γ(R·Δ,ΦΔ). We also present a classification and a structure type results for positive Cox-regular edge-bipartite graphs Δ with dotted loops.

5

Algorithms for Isotropy Groups of Cox-regular Edge-bipartite Graphs

Kasjan S., Simson D.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 3

249--275

EN

This paper can be viewed as a third part of our paper [Fund. Inform. 2015, in press]. Following our Coxeter spectral study in [Fund. Inform. 123(2013), 447-490] and [SIAM J. Discr. Math. 27(2013), 827-854] of the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, we study a larger category RBigrn of Cox-regular edge-bipartite graphs Δ (possibly with dotted loops), up to the usual Z-congruences ~Z and ≈Z. The positive graphs Δ in RBigrn, with dotted loops, are studied by means of the complex Coxeter spectrum speccΔ ⊂ C, the irreduciblemesh root systems of Dynkin types Bn, n ≥ 2, Cn, n ≥ 3, F4, G2, the isotropy group G1(n, Z)Δ (containing the Weyl group of Δ), and by applying the matrix morsification technique introduced in [J. Pure Appl. Algebra 215(2011), 13-24]. Here we present combinatorial algorithms for constructing the isotropy groups G1(n,Z)Δ. One of the aims of our three paper series is to develop computational tools for the study of the Zcongruence ~Z and the following Coxeter spectral analysis question: "Does the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphsΔ,Δ' ∈ RBigrn such that speccΔ = speccΔ' and the numbers of loops in Δ and Δ' coincide?". For this purpose, we construct in this paper a extended inflation algorithm Δ → DΔ, with DΔ ~Z Δ, that allows a reduction of the question to the Coxeter spectral study of the G1(n,Z)D-orbits in the set MorD ⊂ Mn(Z) of matrix morsifications of the associated edge-bipartite Dynkin graph D = DΔ ∈ RBigrn. We also outline a construction of a numeric algorithm for computing the isotropy group G1(n,Z)Δ of any connected positive edge-bipartite graph Δ in RBigrn. Finally, we compute the finite isotropy group G1(n,Z)D, for each of the Cox-regular edge-bipartite Dynkin graphs D.

6

A Horizontal Mesh Algorithm for a Class of Edge-bipartite Graphs and their Matrix Morsifications

Kaniecki M., Kosakowska J., Malicki P., Marczak G.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 4

345--379

EN

We construct a horizontal mesh algorithm for a study of a special type of mesh root systems of connected positive loop-free edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense of [SIAM J. Discrete Math. 27 (2013), 827–854] and [Fund. Inform. 124 (2013), 309-338]. Given such a loop-free edge-bipartite graph Δ, with the non-symmetric Gram matrix ˇGΔ ∈ Mn(Z) and the Coxeter transformation ΦA : Zn → Zn defined by a quasi-triangular matrix morsification A ∈ Mn(Z) of Δ satisfying a non-cycle condition, our combinatorial algorithm constructs a ΦA-mesh root system structure Γ(RΔ,ΦA) on the finite set of all ΦA-orbits of the irreducible root system RΔ := {v ∈ Zn; v · ˇGΔ · vtr = 1}. We apply the algorithm to a graphical construction of a ΦI - mesh root system structure Γ(RI ,ΦI ) on the finite set of ΦI -orbits of roots of any poset I with positive definite Tits quadratic form bqI : ZI → Z.

7

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.

8

Algorithms Determining Matrix Morsifications,Weyl orbits, Coxeter Polynomials and Mesh Geometries of Roots for Dynkin Diagrams

Simson D.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 4

447--490

EN

By computer algebra technique and computer computations, we solve the mesh morsification problems 1.10 and present a classification of irreducible mesh roots systems, for some of the simply-laced Dynkin diagramsΔ ∈ {An,Dn, E6, E7,E8}. The methods we use show an importance of computer algebra tools in solving difficult modern algebra problems of enough high complexity that had no solution by means of standard theoretical tools only. Inspired by results of Sato [Linear Algebra Appl. 406(2005), 99-108] and a mesh quiver description of indecomposable representations of finite-dimensional algebras and their derived categories explained in [London Math. Soc. Lecture Notes Series, Vol. 119, 1988] and [Fund. Inform. 109(2011), 425-462] (see also 5.11), given a Dynkin diagram Δ, with n vertices and the Euler quadratic form qΔ : Zn → Z, we study the set MorΔ ⊆ Mn(Z) of all morsifications of qΔ [37], i.e., the non-singular matrices A ∈ Mn(Z) such that its Coxeter matrix CoxA := −A · A−tr lies in Gl(n, Z) and qΔ(v) = v · A · vtr, for all v ∈ Zn. The matrixWeyl groupWΔ (2.13) acts on MorΔ and the determinant detA ∈ Z, the order cA ≥ 2 of CoxA (i.e. the Coxeter number), and the Coxeter polynomial coxA(t) := det(t ·E−CoxA) ∈ Z[t] are WΔ-invariant. Moreover, the finite set RqΔ = {v ∈ Zn; qΔ(v) = 1} of roots of qΔ is CoxA- invariant. The following problems are studied in the paper: (a) determine the WΔ-orbits Orb(A) of MorΔ and the set CPolΔ = {coxA(t); A ∈ MorΔ}, (b) construct a finite minimal CoxA-mesh quiver in Zn containing all CoxA-orbits of the finite set RqΔ of roots of qΔ. We prove that CPolΔ is a finite set and we construct algorithms allowing us to solve the problems for the morsifications A = [aij ] ∈ MorΔ, with |aij | ≤ 2. In this case, by computer algebra technique and computer computations, we prove that, for n ≤ 8, the number of the WΔ-orbits Orb(A) is at most 6, sΔ := |CPolΔ| ≤ 9 and, given A,A′ ∈ MorΔ and n ≤ 7, the following three conditions are equivalent: (i) A′ = Btr · A · B, for some B ∈ Gl(n, Z), (ii) coxA(t) = coxA′ (t), and (iii) cA · detA = cA′ · detA′. We also show that sΔ equals 6, 5, and 9, if Δ is the diagram E6, E7, and E8, respectively.

9

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.