Matrix Inequalities: A Symbolic Procedure to Determine Convexity Automatically

This paper presents a theory of noncommutative functions which results in an algorithm for determining where they are "matrix convex". Of independent interest is a theory of noncommutative quadratic functions and the resulting algorithm which calculates the region where they are "matrix positive". This is accomplished via a theorem (a type of Positivstellensatz) on writing noncommutative quadratic functions with noncommutative rational coefficients as a weighted sum of squares. Furthermore the paper gives an LDU algorithm for matrices with noncommutative entries and conditions guaranteeing that the decomposition is successful.The motivation for the paper comes from systems engineering. Inequalities, involving polynomials in matrices and their inverses, and associated optimization problems have become very important in engineering. When these polynomials are "matrix convex" interior point methods apply directly. A difficulty is that often an engineering problem presents a matrix polynomial whose convexity takes considerable skill, time, and luck to determine. Typically this is done by looking at a formula and recognizing "complicated patterns involving Schur complements"; a tricky hit or miss procedure. Certainly computer assistance in determining convexity would be valuable. This paper, in addition to theory, describes a symbolic algorithm and software which represent a beginning along these lines.The algorithms described here have been implemented under Mathematica and the noncommutative algebra package NCAlgebra. Examples presented in this article illustrate its use.