The Paulsen problem is a basic open problem in operator theory: Given vectors @math that are @math -nearly satisfying the Parseval's condition and the equal norm condition, is it close to a set of vectors @math that exactly satisfy the Parseval's condition and the equal norm condition? Given @math , the squared distance (to the set of exact solutions) is defined as @math where the infimum is over the set of exact solutions. Previous results show that the squared distance of any @math -nearly solution is at most @math and there are @math -nearly solutions with squared distance at least @math . The fundamental open question is whether the squared distance can be independent of the number of vectors @math . We answer this question affirmatively by proving that the squared distance of any @math -nearly solution is @math . Our approach is based on a continuous version of the operator scaling algorithm and consists of two parts. First, we define a dynamical system based on operator scaling and use it to prove that the squared distance of any @math -nearly solution is @math . Then, we show that by randomly perturbing the input vectors, the dynamical system will converge faster and the squared distance of an @math -nearly solution is @math when @math is large enough and @math is small enough. To analyze the convergence of the dynamical system, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.
In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix in non-commuting variables over @math 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. The celebrated Brascamp-Lieb (BL) inequalities (and their extensions) are an important mathematical tool, unifying and generalizing numerous inequalities in analysis, convex geometry and information theory. While their structural theory is very well understood, far less is known about computing their main parameters. We give polynomial time algorithms to compute feasibility of BL-datum, the optimal BL-constant and a weak separation oracle for the BL-polytope. The same result holds for the so-called Reverse BL inequalities of Barthe. The best known algorithms for any of these tasks required at least exponential time. The algorithms are obtained by a simple efficient reduction of a given BL-datum to an instance of the Operator Scaling problem defined by Gurvits, for which the present authors have provided a polynomial time algorithm. This reduction implies algorithmic versions of many of the known structural results, and in some cases provide proofs that are different or simpler than existing ones. Of particular interest is the fact that the operator scaling algorithm is continuous in its input. Thus as a simple corollary of our reduction we obtain explicit bounds on the magnitude and continuity of the BL-constant in terms of the BL-data. To the best of our knowledge no such bounds were known, as past arguments relied on compactness. The continuity of BL-constants is important for developing non-linear BL inequalities that have recently found so many applications. Generalizing a decision problem for bipartite perfect matching, Edmonds (J. Res. Natl. Bur. Standards 718(4) (1967) 242) introduced the problem (now known as the Edmonds Problem) of deciding if a given linear subspace of M(N) contains a non-singular matrix, where M(N) stands for the linear space of complex N × N matrices. This problem led to many fundamental developments in matroid theory, etc.Classical matching theory can be defined in terms of matrices with non-negative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with non-negative entries. (Here operator refers to maps from matrices to matrices.) First, we reformulate the Edmonds Problem in terms of completely positive operators, or equivalently, in terms of bipartite density matrices. It turns out that one of the most important cases when Edmonds' problem can be solved in polynomial deterministic time, i.e. an intersection of two geometric matroids, corresponds to unentangled (aka separable) bipartite density matrices. We introduce a very general class (or promise) of linear subspaces of M(N) on which there exists a polynomial deterministic time algorithm to solve Edmonds' problem. The algorithm is a thoroughgoing generalization of algorithms in Linial, Samorodnitsky and Wigderson, Proceedings of the 30th ACM Symposium on Theory of Computing, ACM, New York, 1998; Gurvits and Yianilos, and its analysis benefits from an operator analog of permanents, so-called Quantum Permanents.Finally, we prove that the weak membership problem for the convex set of separable normalized bipartite density matrices is NP-HARD.