Noncommutative convexity arises from linear matrix inequalities

This paper concerns polynomials in g   noncommutative variables x=(x1,…,xg)x=(x1,…,xg), inverses of such polynomials, and more generally noncommutative “rational expressions” with real coefficients which are formally symmetric and “analytic near 0.” The focus is on rational expressions r=r(x)r=r(x) which are “matrix convex” near 0; i.e., those rational expressions r   for which there is an ϵ>0ϵ>0 such that if X=(X1,…,Xg)X=(X1,…,Xg) is a g  -tuple of n×nn×n symmetric matrices satisfyingϵIn−(X12+⋯+Xg2)is positive definite and Y is also, then the symmetric matrixtr(X)+(1−t)r(Y)−r(tX+(1−t)Y)is positive semidefinite for all numbers t  , 0⩽t⩽10⩽t⩽1. This article gives a complete classification of matrix convex rational expressions (see Theorem 3.3) by representing such r in terms of a symmetric “linear pencil”Lγ(x):=Id−∑jAjxj+(0d−100−1+γ−r(0)) in the noncommuting variables xjxj, where AjAj are symmetric d×dd×d matrices. Namely, for γ   a real number, γ−rγ−r is a Schur complement of the linear pencil LγLγ. Moreover, given a matrix convex r, the set consisting of g tuples X   of n×nn×n symmetric matricesequation(0.1){X:r(X)−γIis negative definite} has component containing 0 which is the same as the “negativity set,”equation(0.2){X:Lγ(X)is negative definite} for LγLγ. Conditions like Lγ(X)Lγ(X) is negative definite are known as linear matrix inequalities (LMIs) in the engineering literature and arguably the main advance in linear systems theory in the 1990s was the introduction of LMI techniques. In this language what we have shown in (0.1) vs. (0.2) is that the set of solutions to a “convex matrix inequality” with noncommutative unknowns is the same as the set of solutions to some LMI.In many engineering systems problems convexity would have all of the advantages of LMIs. Indeed convexity guarantees that solutions are global and convexity bodes well for reliability of the numerics. Since LMIs have a structure which is seemingly much more rigid than convexity, there is the continual hope that a convexity based theory will be more far reaching than LMIs. But will it? There are two natural situations: one where the unknowns are scalars and one where the unknowns are matrices appearing in formulas which respect matrix multiplication. These latter problems mathematically yield expressions with noncommutative unknowns and they arise in engineering systems problems which are “dimensionless” in the sense that they scale “automatically with dimension” (as do most of the classics of control theory). That is the case we study here and the result stated above suggests the surprising conclusion that for dimensionless systems problems convexity offers no greater generality than LMIs. Indeed the result proves this for a class of model problems. Furthermore, we show that existing algorithms together with algorithms described here construct the LMIs above which are equivalent to the matrix inequalities based on the given matrix convex rational function r.In a very different direction we prove that a symmetric polynomial p in g   noncommutative symmetric variables has a symmetric determinantal representation, namely, there are symmetric matrices A0,…,AgA0,…,Ag in SRd×dSRd×d with A0A0 invertible such thatequation(0.3)detp(X)=det(A0−LA(X))detp(X)=det(A0−LA(X)) for each X a g  -tuple of symmetric n×nn×n matrices. Of course taking n=1n=1 implies immediately that a (commuting variables) polynomial p   on RgRg has a symmetric determinantal representation. For g=2g=2 much stronger commutative results can be obtained using tools of algebraic geometry but these do not seem to generalize to the higher-dimensional case; on the other hand, a nonsymmetric commutative determinantal representation for any g is due to Valiant (“universality of determinant” in algebraic complexity theory).Our determinantal representation theorem is a bi-product of the theory of systems realizations of noncommutative rational functions and can be read independently of much of the rest of the paper.While the notion of noncommutative rational functions is standard, the equivalence relation we use on rational expressions in our construction, based on evaluating rational expressions on matrices, is new and gives a new approach to noncommutative rational functions.