Diagonalisation de matrice dans corps finis
Modérateur : xcasadmin
-
- Messages : 11
- Inscription : lun. avr. 05, 2010 4:40 pm
Diagonalisation de matrice dans corps finis
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.
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.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Re: Diagonalisation de matrice dans corps finis
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:
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:
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:
qui me donne le premier vecteur propre:
et ainsi de suite avec les autres l[j]
(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);
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));
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)))
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]]
-
- Messages : 11
- Inscription : lun. avr. 05, 2010 4:40 pm
Re: Diagonalisation de matrice dans corps finis
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.
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.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Re: Diagonalisation de matrice dans corps finis
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)
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)
Re: Diagonalisation de matrice dans corps finis
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...).
-
- Messages : 11
- Inscription : lun. avr. 05, 2010 4:40 pm
Re: Diagonalisation de matrice dans corps finis
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 ?
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)
Voici l'insulte :
==============
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.
Juste pour info, s'il vous plaît, c'est quoi l'instruction sous gp/PARI, pour avoir la décomposition de Jordan ?
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)
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.
Re: Diagonalisation de matrice dans corps finis
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.
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Re: Diagonalisation de matrice dans corps finis
On a vite des ennuis meme sans cette option:
est ce normal?
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.
Re: Diagonalisation de matrice dans corps finis
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.
et il faudra que je modifie la racine carrée pour marcher aussi dans des corps fini de cardinal >= 2^31.
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);
-
- Messages : 1137
- Inscription : dim. mai 20, 2007 7:09 am
- Localisation : Paris
- Contact :
Re: Diagonalisation de matrice dans corps finis
oui la honte!
(En plus j'avais modifie le premier exemple justement pour ce pb et je n'ai pas verifie celui qui tournait fou).
(En plus j'avais modifie le premier exemple justement pour ce pb et je n'ai pas verifie celui qui tournait fou).