Explication du texte

Bouteille à la mer

Suite à une question je laisse une explicaiion de la partie centrale de l'algo donné en bas.

L’idée est de résoudre sur les réels un système de la forme Li*Mi=0 pour i=1…….p et ou les Li et Mi sont des équations linéaires homogènes qui portent sur N variables .

Je vais nommer S le système quadratique vu en haut dans la suite.

Pour chaque i=1….p Li et Mi sont dits complémentaires dans S.

D’abord un rappel : Dans un système linéaire homogène à N variables (MX=0 sous forme matricielle ) il y a

deux cas possibles

Rang(M) =N et le système à une solution triviale Xi=0 pour i=1….N

Rang(M)<N et on a plusieurs solutions.

Pour S on cherche aussi une solution non triviale.

Si p<N on a une solution non triviale, on prend p équations L ou M ou un mélange (une de chaque paire) et on résout par un pivot de Gauss par exemple. Cela fonctionne car il suffit que l’une de deux soit nulle dans Mi*Li=0 .

Si p>=N on fabrique un nouveau système MX=0 où M est la concaténation de Mi et Li.

On a ici rang(M)<= N <=p et M a 2p lignes et N colonnes.

Je pense que le début est évident et c’est le cas p>=N qui est difficile et qu’on doit analyser.

On va supposer pour la suite que pour chaque i=1…p Mi et Li sont indépendants, en effet si ce n’est pas le cas alors Mi=a*Li avec a réel.

Mi*Li=0 ssi Li=0

On peut alors résoudre xN en fonction des X1….XN-1 et le système S est réduit à un système à p-1 équations et à N-1 inconnues.

On va appeler une collection complète une suite d’équations qui « traverse » S (pour chaque i on prend Mi ou Li)

Par exemple si p=3 (L1,L2,L3 ) , (M1,M2,M3) et (M,,L2,M3) sont des collections complètes.

On revient à M produite par les Li et Mi .

Si rang(M)=m <N , on a dans les lignes de M 2p-m lignes qui sont des combinaisons linéaires des m autres et m<N , il suffit alors de résoudre le sous-système de m équations qui a une solution non triviale.

Si rang(M)=N, S à une solution si il contient une collection complète de rang <N . Cela revient à dire que l’espace vectoriel engendré par la collection en question (en transposant les lignes) est de dimension < N.

Si S contient une collection de rang < N on peut la compléter pour en faire une collection complète de rang N-1 (on ajoute des lignes qui sont dans la base de l’espace vectoriel généré par toutes les lignes L1…Lp et M1….Mp).

On va appeler cet espace vectoriel F et le sous espace génère par la collection complète H. dim(F)=N et dim(H)=N-1.

Quitte à permuter deux éléments de la collection complète on peut trouver une base de F composée d’une base de H et du complémentaire de l’un de ses membres( ceux de la base).

Pour trouver une collection complète de rang =N-1 et en déduire une solution non triviale de S on va appliquer ce qui suit :

1) Pour chaque i=1 …p construire une base de F contenant Li et Mi. B = ( Li, Mi , V1……VN-2)

2) Prendre le sous espace H de base (Li, V1…VN-2) et vérifier si pour chacune des lignes de S au moins l’un de deux vecteurs Lj ou Mj est dans H , si ok on a une solution sinon on passe à 3

3).Prendre le sous espace H de base (Mi, V1…VN-2) et vérifier si pour chacune des lignes de S au moins l’un de deux vecteurs Lj ou Mj est dans H , si ok on a une solution sinon on passe à 4)

4).I++ et retour à 1).

Si aucun i ne permet de former une collection complète de rang=N-1 alors S n’a pas de solution non triviale.

Update

Pour les points 2 et 3 la vérification que Mj ou Lj est dans H se fait par la résolution d’un système linéaire.

Update 6/10/2026

Dans cet essai, on se propose d’étudier un problème posé sur l’ensemble des nombres réels. Il s’agit de résoudre le système quadratique suivant :

Pour i=1,…,p,

Li(x) Mi(x)=0,

où x est un vecteur de N variables, et où Li(x) et Mi(x) sont deux équations linéaires homogènes.

L’objectif est de déterminer si ce système admet une solution autre que la solution triviale (le vecteur nul).

Les équations Li=0 et Mi=0 étant homogènes, on peut les écrire sous la forme

Li⋅X=0,Mi⋅X=0,

où Li et Mi sont deux vecteurs de dimension N.

Comme indiqué dans le message précédent (« une bouteille à la mer »), on sait résoudre les deux cas simples suivants :

1) Si N>p, une solution existe.

2) Si l’espace vectoriel H=⟨L1,…,Lp,M1,…,Mp⟩ est de dimension strictement inférieure à N, alors une solution existe également.

Dans la suite, on se place dans le cas où dim⁡(H)=N et N<p.

Introduction de nouvelles équations

On considère maintenant 2p nouvelles équations homogènes Pi et Qi pour i=1,…,p, où chaque Pi et Qi dépend des N variables de X ainsi que de M nouvelles variables, avec la condition :

N+M>(2p+1) p.

Les vecteurs Pi et Qi sont choisis indépendants.

Une équation Li(x)Mi(x)=0 admet une solution si et seulement si le système suivant en admet une également :

LiPi+MiQi=0,PiQi=0,Pi+Qi=1,

ou, de manière équivalente,

LiPi+Mi(1−Pi)=0,Pi(1−Pi)=0.

Ce nouveau système, constitué de 2p équations portant sur N+M variables, est sous-déterminé.

Méthode envisagée

On va le résoudre en adaptant la méthode utilisée pour les corps finis : un changement de variables permettant d’annuler les premiers monômes xixj des équations.

On utilise la méthode présentée dans le paragraphe 7 de l’article indiqué dans le lien Quadratic (5.76 Mo)

Après le changement de variables, on obtient un nouveau système (S) portant sur les carrés des nouvelles variables yiyi. Contrairement à l’article, ici on travaille sur les nombres réels, et pour pouvoir revenir aux variables d’origine, il est nécessaire de garantir l’existence de solutions toutes positives.