Polynomial SOS

Examples

• Consider ${\displaystyle m=2}$ and the form ${\displaystyle h(x)=x_{1}^{4}-x_{1}^{2}x_{2}^{2}+x_{2}^{4}}$ of degree 4 in two variables. We have $${\displaystyle x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{pmatrix}}\!,~H+L(\alpha )={\begin{pmatrix}1&0&-\alpha _{1}\\0&-1+2\alpha _{1}&0\\-\alpha _{1}&0&1\end{pmatrix}}\!.}$$ Since there exists α such that ${\displaystyle H+L(\alpha )\geq 0}$, namely ${\displaystyle \alpha =1}$, it follows that h(x) is SOS.
• Consider ${\displaystyle m=2}$ and the form ${\displaystyle h(x)=2x_{1}^{4}-5x_{1}^{3}x_{2}/2+x_{1}^{2}x_{2}x_{3}-2x_{1}x_{3}^{3}+5x_{2}^{4}+x_{3}^{4}}$ of degree 4 in three variables. We have $${\displaystyle x^{\{m\}}={\begin{pmatrix}x_{1}^{2}\\x_{1}x_{2}\\x_{1}x_{3}\\x_{2}^{2}\\x_{2}x_{3}\\x_{3}^{2}\end{pmatrix}},~H+L(\alpha )={\begin{pmatrix}2&-5/4&0&-\alpha _{1}&-\alpha _{2}&-\alpha _{3}\\-5/4&2\alpha _{1}&1/2+\alpha _{2}&0&-\alpha _{4}&-\alpha _{5}\\0&1/2+\alpha _{2}&2\alpha _{3}&\alpha _{4}&\alpha _{5}&-1\\-\alpha _{1}&0&\alpha _{4}&5&0&-\alpha _{6}\\-\alpha _{2}&-\alpha _{4}&\alpha _{5}&0&2\alpha _{6}&0\\-\alpha _{3}&-\alpha _{5}&-1&-\alpha _{6}&0&1\end{pmatrix}}.}$$ Since ${\displaystyle H+L(\alpha )\geq 0}$ for ${\displaystyle \alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)}$, it follows that h(x) is SOS.

Matrix SOS

A matrix form F(x) (i.e., a matrix whose entries are forms) of dimension r and degree 2m in the real n-dimensional vector x is SOS if and only if there exist matrix forms ${\displaystyle G_{1}(x),\ldots ,G_{k}(x)}$ of degree m such that $${\displaystyle F(x)=\sum _{i=1}^{k}G_{i}(x)^{T}G_{i}(x).}$$

Noncommutative polynomial SOS

Consider the free algebra R⟨X⟩ generated by the n noncommuting letters X = (X₁, ..., X_n) and equipped with the involution ^T, such that ^T fixes R and X₁, ..., X_n and reverses words formed by X₁, ..., X_n. We consider Hermitian noncommutative polynomials f, which are the noncommutative polynomials of the form f = f^T. When evaluating a Hermitian noncommutative polynomial f on any n-tuple of real matrices of any size r × r produces in a positive semi-definite matrix, f is said to be matrix-positive.

A noncommutative polynomial is SOS if there exists noncommutative polynomials ${\displaystyle h_{1},\ldots ,h_{k}}$ such that $${\displaystyle f(X)=\sum _{i=1}^{k}h_{i}(X)^{T}h_{i}(X).}$$

Surprisingly, in the noncommutative scenario a noncommutative polynomial is SOS if and only if it is matrix-positive. Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.

Polynomial HSOS

A complex polynomial ${\displaystyle p(z_{1},\dots ,z_{n})}$ in variables ${\displaystyle z_{1},\dots ,z_{n}}$ and their conjugates ${\displaystyle z_{1}^{*},\dots ,z_{n}^{*}}$ is Hermitian if it takes on only real values, or equivalently if each term has an equal number of conjugated and un-conjugated variables. It is a hermitian sum-of-squares (HSOS) if there are complex polynomials ${\displaystyle g_{1},\dots ,g_{k}}$, in only the un-conjugated variables ${\displaystyle z_{1},\dots ,z_{n}}$, such that $${\displaystyle p(z)=\sum _{i=1}^{k}g_{i}^{*}(z)g_{i}(z).}$$ A Hermitian square matricial representation of ${\displaystyle p}$ is a matrix ${\displaystyle M}$ such that ${\displaystyle p(z)=(z^{\{m\}})^{*}Mz^{\{m\}}}$, where ${\displaystyle (z^{\{m\}})^{*}}$ is the Hermitian transpose of the vector ${\displaystyle z^{\{m\}}}$. As first observed by Putinar, there is a choice of the matrix ${\displaystyle M}$ having certain symmetry properties, which is in fact unique and can be written explicitly. Thus testing if a Hermitian polynomial is HSOS of degree ${\displaystyle m}$ can be done by testing if a single, fixed matrix is positive-semidefinite.