Algebras with polynomial identities and computing the determinant

Nisan (1991) proved an exponential lower bound on the size of an algebraic branching program (ABP) that computes the determinant of a matrix in the non-commutative "free algebra" setting, in which there are no non-trivial relationships between the matrix entries. By contrast, when the matrix entries commute there are polynomial size ABPs for the determinant. This paper extends Nisan's result to a much wider class of non-commutative algebras, including all non-trivial matrix algebras over any field of characteristic 0, group algebras of all non-abelian finite groups over algebraically closed fields of characteristic 0, the quaternion algebra and the Clifford algebras. As a result, we obtain more compelling evidence for the essential role played by commutativity in the efficient computation of the determinant. The key to our approach is a characterization of non-commutative algebras by means of the polynomial identities that they satisfy. Extending Nisan's lower bound framework, we find that any reduction in complexity compared to the free algebra must arise from the ability of the identities to reduce the rank of certain naturally associated matrices. Using results from the theory of algebras with polynomial identities, we are able to show that none of the identities of the above classes of algebras is able to achieve such a rank reduction.

1. Introduction

All known polynomial time algorithms for computing the determinant of a matrix appear to rely on the fact that multiplication in the underlying field (in which the matrix entries reside) is commutative. How hard is it to compute the determinant in a non-commutative setting? This question is motivated by the broader aim of understanding the computational power of commutativity [21], as well as by recent algorithmic applications of determinants over non-commutative algebras to approximating the permanent [3], [5].