P-matrice

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

Sommaire

1 Définitions

2 Propriétés immédiates

3 Autres propriétés

3.1 Complémentarité linéaire

3.2 Complexité

4 Exemples

5 Annexes

5.1 Notes

5.2 Articles connexes

5.3 Bibliographie

Définitions

La notion de $\mathbf{P}$ -matrice peut se définir de différentes manières, bien sûr équivalentes. On note ci-dessous $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 .$ On note aussi $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 .$

$\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 :

tous les mineurs principaux de $M$ sont strictement positifs : pour tout $I\subset\{1,\ldots,n\}$ non vide, $det M I, I > 0,$

tout vecteur $x\in\R^n$ vérifiant $x\cdot(Mx)\leqslant 0$ est nul,

pour tout $I\subset\{1,\ldots,n\}$ non vide, les valeurs propres réelles de $M I, I$ 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)^[1]. L'équivalence entre les définitions 1 et 2 est due à Fiedler et Pták (1962)^[2].

Propriétés immédiates

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

si $M+M^{\!\top\!}$ est définie positive, alors $M\in\mathbf{P}.$

Autres propriétés

Complémentarité linéaire

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.$

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^[3].

$\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 $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 $CL(M, q)$ n'a pas de solution,

soit $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 $CL(M, q)$ a une solution quel que soit $q .$

Complexité

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^[4].

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

Exemples

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 i j = 1$ si $i = j$ , $M i j = α$ si $i=(j\mod n)+1$ et $M i j = 0$ sinon. Alors^[8]

si $n$ est pair, alors $M\in\mathbf{P}$ si et seulement si $| α | < 1$ ,

si $n$ est impair, alors $M\in\mathbf{P}$ si et seulement si $α > - 1$ .

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^[8] $M\in\mathbf{P}$ si $| α | - 1 < β < | α | / 4$ ou si $\alpha^2+8(\beta-{\textstyle\frac{1}{2}})^2<2$ .

Annexes

Notes

↑ (en) M. Fiedler, V. Pták (1966). Some generalizations of positive definiteness and monotonicity. Numerische Mathematik, 9, 163–172.

↑ (en) M. Fiedler, V. Pták (1962). On matrices with nonpositive off-diagonal elements and principal minors. Czechoslovak Mathematics Journal, 12, 382–400.

↑ (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.

↑ (en) G. E. Coxson (1994). The P-matrix problem is co-NP-complete. Mathematical Programming, 64, 173–178. doi

↑ (en) W. Morris (2002). Randomized pivot algorithms for P-matrix linear complementarity problems. Mathematical Programming, 92A, 285–296. doi

↑ (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.

↑ (en) D. Solow, R. Stone, C.A. Tovey (1987). Solving LCP on P-matrices is probably not NP-hard. Unpublished note.

↑ ^{a et b} (en) I. Ben Gharbia, J.Ch. Gilbert (2011). Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix. Mathematical Programming (à paraître). doi

Articles connexes

Complémentarité linéaire

P0-matrice

Bibliographie

(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.

Portail des mathématiques

Catégories :
Matrice
Complémentarité linéaire

Contenu soumis à la licence CC-BY-SA. Source : Article P-matrice de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Matrice (algèbre) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice (mathematiques) — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice carrée — Matrice (mathématiques) Pour les articles homonymes, voir Matrice. En mathématiques, les matrices servent à interpréter en termes calculatoire … Wikipédia en Français
Matrice Diagonalisable — En algèbre linéaire, une matrice carrée M d ordre n ( ) à coefficients dans un corps commutatif K, est dite diagonalisable si elle est semblable à une matrice diagonale, c est à dire s il existe une matrice inversible P et une matrice diagonale D … Wikipédia en Français
matrice — [ matris ] n. f. • 1265; lat. matrix 1 ♦ Vieilli Utérus. Inflammation de la matrice. ⇒ métrite. Fig. « La terre, inépuisable et suprême matrice » (Hugo). 2 ♦ (1556 ) Techn. Moule qui, après avoir reçu une empreinte particulière en creux et en… … Encyclopédie Universelle
Matrice Définie Positive — En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou complexes : aT désigne la… … Wikipédia en Français
Matrice Inversible — En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In suffit d aprés le… … Wikipédia en Français
Matrice definie positive — Matrice définie positive En algèbre linéaire, la notion de matrice définie positive est analogue à celle de nombre réel strictement positif. On introduit tout d abord les notations suivantes ; si a est une matrice à éléments réels ou… … Wikipédia en Français
Matrice inverse — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… … Wikipédia en Français
Matrice non singulière — Matrice inversible En mathématiques et plus particulièrement en algèbre linéaire, une matrice carrée A d ordre n est dite inversible ou régulière ou encore non singulière, s il existe une matrice B d ordre n telle que AB = BA = In, ( AB = In… … Wikipédia en Français
Matrice par blocs — Matrice par bloc En théorie des matrices, une matrice par bloc ou matrice partitionnée est une matrice pouvant être divisée en matrices rectangulaires de dimensions inférieures appelées blocs. On peut dire également que la matrice est écrite en… … Wikipédia en Français

Mark and share
Search through all dictionaries
Translate…
Search Internet

Share the article and excerpts