Matrice dégénérée

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 ${\displaystyle M\in \operatorname {M} _{n}(\mathbb {R} )}$ est non dégénérée si tous ses mineurs principaux sont non nuls :

${\displaystyle \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 ${\displaystyle u\in \mathbb {R} ^{n}}$, il existe I et J, complémentaires dans ${\displaystyle \{1,\ldots ,n\}}$, tels que ${\displaystyle M_{II}u_{I}=0}$ et ${\displaystyle u_{J}=0}$, ce qui équivaut[1] à ${\displaystyle u\circ (Mu)=0}$ où ${\displaystyle \circ }$ désigne le produit de Hadamard.

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

La non-dénénérescence d'une matrice ${\displaystyle 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 ${\displaystyle \operatorname {LCP} (q,M)}$, dont l'espace des solutions est noté ${\displaystyle \operatorname {SOL} (q,M)}$[4]. Cet espace est discret si et seulement si toute solution est localement unique, c'est-à-dire isolée dans ${\displaystyle \operatorname {SOL} (q,M)}$.