polynome minimal d'une matrice

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

Modérateur : xcasadmin

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

polynome minimal d'une matrice

Message par Denizou » mar. mai 21, 2013 1:01 pm

Bonjour,

j'ai écrit un algorithme naïf permettant de déterminer le polynôme minimal d'une matrice. L'idée est de résoudre les n^2 équations à k-1 inconnues suivantes : X[0]*A^0+X[1]*A^1+...+X[k-1]*A^{k-1}+A^k en faisant varier k entre 1 et n^2.
Je teste mon programme sur I_2 qui me renvoie -1+x, lorsque je le teste sur des matrices aléatoires de dimension 4, le programme marche et donne bien le polynôme minimal.
Mais, lorsque je le teste avec I_4 ou I_5 Xcas s'arrête net au moment de résoudre le système d'équations...
Pourquoi ?
En testant avec des matrices creuse, le programme fonctionne correctement. Que se passe - t - il avec l'identité de dimension supérieure à 3 ?

Merci

François

Mon programme :

Code : Tout sélectionner

polmin(A):={
  local n,s,X,k,Q,j,Eq,l,Inc,P;
  n:=rowdim(A);
  while((s==0) or (size(s)==0)  ) 
    {
      purge(X);
      k:=k+1;
      Q:=eval(add(X[j]*A^j,j=0..k-1)+A^k);
      Eq:=eval(seq(seq(Q[j,l],j=0..n-1),l=0..n-1));
      Eq:=[Eq];
      Inc:=[seq(X[j],j=0..k-1)];
      s:=linsolve(Eq,Inc);
      }
  P:=add(s[j]*x^j,j=0..k-1)+x^k;
  
  return P;
}:;

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

Re: polynome minimal d'une matrice

Message par parisse » mar. mai 21, 2013 2:52 pm

Il y a un bug dans solve.cc, un while (li[j]==0 && j<d) qui devrait être while (j<d && li[j]==0), je vais le corriger. Vous pouvez eviter ce bug en codant directement la matrice du système dans votre programme (et en transformant la recherche du polynome minimal en la recherche du noyau de cette matrice, dès que la dimension est 1 vous avez votre polynome minimal). Notez aussi que votre méthode naive est couteuse puisque vous avez n^2 équations, et que vous résolvez pour 1 puis 2 puis 3 etc. inconnues, ça doit être en O(n^5) sur un corps fini.

Denizou
Messages : 61
Inscription : mer. juin 13, 2012 7:23 am

Re: polynome minimal d'une matrice

Message par Denizou » mer. mai 22, 2013 3:09 pm

Merci beaucoup pour toutes ces informations. Il faut vraiment que je prenne l'habitude de résoudre des systèmes avec le noyau de la matrice effectivement. Quant à la validité de l'algorithme sur des grandes dimensions, je ne doute pas qu'il explose !
François

Répondre