Theory of Computing
-------------------
Title     : Non-Commutative Arithmetic Circuits with Division
Authors   : Pavel Hrubes and Avi Wigderson
Volume    : 11
Number    : 14
Pages     : 357-393
URL       : https://theoryofcomputing.org/articles/v011a014

Abstract
--------

We initiate the study of the complexity of arithmetic circuits with
division gates over non-commuting variables. Such circuits and
formulae compute _non-commutative_ rational functions, which, despite
their name, can no longer be expressed as ratios of polynomials. We
prove some lower and upper bounds, completeness and simulation
results, as follows.

If $X$ is an $n\times n$ matrix consisting of $n^2$ distinct mutually
non-commuting variables, we show that: 

 1. $X^{-1}$ can be computed by a circuit of polynomial size. 
 2. Every formula computing some entry of $X^{-1}$ must have size 
     at least $2^{\Omega(n)}$. 

We also show that matrix inverse is complete in the following sense: 

 1. Assume that a non-commutative rational function $f$ can be computed
   by a formula of size $s$. Then there exists an invertible 2s x 2s
   matrix $A$ whose entries are variables or field elements such that
   $f$ is an entry of $A^{-1}$.
 2. If $f$ is a non-commutative polynomial computed by a formula without 
   inverse gates then $A$ can be taken as an upper triangular matrix
   with field elements on the diagonal.

We show how divisions can be eliminated from non-commutative
circuits and formulae which compute polynomials, and we address the
non-commutative version of the "rational function identity testing"
problem. As it happens, the complexity of both of these procedures
depends on a single open problem in invariant theory.