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.