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 ${\displaystyle M_{I,J}}$ la sous-matrice de ${\displaystyle M}$ formée de ses éléments avec indices de ligne dans ${\displaystyle I}$ et indices de colonne dans ${\displaystyle J.}$

P0-matrice — On dit qu'une matrice carrée réelle ${\displaystyle 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 ${\displaystyle M}$ sont positifs : pour tout ${\displaystyle I\subset \{1,\ldots ,n\}}$ non vide, ${\displaystyle \det M_{I,I}\geqslant 0}$,
2. pour tout vecteur ${\displaystyle x\in \mathbb {R} ^{n}}$ non nul, on peut trouver un indice ${\displaystyle i}$ tel que ${\displaystyle x_{i}\neq 0}$ et ${\displaystyle x_{i}(Mx)_{i}\geqslant 0}$,
3. pour tout ${\displaystyle I\subset \{1,\ldots ,n\}}$ non vide, les valeurs propres réelles de ${\displaystyle M_{I,I}}$ sont positives,
4. pour toute matrice diagonale définie positive ${\displaystyle D}$, ${\displaystyle M+D}$ est inversible.

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

Le nom de ces matrices a été proposé par Fiedler et Pták (1966^[1]), 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^[2]).

Propriétés immédiates

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

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

Complexité

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

Annexes

Note

1. (en) M. Fiedler, V. Pták (1966). Some generalizations of positive definiteness and monotonicity. Numerische Mathematik, 9, 163–172. doi
2. (en) B. Chen, P.T. Harker (1993). A non-interior continuation method for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 14, 1168–1190. doi
3. (en) P. Tseng (2000). Co-NP-completeness of some matrix classification problems. Mathematical Programming, 88, 183–192.

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.