Théorèmes de l'alternative

Les théorèmes de l'alternative, dont le plus fameux est le lemme de Farkas, concernent tous un système d'inéquations linéaires dans un espace vectoriel réel de dimension finie. Il s'agit de donner un critère permettant de trancher si le système est ou non consistant, c'est-à-dire s'il admet ou non une solution (ou, pour ceux dont 0 est une solution évidente, une solution non nulle).

Le principe en est à chaque fois le suivant : face à un système d'inéquations, on peut opérer des combinaisons linéaires de ces inéquations à coefficients positifs ou nuls, qui sont alors toutes des conséquences du système (l'usage judicieux de coefficients strictement positifs permettant au cas par cas de produire des conséquences qui soient des inégalités strictes). Il est bien évident que si l'une de ces conséquences est une absurdité – typiquement $0<0$ – le système initial ne peut avoir de solution. Or, il se trouve que cette condition suffisante pour que le système soit inconsistant est à chaque fois nécessaire : chacun des théorèmes ci-dessous en exprime une variante.

Le nom de « théorèmes de l'alternative » vient du fait que la condition nécessaire et suffisante a, elle aussi, la forme d'un problème de recherche de solutions pour un système mêlant équations et inéquations. On se retrouve donc en parallèle avec deux systèmes, dont un et un seul a des solutions. Traduites en termes de matrices, les deux branches de l'alternative ont des formulations du même esprit, voire étonnamment semblables dans le cas du théorème de Ville.

Systèmes d'inéquations strictes et systèmes d'inéquations larges : les théorèmes de Gordan et de Stiemke

Le théorème de Gordan

Il couvre le cas d'un système d'inéquations toutes strictes, de la forme :

$f_{1}(y)>0,\,f_{2}(y)>0,\ldots ,f_{k}(y)>0$

où les $f_{j}$ sont des formes linéaires sur un espace vectoriel réel $E$ de dimension finie.

Il y a une obstruction évidente à l'existence de solutions pour un tel système : si on fait une combinaison linéaire à coefficients positifs non tous nuls de cette famille d'inéquations, on obtient une nouvelle inéquation stricte vérifiée par toutes les solutions. Si on peut ajuster les coefficients de cette combinaison linéaire de façon à obtenir l'inéquation absurde $0>0$, c'est que le système était inconsistant.

Le théorème de Gordan assure que, à partir de tout système inconsistant, on peut ainsi produire l'inéquation $0>0$ :

Théorème de Gordan (1873) — Soit $f_{1},\ldots ,f_{k}$ des formes linéaires sur un espace vectoriel réel de dimension finie $E$. Alors :

$\{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)>0,\ldots ,f_{k}(y)>0\}=\varnothing$

si et seulement si

il existe une écriture $0=\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}$ à coefficients tous positifs ou nuls dont l'un au moins n'est pas nul.

Le théorème de Stiemke

Il concerne les systèmes d'inéquations linéaires au sens large :

$f_{1}(y)\geq 0,\,f_{2}(y)\geq 0,\ldots ,f_{k}(y)\geq 0$.

Son énoncé est précisément le suivant :

Théorème de Stiemke (1915) — Soit $f_{1},\dots ,f_{k}$ des formes linéaires sur un espace vectoriel de dimension finie $E$. Alors :

$\{y\in E\,\mid \,f_{1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0$, l'une au moins de ces inégalités étant stricte$\}=\varnothing$

si et seulement si

il existe une écriture $0=\lambda _{1}f_{1}+\dots +\lambda _{k}f_{k}$ à coefficients tous strictement positifs.

Cet énoncé est rendu un peu plus difficile à lire que les autres théorèmes de la série à cause de la technicité « l'une au moins de ces inégalités étant stricte » ; la raison d'être de celle-ci est que les systèmes d'inéquations larges ne peuvent être complètement inconsistants : ils comptent au moins $0$ parmi leurs solutions, et au-delà tous les points qui vérifient le système d'équations linéaires correspondant. D'où la nécessité de compliquer un peu la forme du système en ne considérant pas comme des solutions significatives celles qui sont dans l'intersection des noyaux de toutes les formes $f_{j}$.

Démonstration du théorème de Gordan

Parmi tous les théorèmes considérés dans cette page, le théorème de Gordan est celui où la démonstration contient le moins de technicités supplémentaires. On peut la fonder sur un théorème de séparation des convexes (celui parfois appelé « deuxième forme géométrique du théorème de Hahn-Banach ») ou par le théorème de projection sur un convexe fermé. C'est ce dernier choix qui est fait ici.

Comme il est souvent pratique pour faire des manipulations dans un dual, munissons $E$ d'une structure euclidienne ; pour chaque indice $j$, il existe dès lors un vecteur $s_{j}$ unique de $E$ qui permette d'écrire pour tout $y$ : $f_{j}(y)=\langle s_{j}|y\rangle$.

Considérons le convexe compact $K$ enveloppe convexe des $k$ points $s_{j}$ et notons $y_{0}=\pi _{K}(0)$ la projection orthogonale de $0$ sur ce fermé de $E$. On sait que pour tout $s$ de $K$ (et en particulier pour les $s_{j}$) on dispose de l'inégalité : $\langle -y_{0}|s_{j}-y_{0}\rangle \leq 0$ qu'on regroupe en $\|y_{0}\|^{2}\leq f_{j}(y_{0})$.

Entrons dans le vif de la preuve de Gordan. Comme pour tous les théorèmes de l'article, l'implication montante est évidente. Montrons donc l'implication descendante, en supposant le système d'inégalités strictes inconsistant. En particulier $y_{0}$ n'en est alors pas solution, donc il existe un $j$ pour lequel $f_{j}(y_{0})\leq 0$. D'où $\|y_{0}\|=0$, puis $y_{0}=0$, ce qui prouve bien que $0$ appartient à $K$, et est donc combinaison linéaire à coefficients positifs des $s_{j}$.

Le théorème de Gordan entraîne le théorème de Stiemke

On peut donner une démonstration directe du théorème de Stiemke en appelant de nouveau la théorie de la séparation des convexes. Il est toutefois instructif de s'apercevoir que c'est un théorème « dual » du théorème de Gordan, et qu'on peut l'en déduire par des manipulations algébriques simples à défaut d'être naturelles.

On reverra ces mêmes manipulations présentées sous forme matricielle plus loin, en énonçant le théorème de Ville. Elles reposent sur une idée importante qu'on retrouve notamment à la base de la théorie du problème dual en optimisation linéaire : la deuxième branche de l'équivalence dans le théorème de Stiemke, qui est en première lecture un mélange d'inéquations strictes (les conditions $0<\lambda _{j}$) et d'une équation vectorielle (la condition $\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}=0$) peut, avec un peu de doigté, être transformée en une simple collection d'inéquations strictes, à laquelle on peut appliquer le théorème de Gordan. Stiemke apparaît finalement comme une réécriture de Gordan où les emplacements des deux énoncés équivalents se retrouvent intervertis.

Exécution de la preuve

On commence par extraire de $(f_{1},\ldots ,f_{k})$ une famille libre maximale ; quitte à renuméroter, on suppose que c'est $(f_{1},\ldots ,f_{p})$. On la complète arbitrairement en une base $(f_{1},\ldots ,f_{p},f'_{p+1},\ldots ,f'_{n})$ de $E^{*}$ et enfin on note $(e_{1},\ldots ,e_{n})$ la base de $E$ dont $(f_{1},\ldots ,f_{p},f'_{p+1},\ldots ,f'_{n})$ est la base duale. On a donc, pour tout $i$ entre $1$ et $n$ et tout $j$ entre $1$ et $p$ la relation $f_{j}(e_{i})=\delta _{ij}$ (symbole de Kronecker) ; comme les $f_{j}$ pour $j$ entre $p+1$ et $k$ sont des combinaisons linéaires des premiers $f_{j}$, toutes les formes $f_{j}$ s'annulent sur tous les $e_{i}$ d'indices $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 $0=\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}$ avec des $\lambda _{j}$ tous strictement positifs, dans le but de construire un $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 $\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 $f_{j}(e_{i})$, on sait ainsi que :

Le système $\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 $\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 $\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 $\lambda _{j}$, on constate que :

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

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

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

Posons alors $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.

Systèmes mêlant inéquations strictes et larges : le lemme de Farkas et le théorème de Motzkin

Les énoncés

Le lemme de Farkas énonce une condition nécessaire et suffisante d'inconsistance pour un système d'inéquations linéaires dont exactement une est stricte :

Lemme de Farkas(1902) — Soit $f_{1},\ldots ,f_{k}$ des formes linéaires sur un espace vectoriel réel de dimension finie $E$. Alors :

$\{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}=\varnothing$

si et seulement si

il existe une écriture $0=\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}$ à coefficients tous positifs ou nuls et avec $\lambda _{1}\not =0$.

Enfin le théorème de Motzkin couvre le cas général d'un système mêlant inéquations strictes et inéquations larges, avec une au moins stricte ; le lemme de Farkas en est le cas particulier correspondant à $p=1$ (le théorème de Gordan correspondant à $p=n$) :

Théorème de Motzkin (1936) — Soit $f_{1},\ldots ,f_{k}$ des formes linéaires sur un espace vectoriel réel de dimension finie $E$ et soit p avec $1\leq p\leq n$. Alors :

$\{y\in E\,\mid \,f_{1}(y)>0,f_{2}(y)>0,\ldots ,f_{p}(y)>0,f_{p+1}\geq 0,\ldots ,f_{k}(y)\geq 0\}=\varnothing$

si et seulement si

il existe une écriture $0=\lambda _{1}f_{1}+\cdots +\lambda _{k}f_{k}$ à coefficients tous positifs ou nuls avec $(\lambda _{1},\ldots ,\lambda _{p})\not =0$.

Le théorème de Gordan entraîne le lemme de Farkas

Le théorème de Gordan se démontre en moins d'une dizaine de lignes à condition de disposer des théorèmes de séparation des convexes ou de projection sur un convexe fermé. On peut à partir de là prouver le lemme de Farkas avec un peu de gymnastique supplémentaire, qui ne nécessite aucun outil avancé mais n'est pas complètement naturelle.

Détails de la déduction de Farkas depuis Gordan

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 à $\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 $f_{j}$ est la forme nulle s'en déduit sans aucune difficulté. On supposera dès lors toutes les $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 :

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

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

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

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

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

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

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

pour tout $y$ de $H$, $\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 $H=\mathrm {Ker} \,f_{2}$ sont exactement les multiples de $f_{2}$. Il existe donc un réel $\nu$ tel que :

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

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

• • Si $\nu >0$, on récupère la relation en attente $f_{2}+\cdots +f_{p}=0$ et on termine en écrivant : $\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é.

Le lemme de Farkas entraîne le théorème de Motzkin

Bien que le théorème de Motzkin semble plus général que celui de Farkas, il s'en déduit en quelques lignes, comme suit :

On note, pour des indices variant de $1$ à $p$ :

${\begin{matrix}C_{1}&=&\{y\in E\,\mid \,f_{1}(y)>0,&f_{2}(y)\geq 0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)\geq 0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\C_{2}&=&\{y\in E\,\mid \,f_{1}(y)\geq 0,&f_{2}(y)>0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)\geq 0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\\vdots &&&&\vdots &&\vdots \\C_{p}&=&\{y\in E\,\mid \,f_{1}(y)\geq 0,&f_{2}(y)\geq 0,&f_{3}(y)\geq 0,\ldots ,&f_{p}(y)>0,&f_{p+1}(y)\geq 0,\ldots ,f_{k}(y)\geq 0\}\\\end{matrix}}$

On remarque que si on prend $y_{1}$ dans $C_{1}$, $y_{2}$ dans $C_{2}$, $\ldots$, $y_{p}$ dans $C_{p}$, leur somme est dans l'ensemble des solutions du système traité par le théorème de Motzkin. Si celui-ci est vide, c'est donc que l'un des $C_{j}$ est vide. Mais on peut alors appliquer le lemme de Farkas à ce $C_{j}$ et il fournit bien un $k$-uplet $(\lambda _{1},\ldots ,\lambda _{k})$ qui répond aux conditions du théorème de Motzkin (en utilisant $\lambda _{j}\not =0$).

Comme dans tous les théorèmes rassemblés ici, l'implication montante est une évidence.

Extension à des systèmes d'inéquations affines

Une fois connus ces théorèmes, on peut en déduire en tant que de besoin des énoncés pour des systèmes affines, c'est-à-dire où les inéquations n'auraient pas la forme $f_{j}(y)\geq 0$ mais $f_{j}(y)\geq c_{j}$ pour des constantes $c_{j}$. La démarche est explicitée à l'article Lemme de Farkas auquel on renvoie : elle consiste à considérer l'espace affine de référence comme hyperplan affine d'équation $g(y)=1$ dans un espace vectoriel ${\hat {E}}$. La consistance d'un système affine dans $E$ se ramène alors à la consistance d'un système analogue dans ${\hat {E}}$ mais auquel on a ajouté la condition supplémentaire $g(y)>0$. Ainsi un système d'inéquations affines larges est-il traité par le lemme de Farkas, tandis qu'un système d'inéquations affines dont une et une seule est stricte se traite-t-il comme un système linéaire couvert par Motzkin avec $p=2$ (c'est l'énoncé intitulé « lemme de Farkas généralisé » dans l'article lemme de Farkas).

Les théorèmes de l'alternative : point de vue matriciel

Pour $B$ matrice réelle, la notation $B\geq 0$ signifie que tous les termes de $B$ sont positifs ou nuls, la notation $B>0$ que tous les termes de $B$ sont strictement positifs. Enfin on note $B^{T}$ la transposée de la matrice $B$.

Traductions matricielles des énoncés déjà donnés

Commençons par la version matricielle du lemme de Farkas, puisque c'est le théorème le plus notable. Elle s'obtient sans aucune subtilité à partir de la version donnée plus haut, la seule difficulté étant de bien rapprocher les notations de l'une et de l'autre.

Lemme de Farkas, version matricielle — Soit $A$ une matrice de réels de type $(n,k)$ et $b$ un vecteur-colonne avec $n$ entrées, alors un et un seul des systèmes linéaires suivants a une solution :

• le système $Ax=b\,$ pour $x$ vecteur-colonne à $k$ entrées vérifiant par ailleurs $x\geq 0$ ;
• le système $A^{T}y\geq 0$ pour $y\,$ vecteur-colonne à $n$ entrées vérifiant par ailleurs $b^{T}y<0\,$.

Vérification

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 $C_{j}$ de $A$ ($1\leq j\leq k$), notons $f_{j}$ la forme linéaire définie sur $\mathbb {R} ^{n}$ par $y\mapsto C_{j}^{T}y$ ; notons par ailleurs $g$ la forme linéaire $y\mapsto b^{T}y$.

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

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

On écrit de même des versions matricielles pour les théorèmes de Gordan et de Stiemke, dont la vérification est du même esprit.

Théorème de Gordan, version matricielle — Soit $A$ une matrice de réels de type $(n,k)$. Alors un et un seul des systèmes linéaires suivants a une solution :

• le système $Ax=0\,$ pour $x$ vecteur-colonne à $k$ entrées vérifiant par ailleurs $x\geq 0$ et $x\not =0$ ;
• le système $A^{T}y>0$ pour $y\,$ vecteur-colonne à $n$ entrées.

Théorème de Stiemke, version matricielle — Soit $A$ une matrice de réels de type $(n,k)$ et $b$ un vecteur-colonne avec $n$ entrées, alors un et un seul des systèmes linéaires suivants a une solution :

• le système $Ax=0\,$ pour $x$ vecteur-colonne à $k$ entrées vérifiant par ailleurs $x>0$ ;
• le système $A^{T}y\geq 0$ et $A^{T}y\not =0$ pour $y\,$ vecteur-colonne à $n$ entrées.

Le théorème de Ville

Ce théorème, qui se déduit en quelques lignes du théorème de Gordan dès lors qu'on manipule les notations matricielles, a un énoncé très agréablement symétrique sous cette forme ; on peut bien sûr le réécrire en termes de conditions nécessaire et suffisante d'existence de solutions de systèmes d'inéquations, son charme étant qu'on peut le faire de deux façons selon l'ordre dans lequel on considère les deux branches de l'alternative : au choix on peut y voir une condition nécessaire et suffisante d'existence de solutions en nombres positifs ou nuls pour un système d'inégalités linéaires larges, ou d'existence de solutions en nombres strictement positifs pour un système d'inégalités linéaires strictes.

Théorème de Ville (1938) — Soit $A$ une matrice de réels de type $(n,k)$. Alors un et un seul des systèmes linéaires suivants a une solution :

• le système $Ax\leq 0$ pour $x\,$ vecteur-colonne à $k$ entrées vérifiant par ailleurs $x\geq 0$ et $x\not =0$ ;
• ou le système $A^{T}y>0\,$ pour $y$ vecteur-colonne à $n$ entrées vérifiant par ailleurs $y>0$.

Démonstration

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

La deuxième branche est immédiate : $M^{T}y>0$ est directement équivalent à $A^{T}y>0$ et $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 $z$ tel que $Mz=0$ avec $z\geq 0$ et $z\not =0$ revient, en appelant $x$ le vecteur-colonne regroupant les $k$ premières composantes de $z$ et $v$ celui regroupant les $n$ dernières, à l'existence de $(x,v)$ avec :

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

Ce système équivaut immédiatement à :

$Ax+v=0$, $x\geq 0$, $v\geq 0$ et $x\not =0$ (il ne peut avoir de solution avec $x=0$ mais $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 $x$ :

$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é.

Références

Sauf précisions plus spécifiques, les informations fournies par cet article sont issues, sur un mode assez distancié, des pages 51 et suivantes de Linear Programming 2: Theory and Extensions, de George Dantzig et Mukund Thapa, Springer, 2003 (ISBN 978-0387986135).

La démonstration du lemme de Farkas via le théorème de Gordan est issue de Convex Analysis and Nonlinear Optimization, Theory and Examples de Jonathan M. Borwein et Adrian S. Lewis, coll. « Ouvrages de mathématiques de la Société mathématique du Canada », vol. 3, 2^e édition, Springer, 2006 (ISBN 978-0387989402), p. 24-25.