Matrice complètement positive

En mathématiques et, plus particulièrement en algèbre linéaire, une matrice réelle carrée ${\displaystyle A}$ est dite complètement positive si elle admet une factorisation de la forme ${\displaystyle A=BB^{\mathsf {T}}}$, avec ${\displaystyle B}$ positive. Il revient au même de dire qu'une matrice est complètement positive lorsqu'elle est une combinaison convexe de matrices de la forme ${\displaystyle xx^{\mathsf {T}}}$, formées à partir de vecteurs positifs ${\displaystyle x}$.

L'ensemble ${\displaystyle {\mathcal {C}}^{n+}}$ des matrices d'ordre ${\displaystyle n}$ complètement positives est un cône convexe fermé non vide de ${\displaystyle {\mathcal {S}}^{n}}$, l'ensemble des matrices symétriques d'ordre ${\displaystyle n}$. C'est le cône dual (positif) du cône ${\displaystyle {\mathcal {C}}^{n}}$ des matrices d'ordre ${\displaystyle n}$ symétriques copositives, pour le produit scalaire standard de ${\displaystyle {\mathcal {S}}^{n}}$, ce qui justifie la notation ${\displaystyle {\mathcal {C}}^{n+}}$.

Notations

Soit ${\displaystyle {\mathcal {S}}^{n}}$ l'espace vectoriel des matrices réelles symétriques d'ordre ${\displaystyle n}$, que l'on suppose muni de son produit scalaire standard

${\displaystyle (A,B)\in {\mathcal {S}}^{n}\times {\mathcal {S}}^{n}\mapsto \langle A,B\rangle$ :=\operatorname {tr} AB=\sum _{i\in [\![1,n]\!] \atop j\in [\![1,n]\!]}\,A_{ij}B_{ij},}

où ${\displaystyle \operatorname {tr} AB}$ désigne la trace du produit des matrices ${\displaystyle A}$ et ${\displaystyle B}$. On note

${\displaystyle {\mathcal {S}}_{+}^{n}:=\{A\in {\mathcal {S}}^{n}:x^{\mathsf {T}}Ax\geqslant 0~{\mbox{pour tout}}~x\in \mathbb {R} ^{n}\}}$

le cône des matrices de ${\displaystyle {\mathcal {S}}^{n}}$ qui sont semi-définies positives,

${\displaystyle {\mathcal {C}}^{n}:=\{A\in {\mathcal {S}}^{n}:x^{\mathsf {T}}Ax\geqslant 0~{\mbox{pour tout}}~x\geqslant 0\}}$

le cône des matrices de ${\displaystyle {\mathcal {S}}^{n}}$ qui sont copositives et enfin

${\displaystyle {\mathcal {P}}^{n}:=\{A\in {\mathcal {S}}^{n}:A_{ij}\geqslant 0~{\mbox{pour tout}}~(i,j)\in [\![1,n]\!]^{2}\}}$

le cône des matrices de ${\displaystyle {\mathcal {S}}^{n}}$ qui sont positives (élément par élément).

Définition

Matrice complètement positive — Une matrice réelle carrée d'ordre ${\displaystyle n}$ (un entier ${\displaystyle \geqslant 0}$) ${\displaystyle A}$ est dite complètement positive si elle admet la factorisation suivante

${\displaystyle A=BB^{\mathsf {T}},}$

dans laquelle ${\displaystyle B}$ est une matrice positive (c'est-à-dire que tous les éléments de ${\displaystyle B}$ sont positifs).

On note ${\displaystyle {\mathcal {C}}^{n+}}$ l'ensemble des matrices complètement positives.

Une matrice complètement positive ${\displaystyle A}$ est donc nécessairement symétrique et la forme quadratique ${\displaystyle x\mapsto x^{\mathsf {T}}Ax}$ associée s'écrit comme une somme de carrés de fonctions linéaires à coefficients positifs.

Propriétés

Premières propriétés

On voit facilement que ${\displaystyle {\mathcal {C}}^{n+}}$ s'écrit comme une enveloppe convexe :

${\displaystyle {\mathcal {C}}^{n+}:=\operatorname {co} \,\{xx^{\mathsf {T}}:x\in \mathbb {R} _{+}^{n}\}.}$

Le résultat suivant justifie la notation ${\displaystyle {\mathcal {C}}^{n+}}$ adoptée pour le cône des matrices complètement positives.

Cônes ${\displaystyle {\mathcal {C}}^{n}}$ et ${\displaystyle {\mathcal {C}}^{n+}}$ — Les ensembles ${\displaystyle {\mathcal {C}}^{n}}$ et ${\displaystyle {\mathcal {C}}^{n+}}$ sont deux cônes convexes fermés de ${\displaystyle {\mathcal {S}}^{n}}$, duaux l'un de l'autre, et l'on a

${\displaystyle {\mathcal {C}}^{n+}\subset \left\{{\begin{array}{c}{\mathcal {S}}_{+}^{n}\\{\mathcal {P}}^{n}\end{array}}\right\}\subset {\mathcal {C}}^{n}.}$

Dans les inclusions ci-dessus, les cônes ${\displaystyle {\mathcal {S}}_{+}^{n}}$ et ${\displaystyle {\mathcal {P}}^{n}}$ jouent une espèce de rôle de pivot, car ils sont autoduaux et que l'on a ${\displaystyle ({\mathcal {C}}^{n+})^{+}={\mathcal {C}}^{n}}$ et ${\displaystyle ({\mathcal {C}}^{n})^{+}={\mathcal {C}}^{n+}}$.

Reconnaissance

• Vérifier l'appartenance aux cônes ${\displaystyle {\mathcal {C}}^{n}}$ et ${\displaystyle {\mathcal {C}}^{n+}}$ (c'est-à-dire, étant donnés ${\displaystyle A\in \mathbb {Q} _{s}^{n\times n}}$ et ${\displaystyle K={\mathcal {C}}^{n}}$ ou ${\displaystyle K={\mathcal {C}}^{n+}}$, décider si ${\displaystyle A\in K}$ ou si ${\displaystyle A\notin K}$) est NP-ardu^[1],[2], sans que l'on sache si le problème est dans NP.
• Vérifier l'appartenance faible aux cônes ${\displaystyle {\mathcal {C}}^{n}}$ et ${\displaystyle {\mathcal {C}}^{n+}}$ (c'est-à-dire, étant donnés ${\displaystyle \varepsilon \in \mathbb {Q} _{++}}$, ${\displaystyle A\in \mathbb {Q} _{s}^{n\times n}}$, ${\displaystyle K={\mathcal {C}}^{n}}$ ou ${\displaystyle K={\mathcal {C}}^{n+}}$ et ${\displaystyle B}$ la boule unité fermée de ${\displaystyle \mathbb {R} ^{n\times n}}$, décider si ${\displaystyle A\in K+\varepsilon B}$ ou si ${\displaystyle A+\varepsilon B\nsubseteq K}$) est NP-ardu^[2], sans que l'on sache si le problème est dans NP.

Propriétés géométriques

Rayon extrême

Le résultat suivant est démontré par Hall et Newman (1963^[3]).

Rayon extrême — Un rayon extrême de ${\displaystyle {\mathcal {C}}^{n+}}$ est de la forme ${\displaystyle \mathbb {R} _{+}vv^{\mathsf {T}}}$, avec ${\displaystyle v\in \mathbb {R} _{+}^{n}\setminus \{0\}}$.

Approximation

On peut resserrer l'encadrement de ${\displaystyle {\mathcal {S}}_{+}^{n}}$ en utilisant les deux cônes suivants :

${\displaystyle {\mathcal {C}}_{0}^{n}:={\mathcal {S}}_{+}^{n}+{\mathcal {P}}^{n}\qquad {\mbox{et}}\qquad {\mathcal {C}}_{0}^{n+}:={\mathcal {S}}_{+}^{n}\cap {\mathcal {P}}^{n}.}$

Le « ${\displaystyle +}$ » en exposant dans ${\displaystyle {\mathcal {C}}^{n+}}$, qui indique la prise du dual, est justifié par la proposition ci-dessous. On peut aussi voir ${\displaystyle {\mathcal {C}}_{0}^{n}}$ et ${\displaystyle {\mathcal {C}}_{0}^{n+}}$ comme des approximations de ${\displaystyle {\mathcal {C}}^{n}}$ et ${\displaystyle {\mathcal {C}}^{n+}}$, respectivement.

Cônes ${\displaystyle {\mathcal {C}}_{0}^{n}}$ et ${\displaystyle {\mathcal {C}}_{0}^{n+}}$ — Les ensembles ${\displaystyle {\mathcal {C}}_{0}^{n}}$ et ${\displaystyle {\mathcal {C}}_{0}^{n+}}$ sont deux cônes convexes fermés, duaux l'un de l'autre, et l'on a

${\displaystyle {\mathcal {C}}^{n+}\subset {\mathcal {C}}_{0}^{n+}\subset \left\{{\begin{array}{c}{\mathcal {S}}_{+}^{n}\\{\mathcal {P}}^{n}\end{array}}\right\}\subset {\mathcal {C}}_{0}^{n}\subset {\mathcal {C}}^{n}.}$

On peut montrer que ${\displaystyle {\mathcal {C}}_{0}^{n}={\mathcal {C}}^{n}}$ si ${\displaystyle n\in [\![1,4]\!]}$^[4]. Mais ${\displaystyle {\mathcal {C}}_{0}^{n}\neq {\mathcal {C}}^{n}}$, si ${\displaystyle n\geqslant 5}$, comme le montre la matrice de Horn^[5]

${\displaystyle H=\left(\!\!{\begin{array}{rrrrr}1&-1&1&1&-1\\-1&1&-1&1&1\\1&-1&1&-1&1\\1&1&-1&1&-1\\-1&1&1&-1&1\end{array}}\!\!\right)\in {\mathcal {C}}^{5}\setminus {\mathcal {C}}_{0}^{5}.}$

On montre en effet que ${\displaystyle H}$ engendre un rayon extrême de ${\displaystyle {\mathcal {C}}^{5}}$ qui n'est pas dans ${\displaystyle {\mathcal {C}}_{0}^{5}}$.

Le cône ${\displaystyle {\mathcal {C}}_{0}^{n}}$ est aussi le premier cône d'une suite croissante de cônes approchant ${\displaystyle {\mathcal {C}}^{n}}$ par l'intérieur^[6],[7] :

${\displaystyle {\mathcal {C}}_{0}^{n}\subset {\mathcal {C}}_{1}^{n}\subset {\mathcal {C}}_{2}^{n}\subset \cdots \subset {\mathcal {C}}^{n}\qquad {\mbox{et}}\qquad \bigcup _{k\in \mathbb {N} }{\mathcal {C}}_{k}^{n}={\mathcal {C}}^{n},}$

tandis que les cônes duaux approchent ${\displaystyle {\mathcal {C}}^{n+}}$ par l'extérieur :

${\displaystyle {\mathcal {C}}^{n+}\subset \cdots \subset ({\mathcal {C}}_{2}^{n})^{+}\subset ({\mathcal {C}}_{1}^{n})^{+}\subset ({\mathcal {C}}_{0}^{n})^{+}={\mathcal {C}}_{0}^{n+}\qquad {\mbox{et}}\qquad \bigcap _{k\in \mathbb {N} }({\mathcal {C}}_{k}^{n})^{+}={\mathcal {C}}^{n+}.}$