P0-matrice

En mathématiques, une P0-matrice est une matrice carrée réelle dont les mineurs principaux sont positifs. Ces matrices interviennent dans l'étude des problèmes de complémentarité linéaire. Une notion voisine est celle des P-matrices.

Définition

On note ci-dessous $M_{I,J}$ la sous-matrice de $M$ formée de ses éléments avec indices de ligne dans $I$ et indices de colonne dans $J.$

P0-matrice — On dit qu'une matrice carrée réelle $M\in \mathbb {R} ^{n\times n}$ est une P0-matrice si l'une des propriétés équivalentes suivantes est vérifiée :

1. tous les mineurs principaux de $M$ sont positifs : pour tout $I\subset \{1,\ldots ,n\}$ non vide, $\det M_{I,I}\geqslant 0$,
2. pour tout vecteur $x\in \mathbb {R} ^{n}$ non nul, on peut trouver un indice $i$ tel que $x_{i}\neq 0$ et $x_{i}(Mx)_{i}\geqslant 0$,
3. pour tout $I\subset \{1,\ldots ,n\}$ non vide, les valeurs propres réelles de $M_{I,I}$ sont positives,
4. pour toute matrice diagonale définie positive $D$, $M+D$ est inversible.

On note $\mathbf {P_{0}}$ l'ensemble des P0-matrices d'ordre quelconque. On appelle P0-matricité la propriété d'une matrice d'appartenir à $\mathbf {P_{0}}$.

Le nom de ces matrices a été proposé par Fiedler et Pták (1966), qui ont aussi montré l'équivalence entre les définitions 1 et 2. L'expression 4 de la P0-matricité est due à Chen et Harker (1993).

Propriétés immédiates

De la définition 1, on déduit que

• $M\in \mathbf {P_{0}}$ si et seulement si $M^{\top \!}\in \mathbf {P_{0}}$,
• ioiuioo si $M$ est symétrique, alors $M\in \mathbf {P_{0}}$ si et seulement si $M$ est semi-définie positive,
• $\mathbf {P_{0}} \cap \mathbb {R} ^{n\times n}$ est un fermé de $\mathbb {R} ^{n\times n}$,
• si $M+M^{\!\top \!}$ est semi-définie positive, alors $M\in \mathbf {P_{0}} .$

Complexité

Vérifier qu'une matrice donnée dans $\mathbb {Q} ^{n\times n}$ est une P0-matrice est un problème co-NP-complet.

Annexes

Articles connexes

• Complémentarité linéaire
• P-matrice

Ouvrages généraux

• (en) R. W. Cottle, J.-S. Pang, R. E. Stone (2009). The linear complementarity problem. Classics in Applied Mathematics 60. SIAM, Philadelphia, PA, USA.
• (en) R. A. Horn, Ch. R. Jonhson (1991). Topics in Matrix Analysis. Cambridge University Press, New York, NY, USA.