P-matrice

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, une \mathbf{P}-matrice ou matrice \mathbf{P} est une matrice carrée réelle dont les mineurs principaux sont strictement positifs. Certains auteurs[1] qualifient ces matrices de totalement strictement positives.

Les \mathbf{P}-matrices interviennent dans l'étude des problèmes de complémentarité linéaire.

Une notion voisine est celle de \mathbf{P_0}-matrice.

Notations[modifier | modifier le code]

On note

  • [\![1,n]\!]:=\{1,\ldots,n\} l'ensemble des n premiers entiers,
  • u\cdot v le produit de Hadamard de deux vecteurs u et v, qui est défini par (u\cdot v)_i=u_iv_i, pour tout indice i,
  • M_{IJ} la sous-matrice de M formée de ses éléments avec indices de ligne dans I et indices de colonne dans J.

Définitions[modifier | modifier le code]

La notion de \mathbf{P}-matrice peut se définir de différentes manières, bien sûr équivalentes.

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

  1. tous les mineurs principaux de M sont strictement positifs : pour tout I\subset\{1,\ldots,n\} non vide, \det M_{II}>0,
  2. tout vecteur x\in\R^n vérifiant x\cdot(Mx)\leqslant 0 est nul,
  3. pour tout I\subset\{1,\ldots,n\} non vide, les valeurs propres réelles de M_{II} sont strictement positives.

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

Le nom de ces matrices a été proposé par Fiedler et Pták (1966)[2]. L'équivalence entre les définitions 1 et 2 est due à Fiedler et Pták (1962)[3].

Propriétés immédiates[modifier | modifier le code]

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

  • M\in\mathbf{P} si, et seulement si, M^{\top\!}\in\mathbf{P},
  • si M est symétrique, alors M\in\mathbf{P} si, et seulement si, M est définie positive,
  • \mathbf{P}\cap\R^{n\times n} est un ouvert de \R^{n\times n}.

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

Autres propriétés[modifier | modifier le code]

Complémentarité linéaire[modifier | modifier le code]

Un problème de complémentarité linéaire consiste à trouver un vecteur x\geqslant 0, tel que Mx+q\geqslant 0 et x^{\!\top\!}(Mx+q)=0. Dans cette définition, M\in\mathbb{R}^{n\times n}, q\in\R^n, x^{\!\top\!} est le transposé de x et les inégalités doivent se comprendre composante par composante. Ce problème est parfois noté de manière compacte comme suit


\mbox{CL}(M, q)\qquad
0\leqslant x\perp(Mx+q)\geqslant 0.

Existence et unicité de solution[modifier | modifier le code]

L'importance des \mathbf{P}-matrices dans les problèmes de complémentarité linéaire vient du résultat d'existence et d'unicité suivant[4].

\mathbf{P}-matrice et problème de complémentarité linéaire — Pour une matrice M\in\mathbb{R}^{n\times n}, les propriétés suivantes sont équivalentes :

  • M\in\mathbf{P},
  • pour tout vecteur q\in\R^n, le problème de complémentarité linéaire \mbox{CL}(M, q) a une et une seule solution.

Dès lors, si M\notin\mathbf{P}, il existe un vecteur q\in\R^n tel que l'une des deux situations exclusives suivantes a lieu :

  • soit \mbox{CL}(M,q) n'a pas de solution,
  • soit \mbox{CL}(M,q) a plus d'une solution.

On ne peut cependant pas affirmer que, pour une matrice M\notin\mathbf{P}, même symétrique et non dégénérée, il existe un vecteur q tel que la première des deux situations ci-dessus ait lieu. Ainsi


M=\begin{pmatrix}1&2\\2&1\end{pmatrix}

n'est pas une \mathbf{P}-matrice, mais le problème \mbox{CL}(M, q) a une solution quel que soit q.

Caractérisation algorithmique[modifier | modifier le code]

La complémentarité linéaire offre une autre caractérisation des \mathbf{P}-matrices, en termes d'une propriété d'un algorithme de résolution de ces problèmes, l'algorithme de Newton-min. Celui-ci est bien défini lorsque la matrice M est non dégénérée. Pour une telle matrice et un vecteur q donnés, on peut associer à un ensemble d'indices I\subset[\![1,n]\!], un nœud noté x^{(I)} qui est l'unique solution x du système linéaire


x_{I^c}=0
\qquad\mbox{et}\qquad
(Mx+q)_I=0.

On a noté I^c:=[\![1,n]\!]\setminus I le complémentaire de I dans [\![1,n]\!]. Brièvement, l'algorithme de Newton-min est celui de Newton semi-lisse pour résoudre l'équation linéaire par morceaux


\min(x,Mx+q)=0,

qui est équivalente au problème \mbox{CL}(M,q). Dans la version qui importe dans le résultat ci-dessous, l'algorithme de Newton-min détermine d'abord, au point courant x\in\R^n, l'ensemble d'indices


I=\{i\in[\![1,n]\!]:x_i>(Mx+q)_i\}

et calcule ensuite l'itéré suivant x^+=x^{(I)}. On a la caractérisation suivante (théorème 4.2 dans [[5]]).

\mathbf{P}-matrice et algorithme de Newton-min — Pour une matrice M\in\mathbb{R}^{n\times n} non dégénérée, les propriétés suivantes sont équivalentes :

  • M\in\mathbf{P},
  • quel que soit q, l'algorithme de Newton-min décrit ci-dessus ne cycle pas entre deux nœuds lorsqu'il est utilisé pour résoudre \mbox{CL}(M,q).

Résolution en temps polynomial ?[modifier | modifier le code]

On ne connait pas d'algorithme permettant de résoudre le problème \mbox{CL}(M,q) en temps polynomial lorsque M\in\mathbf{P}, mais certains ont proposé des arguments en faveur de cette possibilité[6],[7],[8].

Vérifier la P-matricité[modifier | modifier le code]

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

Une manière évidente de vérifier la P-matricité d'une matrice M donnée est de calculer ses 2^n-1 mineurs principaux (test des mineurs principaux), ce qui requiert O(n^3\,2^n) opérations. Rump (2003[10]) a montré que, quel que soit I\subset[\![1,n]\!] non vide, on peut trouver une matrice M\in\R^{n\times n} telle que \det M_{II}<0 et \det M_{JJ}>0 pour tout J\subset[\![1,n]\!] non vide et différent de I, si bien que le test des mineurs principaux ne peut négliger aucun mineur.

Tsatsomeros et Li (2000[11]) ont proposé un test, fondé sur le complément de Schur, qui réduit le nombre d'opérations à 7\,2^n. Le test requiert toujours ce nombre exponentiel d'opérations si la matrice est une P-matrice, mais peut en demander beaucoup moins si M\notin\mathbf{P}, car un seul mineur négatif suffit pour montrer cette non-appartenance.

Rump (2003) a proposé le premier test qui ne demande pas nécessairement un nombre exponentiel d'opérations pour vérifier la P-matricité.

Exemples[modifier | modifier le code]

  1. Une matrice de Cauchy C\in\R^{n\times n} est une matrice réelle carrée dont l'élément (i,j) est donné par
    \displaystyle C_{ij}=\frac{1}{a_i+b_j},
    a_i+b_j\ne0. Une matrice de Cauchy est une \mathbf{P}-matrice si a_1+b_1>0 et si les suites \{a_i\} et \{b_j\} sont strictement croissantes[12]. En particulier, une matrice de Hilbert est une \mathbf{P}-matrice (c'est une matrice de Cauchy avec a_i=b_i=i-1/2 pour tout i\in[\![1,n]\!]).
  2. Considérons la matrice circulante M\in\mathbb{R}^{n\times n}, n\geqslant 2, définie par
    M=\begin{pmatrix}1       &              &        & \alpha\\\alpha  & ~~~\ddots~~~ &        & \\        & ~~~\ddots~~~ & 1      & \\        &              & \alpha & 1\end{pmatrix}
    ou de manière plus précise par M_{ij}=1 si i=j, M_{ij}=\alpha si i=(j\mod n)+1 et M_{ij}=0 sinon. Alors[13]
    • si n est pair, alors M\in\mathbf{P} si, et seulement si, |\alpha|<1,
    • si n est impair, alors M\in\mathbf{P} si, et seulement si, \alpha>-1.
  3. Considérons la matrice circulante M\in\mathbb{R}^{n\times n}, n\geqslant 3, définie par
    M=\begin{pmatrix}
1      &              &           & \beta~~~  & \alpha \\
\alpha & ~~~\ddots~~~ &           &           & \beta  \\
\beta  & ~~~\ddots~~~ & 1~~~      &                    \\
       & ~~~\ddots~~~ & \alpha~~~ & 1~~~               \\
       &              & \beta~~~  & \alpha~~~ & 1
\end{pmatrix}
    ou de manière plus précise par
    M_{ij}=\left\{\begin{array}{ll}
1      & \mbox{si}~ i=j \\
\alpha & \mbox{si}~ i=(j \mod n) + 1 \\
\beta  & \mbox{si}~ i=((j+1)\mod n) + 1 \\
0      & \mbox{sinon}.
\end{array}\right.
    Alors[13] M\in\mathbf{P} si |\alpha|-1<\beta<|\alpha|/4 ou si \alpha^2+8(\beta-{\textstyle\frac{1}{2}})^2<2.

Annexes[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Définition 1.12, page 20, chez Berman et Shaked-Monderer (2003).
  2. (en) M. Fiedler, V. Pták (1966). Some generalizations of positive definiteness and monotonicity. Numerische Mathematik, 9, 163–172.
  3. (en) M. Fiedler, V. Pták (1962). On matrices with nonpositive off-diagonal elements and principal minors. Czechoslovak Mathematics Journal, 12, 382–400.
  4. (en) H. Samelson, R. M. Thrall, O. Wesler (1958). A partition theorem for the Euclidean n-space. Proceedings of the American Mathematical Society, 9, 805–807.
  5. (en) I. Ben Gharbia, J.Ch. Gilbert (2012). An algorithmic characterization of \mathbf{P}-matricity. SIAM Journal on Matrix Analysis and Applications (à paraître). Rapport de recherche INRIA RR-8004.
  6. (en) W. Morris (2002). Randomized pivot algorithms for P-matrix linear complementarity problems. Mathematical Programming, 92A, 285–296. doi
  7. (en) N. Megiddo (1988). A note on the complexity of P-matrix LCP and computing an equilibrium. Technical Report RJ 6439 (62557). IBM Research, Almaden Research Center, 650 Harry Road, San Jose, CA, USA.
  8. (en) D. Solow, R. Stone, C.A. Tovey (1987). Solving LCP on P-matrices is probably not NP-hard. Unpublished note.
  9. (en) G. E. Coxson (1994). The P-matrix problem is co-NP-complete. Mathematical Programming, 64, 173–178. doi
  10. Théorème 2.2 de Rump (2003).
  11. M.J. Tsatsomeros, L. Li (2000). A recurcive test for P -matrices. BIT, 40, 410–414.
  12. Exemple 1.7, page 20, chez Berman et Shaked-Monderer (2003).
  13. a et b (en) I. Ben Gharbia, J.Ch. Gilbert (2012). Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix. Mathematical Programming, 134, 349-364. doi lien Zentralblatt MATH

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) A. Berman, N. Shaked-Monderer (2003). Completely Positive Matrices. World Scientific, River Edge, NJ, USA.
  • (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.
  • (en) S. M. Rump (2003). On P-matrices. Linear Algebra and its Applications, 363, 237–250.