Explication du texte

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

Rand(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 :

Pour chaque i=1 …p construire une base de F contenant Li et Mi. B = ( Li, Mi , V1……VN-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).

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

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.

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.