Computing in Solvable Matrix Groups

The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for membership-testing, which subsumes the discrete-log problem. However, assuming that the primes in mod G mod (other than the field characteristic) are polynomially-bounded, membership-testing and many other computational problems are in polynomial time. These problems include finding stabilizers of vectors and of subspaces and finding centralizers and intersections of subgroups. An application to solvable permutation groups puts the problem of finding normalizers of subgroups into polynomial time. Some of the results carry over directly to finite matrix groups over algebraic number fields; thus, testing solvability is in polynomial time, as is testing membership and finding Sylow subgroups. >

Authors

• Eugene M. Luks

Keywords

• Polynomials
• Testing
• Galois fields
• Poles and towers
• Information science
• Matrices
• Libraries
• Solvable Group
• Quotient
• Fixed Point
• Vector Space
• Group Classification
• Series Of Derivatives
• Abelian Group
• Linear Algebra
• Finite Field
• Cyclic Group
• Finite Group
• Normal Subgroup
• Disjoint Union
• Conjugacy
• Faithful Representation
• Composite Series
• Basis Elements
• Invariant Subspace
• Unipotent