Matrice complètement positive

En mathématiques et, plus particulièrement en algèbre linéaire, une matrice réelle carrée $A$ est dite complètement positive si elle admet une factorisation de la forme $A=BB^{\mathsf {T}}$ , avec $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 $xx^{\mathsf {T}}$ , formées à partir de vecteurs positifs $x$ .

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

Notations

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

(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ù $\operatorname {tr} AB$ désigne la trace du produit des matrices $A$ et $B$ . On note

{\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 ${\mathcal {S}}^{n}$ qui sont semi-définies positives,

{\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 ${\mathcal {S}}^{n}$ qui sont copositives et enfin

{\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 ${\mathcal {S}}^{n}$ qui sont positives (élément par élément).

Définition

Une matrice complètement positive $A$ est donc nécessairement symétrique et la forme quadratique $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 ${\mathcal {C}}^{n }$ s'écrit comme une enveloppe convexe :

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

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

Reconnaissance

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

Approximation

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

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

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

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 $H$ engendre un rayon extrême de ${\mathcal {C}}^{5}$ qui n'est pas dans ${\mathcal {C}}_{0}^{5}$ .

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

{\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 ${\mathcal {C}}^{n }$ par l'extérieur :

{\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 }.

Annexes

Notes

Bibliographie

(en) A. Berman, N. Shaked-Monderer (2003). Completely Positive Matrices. World Scientific, River Edge, NJ, USA.
(en) M. Hall, M. Newman (1963). Copositive and completely positive quadratic forms. Proceedings Cambridge Philos. Soc., 59, 329–339.