on "sum of squares"

Overview

This post examines J.W. Helton’s seminal work on non-commutative (NC) Sum of Squares (SOS). It highlights the surprising contrast between commutative and non-commutative settings: while commutative positive polynomials are not always SOS, their non-commutative counterparts are SOS if and only if they are matrix-positive.

🏷️ Motivation: Hilbert’s 17th Problem

In the commutative world, the relationship between positivity and sum of squares is complex. Hilbert’s 17th problem investigated whether every non-negative polynomial is a sum of squares of rational functions.

🏷️ The Motzkin Counterexample

The Motzkin polynomial provides the definitive proof that positive polynomials are not necessarily SOS:

$$M(x,y)=x^4{y}^2+x^2{y}^4-3x^2{y}^2+1$$

The positivity follows from the AM-GM inequality, as $\frac{1}{3}(x^4{y}^2+x^2{y}^4+1)\ge \sqrt[3]{x^6{y}^6}=x^2{y}^2$, which implies $M(x,y)\ge 0$. However, $M$ cannot be SOS because the only terms allowed in a potential SOS decomposition are restricted by the absence of lower-order powers, creating a contradiction with the $-3x^2{y}^2$ coefficient.

🏷️ Helton’s Theorem: The Non-Commutative Twist

In his 2002 paper, Helton proved that non-commutative polynomials behave more elegantly regarding positivity.

🏷️ The Main Result

Let $p(x_1,\dots ,x_n)$ be a symmetric non-commutative polynomial. We say $p$ is matrix-positive if $p(X_1,\dots ,X_n)$ is a positive semi-definite matrix for all symmetric matrices $X_i$ of any size.

Helton's SOS Theorem (2002)

A non-commutative polynomial $p$ is matrix-positive if and only if it is a sum of squares:

$$p(x)=\sum _j{f}_j(x{)}^{\ast }{f}_j(x)$$

where $f_j$ are non-commutative polynomials.

🏷️ Why is NC Better?

In the non-commutative setting, the condition of being positive on all matrix sizes is significantly more restrictive than positivity on points in ${\mathbb{R}}^n$. This global positivity requirement effectively collapses the gap between positivity and the SOS representation, eliminating Motzkin-like counterexamples in the free algebra.

🏷️ Implications for Control Theory and LMIs

The power of Helton’s theorem lies in its connection to Linear Matrix Inequalities (LMIs). Problems in systems and control are naturally formulated as matrix inequalities where the variables are matrices of unknown size.

1. Convexity: Helton and McCullough showed that a non-commutative polynomial is convex if and only if its degree is at most 2. This implies that naturally occurring convex matrix problems are essentially LMIs.
2. Dimension-Free Optimization: The SOS representation provides dimension-free certificates of positivity, allowing results proven for one matrix size to generalize across all sizes.

🏷️ The GNS Construction Connection

The proof of Helton’s theorem utilizes the Gelfand-Naimark-Segal (GNS) construction. By viewing the free algebra as a $\ast$-algebra, one can build a Hilbert space where positivity corresponds to the inner product. If a polynomial lacks an SOS representation, a separating hyperplane can be constructed to violate matrix positivity.

🏷️ Notes

• Free Algebra: The setting is the free algebra $\mathbb{R}⟨x_1,\dots ,x_n⟩$ where variables do not commute.
• Rational Functions: NC rational functions are primarily used when analyzing local positivity or restricted domains.

📚 References