COMPUTING THE STRUCTURE OF FINITE-ALGEBRAS

In this paper we address some algorithmic problems related to computations in finite-dimensional associative algebras over finite fields. Our starting point is the structure theory of finite-dimensional associative algebras. This theory determines, mostly in a nonconstructive way, the building blocks of these algebras. Our aim is to give polynomial time algorithms to find these building blocks, the radical and the simple direct summands of the radical-free part. The radical algorithm is based on a new, tractable characterisation of the radical. The algorithm for decomposition of semisimple algebras into simple ideals involves (and generalises) factoring polynomials over the ground field. Next, we study the problem of finding zero divisors in finite algebras. We show that thisproblem is in the same complexity class as the problem of factoring polynomials over finte fields. Applications include a polynomial time Las Vegas method to find a common invariant subspace of a set of linear transformations as well as an explicit isomorphism between a given finite simple algebra and a full matrix algebra over a finite field. © 1990, Academic Press Limited. All rights reserved.