  In this paper we present a deterministic polynomial time algorithm for
testing if a symbolic matrix in non-commuting variables over $\mathbb{Q}$ is
invertible or not. The analogous question for commuting variables is the
celebrated polynomial identity testing (PIT) for symbolic determinants. In
contrast to the commutative case, which has an efficient probabilistic
algorithm, the best previous algorithm for the non-commutative setting required
exponential time (whether or not randomization is allowed). The algorithm
efficiently solves the "word problem" for the free skew field, and the identity
testing problem for arithmetic formulae with division over non-commuting
variables, two problems which had only exponential-time algorithms prior to
this work.
  The main contribution of this paper is a complexity analysis of an existing
algorithm due to Gurvits, who proved it was polynomial time for certain classes
of inputs. We prove it always runs in polynomial time. The main component of
our analysis is a simple (given the necessary known tools) lower bound on
central notion of capacity of operators (introduced by Gurvits). We extend the
algorithm to actually approximate capacity to any accuracy in polynomial time,
and use this analysis to give quantitative bounds on the continuity of capacity
(the latter is used in a subsequent paper on Brascamp-Lieb inequalities).
  Symbolic matrices in non-commuting variables, and the related structural and
algorithmic questions, have a remarkable number of diverse origins and
motivations. They arise independently in (commutative) invariant theory and
representation theory, linear algebra, optimization, linear system theory,
quantum information theory, approximation of the permanent and naturally in
non-commutative algebra. We provide a detailed account of some of these sources
and their interconnections.
