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=B{B}^{𝖳}$, 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 $x{x}^{𝖳}$, formées à partir de vecteurs positifs $x$.

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

Notations

Soit ${𝒮}^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 {𝒮}^n\times {𝒮}^n\mapsto ⟨A,B⟩:=\mathrm{tr}AB=\sum _{\genfrac{}{}{0ex}{}{i\in [[1,n]]}{j\in [[1,n]]}}{A}_{ij}{B}_{ij},$

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

${𝒮}_{+}^n:=\{A\in {𝒮}^n:x^{𝖳}Ax⩾0\text{pour tout}x\in {ℝ}^n\}$

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

${𝒞}^n:=\{A\in {𝒮}^n:x^{𝖳}Ax⩾0\text{pour tout}x⩾0\}$

le cône des matrices de ${𝒮}^n$ qui sont copositives et enfin

${𝒫}^n:=\{A\in {𝒮}^n:A_{ij}⩾0\text{pour tout}(i,j)\in [[1,n]{]}^2\}$

le cône des matrices de ${𝒮}^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^{𝖳}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 ${𝒞}^{n+}$ s'écrit comme une enveloppe convexe :

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

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

Reconnaissance

• Vérifier l'appartenance aux cônes ${𝒞}^n$ et ${𝒞}^{n+}$ (c'est-à-dire, étant donnés $A\in {\mathbb{Q}}_s^{n\times n}$ et $K={𝒞}^n$ ou $K={𝒞}^{n+}$, décider si $A\in K$ ou si $A\notin K$) est NP-arduModèle:,, sans que l'on sache si le problème est dans NP.
• Vérifier l'appartenance faible aux cônes ${𝒞}^n$ et ${𝒞}^{n+}$ (c'est-à-dire, étant donnés $\epsilon \in {\mathbb{Q}}_{++}$, $A\in {\mathbb{Q}}_s^{n\times n}$, $K={𝒞}^n$ ou $K={𝒞}^{n+}$ et $B$ la boule unité fermée de ${ℝ}^{n\times n}$, décider si $A\in K+\epsilon B$ ou si $A+\epsilon B⊈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 ${𝒮}_{+}^n$ en utilisant les deux cônes suivants :

${𝒞}_0^n:={𝒮}_{+}^n+{𝒫}^n\text{et}{𝒞}_0^{n+}:={𝒮}_{+}^n\cap {𝒫}^n.$

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

On peut montrer que ${𝒞}_0^n={𝒞}^n$ si $n\in [[1,4]]$. Mais ${𝒞}_0^n\ne {𝒞}^n$, si $n⩾5$, comme le montre la matrice de Horn

$H=\left(\begin{array}{ccccc}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 {𝒞}^5\setminus {𝒞}_0^5.$

On montre en effet que $H$ engendre un rayon extrême de ${𝒞}^5$ qui n'est pas dans ${𝒞}_0^5$.

Le cône ${𝒞}_0^n$ est aussi le premier cône d'une suite croissante de cônes approchant ${𝒞}^n$ par l'intérieurModèle:, :

${𝒞}_0^n\subset {𝒞}_1^n\subset {𝒞}_2^n\subset \cdots \subset {𝒞}^n\text{et}\bigcup _{k\in \mathbb{N}}{𝒞}_k^n={𝒞}^n,$

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

${𝒞}^{n+}\subset \cdots \subset ({𝒞}_2^n{)}^{+}\subset ({𝒞}_1^n{)}^{+}\subset ({𝒞}_0^n{)}^{+}={𝒞}_0^{n+}\text{et}\bigcap _{k\in \mathbb{N}}({𝒞}_k^n{)}^{+}={𝒞}^{n+}.$

Annexes

Articles connexes

• Matrice copositive
• Optimisation complètement positive

Bibliographie

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