Cartan matrices, quasi-Cartan matrices and associated upper triangular Gram matrices control important combinatorial aspects of Lie theory and representation theory of associative algebras. We provide a graph theoretic proof of the fact that the absolute values of the coefficients of a non-negative quasi-Cartan matrix A as well as of its (minimal) symmetrizer D are bounded by 4, and that the analogous bound in case of the associated Gram matrix GˇA is 8. Moreover, we show that D (and GˇA) has at least one diagonal coefficient equal to 1. We describe some other restrictions and interrelations between the coefficients of A, D and GˇA, and the corank and other properties of A relevant in Lie theory. We apply our results to construct an algorithm by which we classify all non-negative quasi-Cartan matrices of small sizes.

We study edge-bipartite graphs (bigraphs), a class of signed graphs, by means of the inflation algorithm which relies on performing certain elementary transformations on a given bigraph Δ, or equivalently, on the associated integral quadratic form qΔ : ℤn → ℤ, preserving Gram ℤ-congruence. The idea s are inspired by classical results of Ovsienko and recent studies of Simson started in [SIAM J. Discr. Math. 27 (2013), 827-854], concerning classifications of integral quadratic and bilinear forms, and their Coxeter spectral analysis. We provide few modifications of the inflation algorithm and new estimations of its complexity for positive and principal loop-free bigraphs. We discuss in a systematic way the behavior and computational aspects of inflation techniques. As one of the consequences we obtain relatively simple proofs of several interesting properties of quadratic forms and their roots, extending known facts. On the other hand, the results are a first step of a solution of a variant of Grothendieck group recognition, a difficult combinatorial problem arising in representation theory of finite dimensional algebras and their derived categories, which we discuss in Part II of this two parts article with the same main title.

In this two parts article with the same main title we study a problem of Coxeter-Gram spectral analysis of edge-bipartite graphs (bigraphs), a class of signed graphs. We ask for a criterion deciding if a given bigraph Δ is weakly or strongly Gram-congruent with a graph. The problem is inspired by r ecent works of Simson et al. started in [SIAM J. Discr. Math. 27 (2013), 827-854], and by problems related to integral quadratic forms, bilinear lattices, representation theory of algebras, algebraic methods in graph theory and the isotropy groups of bigraphs. In this Part II we develop general combinatorial techniques, with the use of inflation algorithm discussed in Part I, morsifications and the isotropy group of a bigraph, and we provide a constructive solution of the problem for the class of all positive connected loop-free bigraphs. Moreover, we present an application of our results to Grothendieck group recognition problem: deciding if a given bilinear lattice is the Grothendieck group of some category. Our techniques are tested in a series of experiments for so-called Nakayama bigraphs, illustrating the applications in practice and certain related phenomena. The results show that a computer algebra technique and discrete mathematical computing provide important tools in solving theoretical problems of high complexity.

We present combinatorial algorithms for solving three problems that appear in the study of the degeneration order ≤ deg for the variety of finite-dimensional modules over a k-algebra Λ, where M ≤ deg N means that a module N belongs to an orbit closure $\overline{\cal{O}(M)}$ of a module M in the variety of Λ-modules. In particular, we introduce algorithmic techniques for deciding whether or not the relation M ≤ deg N holds and for determining all predecessors (resp. succesors) of a given module M with respect to ≤ deg . The order ≤ deg plays an important role in modern algebraic geometry and module theory. Applications of our technique and experimental tests for particular classes of algebras are presented. The results show that a computer algebra technique and algorithmic computer calculations provide important tools in solving theoretical mathematics problems of high computational complexity. The algorithms are implemented and published as a part of an open source GAP package called QPA.

We study the complexity of Bongartz's algorithm for determining a maximal common direct summand of a pair of modules M, N over k-algebra Λ; in particular, we estimate its pessimistic computational complexity 𝒪(rm 6 n 2 (n + m log n)), where m = dim k M ≤ n = dim k N and r is a number of common indecomposable direct summands of M and N. We improve the algorithm to another one of complexity 𝒪(rm 4 n 2 (n+m log m)) and we show that it applies to the isomorphism problem (having at least an exponential complexity in a direct approach). Moreover, we discuss a performance of both algorithms in practice and show that the “average” complexity is much lower, especially for the improved one (which becomes a part of QPA package for GAP computer algebra system).

Inspired by the bimodule matrix problem technique and various classification problems in poset representation theory, finite groups and algebras, we study the action of Belitskii algorithm on a class of square n by n block matrices M with coefficients in a field K. One of the main aims is to reduce M to its special canonical form M ∞ with respect to the conjugation by elementary transformations defined by a class of matrices chosen in a subalgebra of the full matrix algebra $\mathbb{M}_n$(K). The algorithm can be successfully applied in the study of indecomposable linear representations of finite posets by a computer search using numeric and symbolic computation. We mainly study the case when the di-graph (quiver) associated to the output matrix M ∞ of the algorithm is a disjoint union of trees. We show that exceptional representations of any finite poset are determined by tree matrices. This generalizes a theorem of C.M. Ringel proved for linear representations of di-graphs.