Diagonalisation de matrice dans corps finis

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

Répondre
Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Diagonalisation de matrice dans corps finis

Message par Francky la Hache » lun. mars 04, 2013 6:13 pm

Bonjour,

J'ai essayé de diagonaliser une matrice aléatoires (18×18) d'éléments dans Fp, où p est premier sur 29bits.
J'ai utilisé la commande jordan.
J'ai dû tuer la tâche, XCAS venait d'engloutir plus de 7Go de RAM. ( xcas 0.9.8, linux64)

Existe-t-il un moyen 'simple' d'obtenir , P,D,P⁻¹ ?

(J'ai réussi à me coder un petit programme qui m'a donné le polynôme minimal, et XCAS avait réussi à me le donner dans Z très vite. La réduction dans Fp a confirmé mon calcul.)


Merci d'avance pour toute information utile.

Edit : idem avec une matrice 6×6, mais pas avec une matrice 2×2.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par frederic han » lun. mars 04, 2013 8:25 pm

Bonjour,
(Je prend un exemple plus petit car GF rame vite, (ca me semble vite trop complique pour rat jordan))

a priori une matrice aleatoire n'aura pas un polynome minimal scinde sur Fp, il vous faudra donc


Ex:

Code : Tout sélectionner

A:=[[(-2) % 5,1 % 5,2 % 5,(-2) % 5,1 % 5,2 % 5],[0 % 5,(-1) % 5,1 % 5,(-2) % 5,(-1) % 5,2 % 5],[(-1) % 5,(-2) % 5,(-2) % 5,(-2) % 5,1 % 5,0 % 5],[0 % 5,1 % 5,1 % 5,(-2) % 5,2 % 5,0 % 5],[2 % 5,2 % 5,(-2) % 5,0 % 5,(-2) % 5,0 % 5],[(-1) % 5,1 % 5,0 % 5,2 % 5,0 % 5,(-1) % 5]];
p:=(pmin(A,x));
factors(p);
1) le factoriser sur fp
dans mon exemple factors(p) donne:
[(1 % 5)*x-1 % 5,1,(1 % 5)*x^2+(-1 % 5)*x+2 % 5,1,(1 % 5)*x^3+(2 % 5)*x^2+(2 % 5)*x-2 % 5,1]

2) prendre une extension de corps avec GF pour que ca devienne scinde
alors:

Code : Tout sélectionner

K:=GF(5,6);
B:= K(A % 0); 
factor(pmin(B,x));
l:=solve(pmin(B,x));
3) regarder les espaces propres avec ker:

ensuite on a du mal a faire la matrice diagonale l[0] car l[0]*idn(6) ne marche pas.

donc:

Code : Tout sélectionner

ker(B-(diag(l[0]$6)))
qui me donne le premier vecteur propre:

Code : Tout sélectionner

[[-l^5+l^4-l^3-l^2+2*l,-2*l^5-l^4-2*l^3+l^2+2*l-2,l^5-l^4+l^3+l^2-2*l-2,2*l^4-2*l^2-2*l-2,-l^5+2*l^4-l^3-2*l^2+l+1,-1]]
et ainsi de suite avec les autres l[j]

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Re: Diagonalisation de matrice dans corps finis

Message par Francky la Hache » lun. mars 04, 2013 8:44 pm

Attention p est sur 29bit : donc bien plus grand que 5, et ça change tout.
Je n'ai aucun problème avec p=5.

Sinon, (avec 18×18 aléatoire, et p premier sur 29bit) je parie ma chemise que le polynôme est scindé.


Peut-on éviter GF, et travailler plus rapidement avec Z/pZ ?
Merci.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par frederic han » lun. mars 04, 2013 9:42 pm

Bof,
Les polynomes unitaires scindes sont en bijection avec les tirages des racines avec remise donc en degre 18 il y en a
binomial(p+18-1,18) contre p**18 poly unitaires de degre 18, ca me semble etre de l'ordre de 10^(-92)
si
p:=nextprime(2**29)

OK?


Vous serez donc oblige de faire une extention de corps. Ex si vous tombez sur un facteur de degre 10*un facteur de degre 8 alors il faudra monter dans F_(p^80) ce qui sera trop gros pour GF car c'est le point faible d'xcas.

pari()
ffinit(p,80,r) fonctionne sans Pb.
il faudra alors trouver les instructions correspondantes sous pari. (Cf le menu Aide> Manuel > Pari-GP)

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par parisse » mar. mars 05, 2013 12:45 pm

Bon, il y avait une gros probleme dans une initialisation dans le test d'irreductibilite du polynome minimal pour des premiers p grands, je le corrige. J'ajoute aussi la possibilite de ne pas renvoyer un polynome primitif (ajout d'un 0 en 3eme argument). Ca restera quand meme beaucoup plus lent que pari qui utilise un algorithme beaucoup plus rapide (du moins tant que j'en reste a l'algo actuel...).

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Re: Diagonalisation de matrice dans corps finis

Message par Francky la Hache » mar. mars 05, 2013 2:01 pm

Merci pour la réponse, j'espère avoir été utile si j'ai soulevé un point utile.

Juste pour info, s'il vous plaît, c'est quoi l'instruction sous gp/PARI, pour avoir la décomposition de Jordan ? :oops:
Je sais déjà entrer une matrice en mode Z/pZ.

Je connais mal, et me bats un peu avec ces heures-ci, merci d'avance.

Voici un exemple en 6×6 qui m'envoie une insulte avec gp (version 2.5.0 de mes dépôts)

Code : Tout sélectionner

p = 1000000007
M = [0,2,0,0,0,0 ; 1,0,1,1,0,0 ; 0,1,1,0,1,0 ; 0,2,0,0,2,0 ; 0,0,1,1,1,1 ; 0,0,0,0,2,2]
M= Mod(M, p)
mateigen(M)
Voici l'insulte :

Code : Tout sélectionner

  ***   at top-level: mateigen(M)
  ***                 ^-----------
  *** mateigen: invalid coefficients in roots.
  ***   Break loop: type 'break' to go back to GP
==============
Edit :
Pour l'exemple 6×6 : j'ai réussi à "bourriner", en itérant sur Fp à trouver les valeurs propres (j'avais déjà eu facilement le polynôme minimal), j'ai trouvé 6 valeurs propres distinctes, et ensuite cela m'a permis de trouver les vecteurs propres associés.
J'ai donc pu avoir D et P.
J'ai obtenu P⁻¹, en faisant P puissance ordre du groupe linéaire. -> Réussite partielle.

Mais, J'ai essayé de bourriner avec deux matrices aléatoires 18×18, donc j'avais le pmin, mais je n'ai trouvé aucune racine pour pmin dans Fp dans les deux cas.
Il semblerait que j'ai perdu ma chemise dans mon pari d'un post précédent... :-(

Sinon, j'ai fait des tests avec GAP, qui m'a rapidement insulté, il lui fallait un paquet supplémentaire pour la factorisation de grands entiers (Rho-Pollard ne lui suffisait plus), j'ai installé le dit-package, relancer GAP, mais ensuite, il m'a dit en substance : "T'as perdu!"

Je veux bien toujours une aide pour (tenter)-faire ça avec gp/PARI.
Merci encore, d'avance.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par parisse » mer. mars 06, 2013 2:10 pm

Je viens d'updater les packages linux 1.1 testing, avec appel de pari pour generer le poly irreductible si on ajoute 0 en 3eme parametre de GF, par exemple p:=nextprime(2^29); GF(p,80,0). Mais le polynome n'est alors pas primitif en general.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par frederic han » mer. mars 06, 2013 2:58 pm

On a vite des ennuis meme sans cette option:

est ce normal?

Code : Tout sélectionner

restart;
p:=nextprime(2**4);
K:=GF(p,6);
solve(x^6+x+7 % p);//pas de solutions donc c'est bien irred

solve(x^6+x+K(7));// OK il est donc bien scinde sur K 
restart;
p:=nextprime(2**5);
K:=GF(p,6);
solve((x^6+x-3) % p); // il ne trouve rien donc ce poly est bien irred 
solve(x^6+x-K(3)); // donc il devrait etre scinde sur K mais ca tourne fou.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par parisse » mer. mars 06, 2013 5:18 pm

attention solve n'est pas équivalent à factor, s'il n'y a pas de solutions ce n'est pas pour autant irréductible, dans ton 2ème exemple la factorisation donne un poly de degré 2 et un de degré 4.
Mais il y a bien un bug dans cantor-zassenhauss, une conversion en int malencontreuse puisque le cardinal de ton corps est > 2^31.

Code : Tout sélectionner

diff modfactor.cc modfactor.cc~
354c354
<       pp=powmod(pp,(env->pn-1)/2,ddfactor,env);
---
>       pp=powmod(pp,(env->pn.val-1)/2,ddfactor,env);
et il faudra que je modifie la racine carrée pour marcher aussi dans des corps fini de cardinal >= 2^31.

frederic han
Messages : 1137
Inscription : dim. mai 20, 2007 7:09 am
Localisation : Paris
Contact :

Re: Diagonalisation de matrice dans corps finis

Message par frederic han » mer. mars 06, 2013 6:36 pm

oui la honte! :mrgreen:
(En plus j'avais modifie le premier exemple justement pour ce pb et je n'ai pas verifie celui qui tournait fou).

Répondre