Testing Membership in Unitriangular Matrix Groups.
Gábor Ivanyos · 1996
We present an algorithm that, given a subgroup G of the group of the upper triangular matrices with rational entries by a set of generators, computes generators of the lower central series of G. As an application, we show that the constructive membership problem in G can be performed in polynomial time. This draft is intended to be part of a larger project investigating the complexity of computational problems in finitely generated linear groups. 1 Introduction Polynomial time algorithms for computational problems in some classes of matrix groups over algebraic number fields have been recently obtained. The constructive membership problem in a linear group G given by a finite set of generators has been shown to be soluble in polynomialtime in the one-dimensional case by Ge [Ge1, Ge2], in the abelian case by Cai, Lipton, Zalcstein [CLZ], Babai, Beals, Cai, Ivanyos, and Luks [BBCIL], in the abelian-by-finite case by Beals [Be]. Beals [Be] also presents a polynomial time algorithm that d...