title: Q0-matrice
text: # Q0-matrice
  
  En mathématiques, une $Q_0-matrice$ est une matrice carrée réelle apportant des propriétés particulières aux problèmes de complémentarité linéaire. Ce sont celles qui assurent l'existence d'une solution dès que le problème est réalisable.
  
  ## Définitions
  
  ### Quelques notations
  
  Pour un vecteur $v\in \mathbb {R} ^{n}$, la notation $v\geqslant 0$ signifie que toutes les composantes $v_{i}$ du vecteur sont positives.
  
  On note $\mathbb {R} _{+}^{n}:=\{x\in \mathbb {R} ^{n}:x\geqslant 0\}$ l'orthant positif de $\mathbb {R} ^{n}$.
  
  Si $A$ est une matrice d'ordre $n$, on note $A(\mathbb {R} _{+}^{n}):=\{Ax:x\geqslant 0\}$ l'image de $\mathbb {R} _{+}^{n}$ par $A$ ; c'est un cône polyédrique (donc un fermé).
  
  ### Problème de complémentarité
  
  Étant donnés une matrice réelle carrée $M\in \mathbb {R} ^{n\times n}$ et un vecteur $q\in \mathbb {R} ^{n}$, un problème de complémentarité linéaire consiste à trouver un vecteur $x\in \mathbb {R} ^{n}$ tel que $x\geqslant 0$, $Mx+q\geqslant 0$ et $x^{\!\top }(Mx+q)=0$, ce que l'on écrit de manière abrégée comme suit :
  
  ${\mbox{CL}}(M,q):\qquad 0\leqslant x\perp (Mx+q)\geqslant 0.$
  
  Un point $x$ vérifiant $x\geqslant 0$ et $Mx+q\geqslant 0$ est dit admissible pour le problème ${\mbox{CL}}(M,q)$ et l'ensemble
  
  ${\mbox{Adm}}(M,q):=\{x\in \mathbb {R} ^{n}:x\geqslant 0,~Mx+q\geqslant 0\}$
  
  est appelé l'ensemble admissible de ce problème. On dit que le problème ${\mbox{CL}}(M,q)$ est réalisable si ${\mbox{Adm}}(M,q)\neq \varnothing$.
  
  ### $Q_0-matrice$
  
  Pour $M\in \mathbb {R} ^{n\times n}$, on introduit les deux cônes de $\mathbb {R} ^{n}$ suivants
  
  ${\begin{array}{rcl}Q_{R}(M)&:=&\{q\in \mathbb {R} ^{n}:\operatorname {CL} (M,q)~{\mbox{est réalisable}}\},\\Q_{S}(M)&:=&\{q\in \mathbb {R} ^{n}:\operatorname {CL} (M,q)~{\mbox{a une solution}}\}.\end{array}}$
  
  Évidemment $Q_{S}(M)\subset Q_{R}(M)$, sans que l'on ait nécessairement égalité (c'est ce qui motive l'introduction de la notion de $Q_0-matrice).$ Le cône $Q_{R}(M)$ est convexe polyédrique car il s'écrit comme la somme de deux cônes convexes polyédriques :
  
  $Q_{R}(M)=R_{+}^{n}-M(R_{+}^{n})$
  
  Au contraire, $Q_{S}(M)$ n'est pas nécessairement convexe. En réalité, on montre que $Q_{S}(M)$ est une réunion de cônes convexes $polyédriques^,^,$ (disjoints quel que soit $q$ si et seulement si $M$ est suffisante en colonne) :
  
  $Q_{S}(M)=\displaystyle \bigcup _{I\subset \{1,\ldots ,n\}}\,K_{I}(\mathbb {R} _{+}^{n})$
  
  où $K_{I}$ est la matrice dont les colonnes sont données par
  
  $(K_{I})^{I}=-M^{I}\qquad {\mbox{et}}\qquad (K_{I})^{I^{c}}=I^{I^{c}}.$
  
  On voit que les deux cônes dont $Q_{R}(M)$ est la somme sont contenus dans $Q_{S}(M)$ ; on les obtient en prenant $I=\varnothing$ et $I=\{1,\ldots ,n\}$. Ces observations conduisent à la définition suivante.
  
  $Q_0-matrice$ — On dit qu'une matrice $M\in \mathbb {R} ^{n\times n}$ est une $Q_0-matrice$ si elle vérifie l'une des conditions équivalentes suivantes :
  
  * le problème $\operatorname {CL} (M,q)$ a une solution s'il est réalisable,
  * $Q_{S}(M)=Q_{R}(M)$,
  * $Q_{S}(M)$ est convexe.
  
  On note $\mathbf {Q_{0}}$ l'ensemble des $Q_0-matrices.$
  
  