Polynôme somme de carrés

Modèle:3autres En mathématiques, un polynôme homogène à coefficients réels $h(x)$ de degré $2m$, en les Modèle:Mvar variables $x=(x_1,\dots ,x_n)$ est somme de carrés (en anglais SOS pour sum of squares) si et seulement s'il existe des polynômes homogènes $g_1(x),\dots ,g_k(x)$ de degré $m$ tels que

$h(x)=\sum _{i=1}^k{g}_i(x{)}^2.$

Exemple et propriétés

Le polynôme homogène de degré 4 en deux variables $h(x)=x_1^4-x_1^2{x}_2^2+x_2^4$ s'écrit sous la forme

$h(x)=x_1^4-x_1^2{x}_2^2+x_2^4=(x_1^2-x_2^2{)}^2+(x_1{x}_2{)}^2.$

Il est donc la somme de deux carrés.

Tout polynôme homogène qui est somme de carrés est un polynôme positif (un polynôme qui ne prend que des valeurs positives) ; la réciproque n'est pas vraie et Hilbert a prouvé que, pour $n=2,m=1$ ou pour $n=3,m=2$, un polynôme homogène est somme de carrés si et seulement s'il est positif. Il en est de même pour le problème analogique des polynômes homogènes symétriques positifs Modèle:,.

Des conditions suffisantes pour qu'un polynôme homogène soit somme de carrés ont été donnéesModèle:,. De plus, un polynôme homogène réel positif peut être approchée arbitrairement près (pour la norme $l_1$ de son vecteur de coefficients) par une suite de polynômes homogènes qui sont sommes de carrés.

Représentation matricielle carrée (SMR)

On peut voir le problème d'établir qu'un polynôme homogène $h(x)$ est somme de carrés comme la résolution d'un problème d'optimisation convexe. En effet, $h(x)$ peut s'écrire sous la forme

$h(x)=x^{\{m{\}}^{\prime }}(H+L(\alpha ))x^{\{m\}}$

où $x^{\{m\}}$ est un vecteur contenant une base des polynômes homogènes de degré $m$ en $x$ (comme par exemple les monômes de degré degré $m$ en $x$), le symbole ′ désigne la transposée, où $H$ est la matrice symétrique vérifiant

$h(x)=x^{\left\{m\right\}}H{x}^{\{m\}}$

et où $L(\alpha )$ est une paramétrisation linéaire de l'espace linéaire

$ℒ=\{L=L^{\prime }:x^{\{m{\}}^{\prime }}L{x}^{\{m\}}=0\}.$

La dimension du vecteur $x^{\{m\}}$ est égale à

$\sigma (n,m)=(\genfrac{}{}{0ex}{}{n+m-1}{m}),$

et la dimension du vecteur $\alpha$ est :

$\omega (n,2m)=\frac{1}{2}\sigma (n,m)(1+\sigma (n,m))-\sigma (n,2m).$

Avec ces notation, le polynôme $h(x)$ est une somme de carrés si et seulement s'il existe un vecteur $\alpha$ tel que

$H+L(\alpha )\ge 0$,

ce qui signifie que la matrice $H+L(\alpha )$ est semi-définie positive. On se ramène ainsi à la vérification d'une inégalité matricielle linéaire qui est un problème d'optimisation convexe. L'expression

$h(x)=x^{\{m{\}}^{\prime }}(H+L(\alpha ))x^{\{m\}}$

a été introduite dans sous le nom de représentation matricielle carrée (square matrix representation abrégé en SMR) afin d'établir si un polynôme homogène est somme de carrés à travers une inégalité matricielle linéaire. Cette représentation est également connue sous le nom de matrice de Gram.

Exemples

• On considère le polynôme homogène de degré 4 en deux variables $h(x)=x_1^4-x_1^2{x}_2^2+x_2^4$ . On a

$m=2,x^{\{m\}}=\left(\begin{array}{c}{x}_1^2\\ x_1{x}_2\\ x_2^2\end{array}\right),H+L(\alpha )=\left(\begin{array}{ccc}1& 0& -{\alpha }_1\\ 0& -1+2{\alpha }_1& 0\\ -{\alpha }_1& 0& 1\end{array}\right).$

Pour la valeur $\alpha =1$ on a $H+L(\alpha )\ge 0$ ; il s'ensuit que $h(x)$ est somme de carrés.

• On considère le polynôme homogène de degré 4 en trois variables $h(x)=2x_1^4-2.5x_1^3{x}_2+x_1^2{x}_2{x}_3-2x_1{x}_3^3+5x_2^4+x_3^4$ . On a

$m=2,x^{\{m\}}=\left(\begin{array}{c}{x}_1^2\\ x_1{x}_2\\ x_1{x}_3\\ x_2^2\\ x_2{x}_3\\ x_3^2\end{array}\right),H+L(\alpha )=\left(\begin{array}{cccccc}2& -1.25& 0& -{\alpha }_1& -{\alpha }_2& -{\alpha }_3\\ -1.25& 2{\alpha }_1& 0.5+{\alpha }_2& 0& -{\alpha }_4& -{\alpha }_5\\ 0& 0.5+{\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{array}\right).$

Comme $H+L(\alpha )\ge 0$ pour $\alpha =(1.18,-0.43,0.73,1.13,-0.37,0.57)$, il s'ensuit que $h(x)$ est somme de carrés.

Somme de carrés de polynômes non commutatifs

On considère l'algèbre libre $R⟨X⟩$ engendrée par $n$ symboles non commutants $X=\{x_1,\dots ,x_n\}$, muni de l'involution ~, qui fixe $R$ et les $x_i$ et qui retourne les mots sur $X$ . Par analogie au cas commutatif, les polynômes symétriques non commutatifs sont les polynômes non commutatifs invariants par l'involution ~.

Un polynôme non commutatif est somme de carrés s'il existe des polynômes non commutatifs $h_1,\dots ,h_k$ tel que

$f(X)=\sum _{i=1}^k{h}_i(X{)}^{\sim }{h}_i(X).$

Lorsqu'une matrice réelle de dimension $r\times r$ est évaluée en un polynôme non commutatif symétrique $f$ , et qu'on obtient une matrice semi-définie positive, $f$ est dite matrice-positif. Dans le cadre non commutatif, un polynôme non commutatif est somme de carrés si et seulement s'il est matrice-positif. De plus, il existe des algorithmes pour décomposer les polynômes matrice-positifs en une somme des carrés de polynômes non commutatifs.

Voir également

• Dix-septième problème de Hilbert
• Sommes de carrés