Simplification of symbolic polynomials on non-commutative variables

We address the issue of simplifying symbolic polynomials on non-commutative variables. The problem is motivated by applications in optimization and various problems in systems and control. We develop theory for polynomials which are linear in a subset of the variables and develop algorithms to produce representations which have the minimal possible number of terms. The results can handle polynomial matrices as well as block-matrix variables.