somme de vecteur dans Z/2Z

[invitea0ece8ff]

Bonjour, voila mon problème:

Je dispose de N vecteur de taille N, a coeficient dans Z/2Z
V1=[1 0 1 1 0 1...]
V2=[1 0 1 0 0 1...]
...

Je souhaiterai resoudre cette équation a N inconnue:
(a,b,c...)€(Z/2Z)^N
a*V1+b*V2+c*V3+...=[0 0 0 0 0 0...]

J'avait commencer a programmer une fonction qui permettai de resoudre le problème en scilab, mais le nombre de cas particuliers sur lequel je tombai m'on montré que je mit prenai surement pas de la bonne manière.

Donc voila, comment résoudre ce systeme d'équation en scilab ?
Merci d'avance.
-----

[invitea0ece8ff]

Je précise que je cherche une solution ou au moin un des (a,b,c...) vaut 1.

[invitea0ece8ff]

Re, il n'y a pas beaucoup de réponse, dite moi si jamais quelque chose n'est pas clair.

[lapin savant]

Bonsoir,
par simple curiosité, ta question est-elle liée à la recherche de la distance minimale d'un code correcteur ?

[A voir en vidéo sur Futura]

[invitea0ece8ff]

Bonsoir,
par simple curiosité, ta question est-elle liée à la recherche de la distance minimale d'un code correcteur ?

Non, c'est pour implémenter la "factorisation de dixion".
J'avait pas pensé que cette étape poserai une difficultée, mais j'suis presque sur qu'il y a quelque chose que je voie pas.

[invite7cf0b55f]

c'est un systeme lineaire de N équations à N inconnues, ce qui est nouveau est le corps ici Z/2Z, calcul la matrice, calcul le determinant etc..

[sylvainc2]

Si tu places les V1,V2... dans les colonnes d'une matrice A, alors tu cherches un vecteur u=(a,b,c...) tel que Au=0 c.a.d. u dans ker(A). Comme le pivot de Gauss marche dans n'importe lequel corps, et que Z/2Z est un corps, ca ne devrait pas poser de problème.

[invitea0ece8ff]

Si tu places les V1,V2... dans les colonnes d'une matrice A, alors tu cherches un vecteur u=(a,b,c...) tel que Au=0 c.a.d. u dans ker(A). Comme le pivot de Gauss marche dans n'importe lequel corps, et que Z/2Z est un corps, ca ne devrait pas poser de problème.

Enfaite, c'est avec le pivot de gauss que j'me galérai un peut.

Par exemple pour resoudre ça:

[1 1 0 0 1]
[1 0 0 1 1]
[1 1 1 0 0]
[0 1 0 1 0]
[1 1 1 0 0]

(chaque ligne correspond a un de mes vecteurs)

J'commence par ajouter la premiere ligne a celle d'en dessous quand elle contiennent un 1 sur la premiere colone:

[1 1 0 0 1]
[0 1 0 1 0]+l1
[0 0 1 0 1]+l1
[0 1 0 1 0]
[0 0 1 0 1]+l1

Ensuite je recommence avec la 2émé ligne et la 2ème colone:

[1 1 0 0 1]
[0 1 0 1 0]+l1
[0 0 1 0 1]+l1
[0 0 0 0 0]+l1+l2
[0 0 1 0 1]+l1

(Bon déjà la j'ai une solution (l1+l2+l4=0) est se que ça peut etre favorable dans l'algoritme de vérifier a chaque etape j'ai pas deja trouver une solution ?)

Ensuite si jamais je me retrouve avec un 0 au mauvaise endroi:
ex:
[0 1 0 0 1]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 1 1 0]
[1 0 1 0 1]

La j'peut pas commencer par éliminer la premiere colone de 1, vu que ma premiere ligne a 0 sur cette colone.
L'autre problème c'est qu'il faut que j'élimine ma derniere ligne, vu que je sait que je pourrai pas éliminé le 1 de sa premiere colone.

Enfin voila, j'me retrouve a programmer quelque chose de compliqué, alors que pourtant le problème me semble simple.

[invitea0ece8ff]

c'est un systeme lineaire de N équations à N inconnues, ce qui est nouveau est le corps ici Z/2Z, calcul la matrice, calcul le determinant etc..

Désolé, je sait pas calculer le determinant, ni quoi en faire apres.

[invite7cf0b55f]

la méthode ne fonctionne pas , par contre as tu essayé cela :
http://www.math-linux.com/spip.php?article37

[sylvainc2]

Si tu te retouves avec un élément pivot à zéro, alors tu peux faire une permutation de 2 lignes, dans ton exemple, ce sont les lignes 1 et la dernière, et tu procèdes ensuite comme avant.

Si tu peux pas faire de permutation pour éliminer le pivot à zéro c'est que les lignes sont liées.

[invitea0ece8ff]

Ok, merci de vos aides, j'vait regarder ça de plus pret.