Matrice dégénérée

En mathématiques, une matrice carrée réelle est dite dégénérée si un de ses mineurs principaux est nul. Une matrice carrée réelle non dégénérée est donc une matrice dont tous les mineurs principaux sont non nuls.

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

Définition

Pour toute matrice Modèle:Mvar, on note Modèle:Mvar la sous-matrice formée des éléments avec indices de ligne dans Modèle:Mvar et indices de colonne dans Modèle:Mvar. Modèle:Théorème

La matrice Modèle:Mvar est donc dégénérée si et seulement si, pour un certain vecteur non nul $u\in {ℝ}^n$, il existe Modèle:Mvar et Modèle:Mvar, complémentaires dans $\{1,\dots ,n\}$, tels que $M_{II}{u}_I=0$ et $u_J=0$, ce qui équivaut à $u\circ (Mu)=0$ où $\circ$ désigne le produit de Hadamard.

Complexité

Vérifier qu'une matrice donnée dans ${\mathrm{M}}_n(\mathbb{Q})$ est non dégénérée est un problème co-NP-completModèle:,.

Rôle dans les problèmes de complémentarité

La non-dégénérescence d'une matrice $M\in {\mathrm{M}}_n(ℝ)$ est reliée à une notion d'unicité locale des solutions du problème de complémentarité linéaire $\mathrm{LCP}(q,M)$, dont l'espace des solutions est noté $\mathrm{SOL}(q,M)$. Cet espace est discret si et seulement si toute solution est localement unique, c'est-à-dire isolée dans $\mathrm{SOL}(q,M)$.

Annexes

Articles connexes

• Algorithme de Newton-min
• P-matrice

Bibliographie

• Modèle:Ouvrage Modèle:Plume
• Modèle:En R. A. Horn et Ch. R. Jonhson, Topics in Matrix Analysis, New York, Cambridge University Press, 1991
• Modèle:Ouvrage Modèle:Plume