Théorèmes de l'alternative

On commence par extraire de ${\displaystyle (f_{1},\ldots ,f_{k})}$ une famille libre maximale ; quitte à renuméroter, on suppose que c'est ${\displaystyle (f_{1},\ldots ,f_{p})}$. On la complète arbitrairement en une base ${\displaystyle (f_{1},\ldots ,f_{p},f'_{p+1},\ldots ,f'_{n})}$ de ${\displaystyle E^{*}}$ et enfin on note ${\displaystyle (e_{1},\ldots ,e_{n})}$ la base de ${\displaystyle E}$ dont ${\displaystyle (f_{1},\ldots ,f_{p},f'_{p+1},\ldots ,f'_{n})}$ est la base duale. On a donc, pour tout ${\displaystyle i}$ entre ${\displaystyle 1}$ et ${\displaystyle n}$ et tout ${\displaystyle j}$ entre ${\displaystyle 1}$ et ${\displaystyle p}$ la relation ${\displaystyle f_{j}(e_{i})=\delta _{ij}}$ (symbole de Kronecker) ; comme les ${\displaystyle f_{j}}$ pour ${\displaystyle j}$ entre ${\displaystyle p+1}$ et ${\displaystyle k}$ sont des combinaisons linéaires des premiers ${\displaystyle f_{j}}$, toutes les formes ${\displaystyle f_{j}}$ s'annulent sur tous les ${\displaystyle e_{i}}$ d'indices ${\displaystyle i\geq p+1}$.

Une fois ces notations posées, lançons nous dans la preuve de Stiemke. Comme dans chaque énoncé, l'implication montante est évidente. Prouvons l'autre par contraposition, en supposant donc que 0 ne peut pas être écrit sous la forme ${\displaystyle 0=\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}}$ avec des ${\displaystyle \lambda _{j}}$ tous strictement positifs, dans le but de construire un ${\displaystyle y}$ solution du système d'inéquations.

Une relation entre applications linéaires est vraie, si et seulement si, elle est vraie en tout vecteur d'une base donnée ; on peut donc remarquer que :

Le système ${\displaystyle \left\{{\begin{array}{l}{\begin{matrix}\lambda _{1}>0\\\vdots \\\lambda _{k}>0\\\end{matrix}}\\{\begin{matrix}(\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k})(e_{1})=0\\\vdots \\(\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k})(e_{n})=0\\\end{matrix}}\\\end{array}}\right.}$ n'a pas de solutions.

Insérons dans ce système les informations sur les ${\displaystyle f_{j}(e_{i})}$, on sait ainsi que :

Le système ${\displaystyle \left\{{\begin{array}{l}{\begin{matrix}\lambda _{1}>0\\\vdots \\\lambda _{k}>0\\\end{matrix}}\\{\begin{matrix}\lambda _{1}&&&+\lambda _{p+1}f_{p+1}(e_{1})+\cdots +\lambda _{k}f_{k}(e_{1})=0\\&&&\vdots \\&&\lambda _{p}&+\lambda _{p+1}f_{p+1}(e_{p})+\cdots +\lambda _{k}f_{k}(e_{p})=0\\\end{matrix}}\\\end{array}}\right.}$ n'a pas de solutions.

Point crucial de la preuve, l'inconsistance du système mixte d'inéquations et équations qui précède peut se réexprimer comme inconsistance d'un système plus simple ne comprenant plus que des inéquations :

Le système ${\displaystyle \left\{{\begin{array}{l}{\begin{matrix}\lambda _{p+1}f_{p+1}(e_{1})+\cdots +\lambda _{k}f_{k}(e_{1})<0\\\vdots \\\lambda _{p+1}f_{p+1}(e_{p})+\cdots +\lambda _{k}f_{k}(e_{p})<0\\\end{matrix}}\\\end{array}}\right.}$ n'a pas de solutions.

La forme de ce système rentre dans le cadre du théorème de Gordan. Il existe donc des réels positifs ou nuls ${\displaystyle \alpha _{1},\ldots ,\alpha _{p}}$, dont au moins un n'est pas nul, avec lesquels on peut construire une combinaison linéaire nulle des formes apparaissant dans le système qui précède. En annulant successivement le coefficient de chaque ${\displaystyle \lambda _{j}}$, on constate que :

pour tout indice ${\displaystyle i}$ entre ${\displaystyle p+1}$ et ${\displaystyle k}$, ${\displaystyle f_{i}(\alpha _{1}e_{1}+\cdots +\alpha _{p}e_{p})=0}$.

Il découle par ailleurs des relations ${\displaystyle f_{j}(e_{i})=\delta _{ij}}$ que

pour les indices ${\displaystyle i}$ entre ${\displaystyle 1}$ et ${\displaystyle p}$, ${\displaystyle f_{i}(\alpha _{1}e_{1}+\cdots +\alpha _{p}e_{p})=\alpha _{i}}$.

Posons alors ${\displaystyle y=\alpha _{1}e_{1}+\cdots +\alpha _{p}e_{p}}$. On s'aperçoit alors qu'on vient de construire avec ce vecteur une solution non triviale du système d'inéquations objet de l'énoncé du théorème de Stiemke.

On montre le lemme de Farkas par récurrence sur la dimension. Il est évident en dimension 0 ou 1 ; supposons le vrai en toute dimension strictement inférieure à ${\displaystyle \mathrm {dim} \,E}$.

On vérifie sans mal que si on dispose du théorème de Farkas pour des familles de formes linéaires toutes non nulles, les cas particuliers où telle ou telle des ${\displaystyle f_{j}}$ est la forme nulle s'en déduit sans aucune difficulté. On supposera dès lors toutes les ${\displaystyle f_{j}}$ non nulles.

Supposons inconsistant le système qui apparaît dans l'énoncé du lemme de Farkas. Celui qui apparaît dans l'énoncé de Gordan est a fortiori inconsistant. On peut donc écrire :

${\displaystyle \lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}=0\qquad (*)}$

avec des réels positifs ou nuls ${\displaystyle \lambda _{j}}$ dont un au moins n'est pas nul.

• Cas évident : si ${\displaystyle \lambda _{1}\not =0}$. Le résultat souhaité est obtenu, on a fini.

• Cas problématique : si ${\displaystyle \lambda _{1}=0}$. Quitte à renuméroter les ${\displaystyle f_{j}}$, on peut alors supposer qu'il y a un ${\displaystyle p\leq k}$ tel que les ${\displaystyle \lambda _{j}}$ non nuls soient exactement ${\displaystyle \lambda _{2},\ldots ,\lambda _{p}}$. Quitte à multiplier les ${\displaystyle f_{j}}$ par des constantes strictement positives, on peut même supposer, ce qui simplifiera les calculs, que la relation ${\displaystyle (*)}$ se réduit à :

${\displaystyle f_{2}+\cdots +f_{p}=0}$.

Notons ${\displaystyle H=\mathrm {Ker} \,f_{2}}$, de dimension strictement plus petite que ${\displaystyle E}$ puisque ${\displaystyle f_{2}}$ n'est pas nulle. Le lemme de Farkas est donc vrai dans ${\displaystyle H}$. Par ailleurs le système ${\displaystyle f_{1}(y)>0,f_{3}(y)\geq 0,\ldots ,f_{k}(y)\geq 0}$ est sans solution dans ${\displaystyle H}$.

Il existe donc des réels positifs ou nuls ${\displaystyle \mu _{1},\mu _{3}\ldots ,\mu _{k}}$ avec ${\displaystyle \mu _{1}>0}$ tels que :

pour tout ${\displaystyle y}$ de ${\displaystyle H}$, ${\displaystyle \mu _{1}f_{1}(y)+\mu _{3}f_{3}(y)+\cdots +\mu _{k}f_{k}(y)=0}$.

Les formes linéaires nulles sur l'hyperplan ${\displaystyle H=\mathrm {Ker} \,f_{2}}$ sont exactement les multiples de ${\displaystyle f_{2}}$. Il existe donc un réel ${\displaystyle \nu }$ tel que :

${\displaystyle \mu _{1}f_{1}+\mu _{3}f_{3}+\cdots +\mu _{k}f_{k}=\nu f_{2}}$.

• • Si ${\displaystyle \nu \leq 0}$, on regroupe cette relation en ${\displaystyle \mu _{1}f_{1}-\nu f_{2}+\mu _{3}f_{3}+\cdots +\mu _{k}f_{k}=0}$ et on a terminé ;

• • Si ${\displaystyle \nu >0}$, on récupère la relation en attente ${\displaystyle f_{2}+\cdots +f_{p}=0}$ et on termine en écrivant : ${\displaystyle \mu _{1}f_{1}+(\mu _{3}+\nu )f_{3}+\cdots +(\mu _{p}+\nu )f_{p}+\mu _{p+1}f_{p+1}+\mu _{k}f_{k}=0}$ et on a aussi terminé.

La vérification qui suit utilise les notations non de la version donnée plus haut mais de la version dite « version vectorielle » dans l'article lemme de Farkas (qui lui est équivalente de façon immédiate) à laquelle on se réfèrera donc.

Pour chaque colonne ${\displaystyle C_{j}}$ de ${\displaystyle A}$ (${\displaystyle 1\leq j\leq k}$), notons ${\displaystyle f_{j}}$ la forme linéaire définie sur ${\displaystyle \mathbb {R} ^{n}}$ par ${\displaystyle y\mapsto C_{j}^{T}y}$ ; notons par ailleurs ${\displaystyle g}$ la forme linéaire ${\displaystyle y\mapsto b^{T}y}$.

L'existence d'une solution pour la première branche de l'alternative, c'est l'existence d'un ${\displaystyle k}$-uplet ${\displaystyle (x_{1},\ldots ,x_{k})}$ de nombres positifs ou nuls tels que ${\displaystyle x_{1}C_{1}+\cdots +x_{k}C_{k}=b}$, autrement dit c'est la possibilité d'écrire ${\displaystyle g}$ comme combinaison linéaire à coefficients positifs des ${\displaystyle f_{j}}$.

L'existence d'une solution pour la deuxième branche de l'alternative, c'est l'existence d'un ${\displaystyle y}$ qui soit dans ${\displaystyle \{y\in E\,\mid \,f_{1}(y)\geq 0,\cdots ,f_{k}(y)\geq 0\}}$ mais qui ne soit pas dans ${\displaystyle \{y\in E\,\mid \,g(y)\geq 0\}}$.

L'équivalence annoncée par le théorème de Farkas garantit donc précisément qu'un et un seul des deux systèmes a une solution.

Il se vérifie en quelques lignes : introduisons la matrice définie par collage de deux blocs : ${\displaystyle M={\begin{pmatrix}A&I_{n}\end{pmatrix}}}$ et explicitons pour cette matrice ${\displaystyle M}$ l'alternative matricielle énoncée par le théorème de Gordan.

La deuxième branche est immédiate : ${\displaystyle M^{T}y>0}$ est directement équivalent à ${\displaystyle A^{T}y>0}$ et ${\displaystyle y>0}$, ce qui est exactement le système figurant en deuxième branche de l'alternative dans l'énoncé qu'on est en train de montrer.

La première demande un peu plus de concentration. L'existence d'un ${\displaystyle z}$ tel que ${\displaystyle Mz=0}$ avec ${\displaystyle z\geq 0}$ et ${\displaystyle z\not =0}$ revient, en appelant ${\displaystyle x}$ le vecteur-colonne regroupant les ${\displaystyle k}$ premières composantes de ${\displaystyle z}$ et ${\displaystyle v}$ celui regroupant les ${\displaystyle n}$ dernières, à l'existence de ${\displaystyle (x,v)}$ avec :

${\displaystyle Ax+v=0}$, ${\displaystyle x\geq 0}$, ${\displaystyle v\geq 0}$ et ${\displaystyle (x,v)\not =0}$.

Ce système équivaut immédiatement à :

${\displaystyle Ax+v=0}$, ${\displaystyle x\geq 0}$, ${\displaystyle v\geq 0}$ et ${\displaystyle x\not =0}$ (il ne peut avoir de solution avec ${\displaystyle x=0}$ mais ${\displaystyle v\not =0}$).

Enfin on s'aperçoit que ce dernier système a des solutions, si et seulement si, le système plus simple, de seule inconnue ${\displaystyle x}$ :

${\displaystyle Ax\leq 0,x\geq 0,x\not =0}$ en possède.

On reconnaît la première branche de l'alternative dans l'énoncé du théorème de Ville, qui est ainsi prouvé.