En mathématiques, une P-matrice ou matrice P est une matrice carrée réelle dont les mineurs principaux sont strictement positifs. Certains auteursDéfinition 1.12, page 20, chez Berman et Shaked-Monderer (2003). qualifient ces matrices de totalement strictement positives.

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

Une notion voisine est celle de P-matrice.

Notations

On note l'ensemble des premiers entiers, le produit de Hadamard de deux vecteurs et , qui est défini par pour tout indice , la sous-matrice de formée de ses éléments avec indices de ligne dans et indices de colonne dans .

Définitions

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

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

Propriétés immédiates

De la définition 1, on déduit que si, et seulement si, , si est symétrique, alors si, et seulement si, est définie positive, est un ouvert de .

De la définition 2, on déduit que si est définie positive, alors

Autres propriétés

Complémentarité linéaire

Un problème de complémentarité linéaire consiste à trouver un vecteur tel que et Dans cette définition, est le transposé de et les inégalités doivent se comprendre composante par composante. Ce problème est parfois noté de manière compacte comme suit

Existence et unicité de solution

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

Dès lors, si , il existe un vecteur tel que l'une des deux situations exclusives suivantes a lieu : soit n'a pas de solution, soit a plus d'une solution. On ne peut cependant pas affirmer que, pour une matrice , même symétrique et non dégénérée, il existe un vecteur tel que la première des deux situations ci-dessus ait lieu. Ainsi

n'est pas une P-matrice, mais le problème a une solution quel que soit

Caractérisation algorithmique

La complémentarité linéaire offre une autre caractérisation des 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 est non dégénérée. Pour une telle matrice et un vecteur donnés, on peut associer à un ensemble d'indices , un nœud noté qui est l'unique solution du système linéaire

On a noté le complémentaire de dans . Brièvement, l'algorithme de Newton-min est celui de Newton semi-lisse pour résoudre l'équation linéaire par morceaux

qui est équivalente au problème . Dans la version qui importe dans le résultat ci-dessous, l'algorithme de Newton-min détermine d'abord, au point courant , l'ensemble d'indices

et calcule ensuite l'itéré suivant . On a la caractérisation suivante.]).

Résolution en temps polynomial ?

On ne connait pas d'algorithme permettant de résoudre le problème en temps polynomial lorsque , mais certains ont proposé des arguments en faveur de cette possibilité...

Vérifier la P-matricité

Vérifier qu'une matrice donnée dans est une P-matrice est un problème co-NP-complet.

Une manière évidente de vérifier la P-matricité d'une matrice donnée est de calculer ses mineurs principaux (test des mineurs principaux), ce qui requiert opérations. Rump (2003Théorème 2.2 de Rump (2003).) a montré que, quel que soit non vide, on peut trouver une matrice telle que et pour tout non vide et différent de , si bien que le test des mineurs principaux ne peut négliger aucun mineur.

Tsatsomeros et Li (2000.) ont proposé un test, fondé sur le complément de Schur, qui réduit le nombre d'opérations à . Le test requiert toujours ce nombre exponentiel d'opérations si la matrice est une P-matrice, mais peut en demander beaucoup moins si , 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

Une matrice de Cauchy est une matrice réelle carrée dont l'élément est donné par

où . Une matrice de Cauchy est une P-matrice si et si les suites et sont strictement croissantesExemple 1.7, page 20, chez Berman et Shaked-Monderer (2003).. En particulier, une matrice de Hilbert est une P-matrice (c'est une matrice de Cauchy avec pour tout ). Considérons la matrice circulante définie parou de manière plus précise par si , si et sinon. Alors 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 si est pair, alors si, et seulement si, , si est impair, alors si, et seulement si, . Considérons la matrice circulante définie parou de manière plus précise parAlors si ou si .

Annexes

Notes

Articles connexes

Complémentarité linéaire P0-matrice

Bibliographie

. . . .

P-matrice Catégorie:Complémentarité linéaire