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 $M$ , on note $M IJ$ la sous-matrice formée des éléments avec indices de ligne dans $I$ et indices de colonne dans $J$ .

Matrice non dégénérée — On dit qu'une matrice carrée réelle $M\in \operatorname {M} _{n}(\mathbb {R} )$ est non dégénérée si tous ses mineurs principaux sont non nuls :

\forall I\subset \{1,\ldots ,n\}\quad \det M_{II}\neq 0

.

La matrice $M$ est donc dégénérée si et seulement si, pour un certain vecteur non nul $u\in \mathbb {R} ^{n}$ , il existe $I$ et $J$ , complémentaires dans $\{1,\ldots ,n\}$ , tels que $M_{II}u_{I}=0$ et $u_{J}=0$ , ce qui équivaut^[1] à $u\circ (Mu)=0$ où $\circ$ désigne le produit de Hadamard.

Complexité

Vérifier qu'une matrice donnée dans $\operatorname {M} _{n}(\mathbb {Q} )$ est non dégénérée est un problème co-NP-complet^[2]^,^[3].

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

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

Matrice non dégénérée et complémentarité^[5] — Pour une matrice $M\in \operatorname {M} _{n}(\mathbb {R} )$ , les propriétés suivantes sont équivalentes :

$M$ est non dégénérée ;
pour tout $q\in \mathbb {R} ^{n}$ , $\operatorname {SOL} (q,M)$ a au plus $2^{n}$ éléments ;
pour tout $q\in \mathbb {R} ^{n}$ , $\operatorname {SOL} (q,M)$ est fini ;
pour tout $q\in \mathbb {R} ^{n}$ , $\operatorname {SOL} (q,M)$ est discret.

Notes et références

↑ Cette équivalence est mentionnée dans (en) P. Tseng, « Co-NP-completeness of some matrix classification problems », Mathematical Programming, vol. 88, n^o 1,‎ 2000, p. 183-192.
↑ (en) R. Chandrasekaran, S. N. Kabadi et K. G. Murty, « Some NP-complete problems in linear programming », Operations Research Letters, vol. 1, n^o 1,‎ 1982, p. 101-104.
↑ Murty 1988, p. 179.
↑ Cottle, Pang et Stone 2009, p. 2.
↑ Cottle, Pang et Stone 2009, Théorème 3.6.3.

Annexes

Articles connexes

Bibliographie

: document utilisé comme source pour la rédaction de cet article.

(en) R. W. Cottle, J.-S. Pang et R. E. Stone, The Linear Complementarity Problem, Philadelphia, PA, SIAM, coll. « Classics in Applied Mathematics » (n^o 60), 2009 (lire en ligne)
(en) R. A. Horn et Ch. R. Jonhson, Topics in Matrix Analysis, New York, Cambridge University Press, 1991
(en) K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Berlin, Heldermann Verlag, 1988

Portail de l’algèbre

[1] Cette équivalence est mentionnée dans (en) P. Tseng, « Co-NP-completeness of some matrix classification problems », Mathematical Programming, vol. 88, n^o 1,‎ 2000, p. 183-192.

[2] (en) R. Chandrasekaran, S. N. Kabadi et K. G. Murty, « Some NP-complete problems in linear programming », Operations Research Letters, vol. 1, n^o 1,‎ 1982, p. 101-104.

[3] Murty 1988, p. 179.

[4] Cottle, Pang et Stone 2009, p. 2.

[5] Cottle, Pang et Stone 2009, Théorème 3.6.3.

[1]

[2]

[3]

[4]

[5]