Q0-matrice
# 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.$

