Théorèmes de l'alternative - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

- Introduction - Systèmes d'inéquations strictes et systèmes d'inéquations larges : les théorèmes de Gordon et de Stiemke - Les théorèmes de l'alternative : point de vue matriciel - Systèmes mêlant inéquations strictes et larges : le lemme de Farkas et le théorème de Motzkin

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$ ;

ou le système $A^Ty \geq 0$ pour $y\,$ vecteur-colonne à $n$ entrées vérifiant par ailleurs $b^Ty < 0\,$ .

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 $\R^n$ par $y\mapsto C_j^T y$ ; notons par ailleurs $g$ la forme linéaire $y\mapsto b^Ty$ .

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_1C_1+\cdots+x_kC_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$ ;

ou 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$ ;

ou le système $A^Ty \geq 0$ et $A^Ty \not= 0$ pour $y\,$ vecteur-colonne à $n$ entrées.

Le théorème de Ville

Ce théorème de Jean Ville, 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^Ty > 0\,$ pour $y$ vecteur-colonne à $n$ entrées vérifiant par ailleurs $y > 0$ .

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 $M z = 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 :

A x + v = 0

Ce système équivaut immédiatement à :

A x + v = 0

(il ne peut avoir de solution avec

x = 0

mais

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$ :

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

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

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

👽 Découvrir enfin une vie extraterrestre

🎯 Une piste très prometteuse pour empêcher les rechutes du cancer du sein

✨ Pourquoi les étoiles paraissent plus brillantes l'été ?

🌱 Comment les plantes résistent-elles à une lumière trop intense ?

⚫ Une IA révèle que le trou noir supermassif de notre galaxie pointe vers la Terre

🏔️ Découverte d'un monde perdu sous l'Antarctique

🌍 Découverte: cette règle universelle régit toute vie sur terre

⏳ L'Univers pourrait disparaître plus tôt que prévu: ce que révèle cette étude

🌍 Les dernières mesures révèlent un niveau de CO₂ jamais vu depuis 4 millions d'années

🛡️ Le paradoxe des gangs de rue

💰 Quelle quantité d'or existe-t-il vraiment sur Terre ?

🦟 Pourquoi les moustiques sont plus nombreux et piquent davantage en été ?

⚫ Ces trous noirs interagissent avec la lumière fossile du Big Bang

🦕 Et si les dinosaures détenaient le secret pour vaincre le cancer ?

😎 Comment font les lunettes de soleil pour filtrer les UV ?

🚶‍♂️‍➡️ La marche des babouins éclaire l'évolution de la bipédie humaine

🔭 James Webb capture cette image directe d'une étrange planète à 60 années-lumière

🦋 Pourquoi et comment les chenilles deviennent-elles des papillons ?

🔭 Voici la plus grande carte de l'Univers. Ses révélations sont surprenantes !

😴 Penser que l'on est éveillé alors que l'on dort, normal ?

🌊 Ce cratère raconte l'histoire de l'eau sur Mars

🐝 Comment les fleurs attirent-elles les insectes pollinisateurs ?

💥 La collision entre notre Voie lactée et la galaxie d'Andromède remise en question

🎶 Pourquoi les oiseaux chantent-ils autant et si fort au printemps ?

💡 Générer de la lumière à partir du vide, c'est possible

Découverte d'un deuxième système d'apprentissage dans le cerveau

☀️ Comment se produit un coup de chaleur et comment s'en protéger ?

⚽ Comment fonctionne la physique d'un tir puissant au foot ?

🧠 Un algorithme révèle comment notre cerveau se motive

🔭 Une si grande planète orbite une si petite étoile, comment est-ce possible ?

🐋 Les baleines développent de nouvelles méthodes pour communiquer avec nous

🥚 Le noyau de Mars sent l'œuf pourri

🧠 On sait enfin pourquoi le sémaglutide fait maigrir

🌱 La vie pourrait renaître sur Europe après la mort de la Terre

🌿 Confirmation scientifique: ce remède ancestral fait naturellement maigrir, et pas qu'un peu !

💥 Des astronomes identifient les plus puissantes explosions depuis le Big Bang

🦕 Ce crâne de stégosaure, le plus complet jamais découvert, réécrit l'histoire

🛏️ Les punaises de lit, ces compagnons indésirables depuis la préhistoire

🕸️ Connaissez-vous la toile cosmique, l'architecte de l'Univers ?

🌋 L'éruption de l'Etna vue depuis l'espace

🐋 Il y a 20 000 ans, l'Homme fabriquait des outils avec des os de baleines

🟠 Quel est le rôle de ce labyrinthe sur Mars ?

🎯 Cette stratégie innovante contre le cancer du sein offre une survie de 100%

💥 Le pulsar à trou noir: un objet qui intrigue les astrophysiciens

🐒 Première: ces singes kidnappent les bébés d'une autre espèce

🌍 Découverte d'une super-Terre à l'habitabilité intermittente

🧠 Ces cellules pourraient jouer un rôle bien plus important que les neurones dans la mémoire

🛰️ Une carte photographique de la Terre toutes les 35 minutes

Pourquoi l'oxygène est-il si indispensable à autant d'êtres vivants ?

🐱 Pourquoi certains chats miaulent et ronronnent plus que d'autres ?

Page générée en 0.104 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales
Version anglaise | Version allemande | Version espagnole | Version portugaise