Polynôme minimal d'un endomorphisme

Dans la théorie sur la réduction des endomorphismes, on utilise deux polynômes particuliers, le polynôme caractéristique et le polynôme minimal. Le prolynôme caractéristique est simple (mais long en grandes dimensions) à calculer puisque c'est juste un déterminant. Pour le factoriser et déterminer ses racines, c'est une autre histoire.

Le polynôme minimal, par contre, on peut montrer qu'il existe, mais je n'ai jamais appris de méthode "universelle" pour le déterminer explicitement.

En bouquinant, comme je fais souvent, sur Wikipédia, je suis (re)tombé sur ça. J'étais arrivé dessus en étant parti des endomorphismes semi-simples ou irréductibles. Et pour qu'un endomorphisme $u$ soit irréductible, en dimension finie, il faut qu'il soit cyclique. L'article dont je viens de donner le lien donne quatre caractérisations de ça.

1) Le degré du polynôme minimal est égal à la dimension de l'espace
et
2) Le polynôme minimal est égal au polynôme caractéristique
Pour ces deux-là, il faut soit réussir à déterminer le polynôme minimal, soit réussir à factoriser le polynôme caractéristique et espérer s'en sortir avec ça (d'où le problème de la factorisation), soit... je ne sais pas.

3) Les seuls endomorphismes qui commutent avec $u$ sont exactement les polynômes en $u$
Je ne saurais même pas comment on vérifie ça en pratique.

4) il existe une base de E dans laquelle la matrice de u est une matrice compagnon.
Je doute qu'il soit particulièrement simple de trouver ladite base en pratique.

A priori, j'ai plus envie de miser sur l'une des deux premières (mais libre à vous de me faire changer d'avis en me montrant comment s'en sortir avec les deux autres !), mais pour ça, je pense vraiment que dans le cas général, il faudrait trouver une méthode générale pour déterminer le polynôme minimal. Est-ce que ça existe ? En particulier, une méthode qui ne nécessite pas de réussir à factoriser le polynôme caractéristique ?

Réponses

  • Une méthode possible sans factoriser le polynôme caractéristique mais impraticable à la main : tu décomposes les $u^k$ pour $0\leq k\leq \dim(E)-1$ dans une base de $\mathcal{L}(E)$ puis tu utilises le pivot de Gauss pour déterminer le rang $r$ de la famille et une relation entre les $r+1$ premières puissances.
  • Si $A$ est une matrice carrée à coefficients dans un corps le polynôme minimal de $A$ est égal au polynôme caractéristique (unitaire) divisé par le pgcd des cofacteurs de la matrice $A-XI_{n}$
  • La remarque de michel2 me fait penser qu’il suffit de calculer les invariants de similitude de la matrice (ce qui se fait simplement). Le polynôme minimal est l'invariant de similitude de plus petit haut degré.

    Edit : Merci GaBuZoMeu!
  • Pour des matrices en basse dimension, en pratique tu calcules juste les puissances successives et tu vois quand est-ce que ça devient lié.
    Évidemment en pratique, à la main, ça devient vite intenable en grandes dimension pour des matrices "génériques"
  • MrJ a écrit:
    Le polynôme minimal est l'invariant de similitude de plus petit degré.
    Nan, de plus haut degré.
  • Oups, en effet! C’est corrigé. Merci!
  • Pour s'amuser (??) et illustrer ce que dit Maxtimax. Comparaison entre un algorithme efficace et un algorithme naïf qui consiste à chercher la première relation linéaire entre les puissances de la matrice.

    Le corps de base est ici $K = \Q$ et j'ai généré des matrices $M$ diagonales par blocs de Jordan. Est ce que c'est significatif ? Je n'en sais rien car je n'ai pas réfléchi. Peut-être que j'aurais dû y ajouter un coup de $P M P^{-1}$.
    [color=#000000]> M := Matrice([K| 1,-1], [2,3]) ;
    > M ;
    [ 1  1  0  0  0]
    [ 0  1  0  0  0]
    [ 0  0 -1  1  0]
    [ 0  0  0 -1  1]
    [ 0  0  0  0 -1]
    > time P<X> := MinimalPolynomial(M) ;
    Time: 0.000
    > P ;
    X^5 + X^4 - 2*X^3 - 2*X^2 + X + 1
    > time Q<X> := NaiveMinimalPolynomial(M) ;
    Time: 0.000
    > Q ;
    X^5 + X^4 - 2*X^3 - 2*X^2 + X + 1
    [/color]
    
    Là, c'est tellement petit, avec $1, -1$ sur la diagonale et des petits blocs que naïf ou pas naïf, c'est kif, kif.

    Je monte un peu la gomme tout en restant raisonnable.
    [color=#000000]> I := [1..5] ;
    > M := Matrice([K| Random(-1,1) : i in I], [Random(2,5) : i in I]) ;
    > M ;
    [-1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0 -1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0 -1  1  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0 -1  1  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0 -1  1  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0 -1  1  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1]
    [ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
    > NumberOfRows(M) ;
    22
    > time P<X> := MinimalPolynomial(M) ;
    Time: 0.000
    > P ;
    X^14 - 5*X^12 + 10*X^10 - 10*X^8 + 5*X^6 - X^4
    > time Q<X> := NaiveMinimalPolynomial(M) ;
    Time: 0.010
    > Q ;
    X^14 - 5*X^12 + 10*X^10 - 10*X^8 + 5*X^6 - X^4
    > P eq Q ;
    true
    [/color]
    
    Là, je monte vraiment la gomme en mettant des $0, \pm 1, \pm 2$ sur la diagonale et avec des tailles plus grandes. Evidemment, je ne montre ni la matrice ni les polynômes minimaux. On commence à sentir la différence entre du pas naïf et du naïf.
    [color=#000000]> I := [1..50] ;
    > M := Matrice([K| Random(-2,2) : i in I], [Random(5,10) : i in I]) ;
    > NumberOfRows(M) ;
    383
    > time P<X> := MinimalPolynomial(M) ;
    Time: 0.360
    > time Q<X> := NaiveMinimalPolynomial(M) ;
    Time: 18.080
    > P eq Q ;
    true
    [/color]
    
    Sans aucun doute, cela n'amuse que moi et c'est même pas sûr.
  • > Sans aucun doute, cela n'amuse que moi et c'est même pas sûr.

    Mais non, c'est intéressant de voir ce que vaut l'algorithme naïf !
  • Je ne pensais pas avoir autant de réponses d'un coup ::o

    MrJ : Je n'ai pas très bien compris la méthode que tu décris. Je choisis une base, j'écris les matrices des $u^k$ dans cette base, je trouve le rang de chaque matrice avec le pivot de Gauss (tout ça est faisable à la main, même en grandes dimensions, c'est juste hyper long). Pourquoi existerait-il une relation exploitable entre les $r+1$ premières puissances ?

    Sinon, en gros, vous me dites à peu près tous de passer par la décomposition de Frobenius, quoi.

    claude : Je n'ai pas assez de connaissances en algo/prog pour comprendre comment tu as fait, mais si ton algorithme permet en effet de trouver le polynôme minimal à chaque fois, c'est solide. Bon, encore, tu as utilisé des coefficients entiers et mis beaucoup de zéros. Si tu génères aléatoirement une matrice 30 par 30 à coefficients rationnels, je me demande ce que ça va donner !
  • Pourquoi est-ce qu'il existe une relation linéaire entre les premières puissances de $u$ ? Parce que justement le polynôme minimal existe (est non nul), ce qui peut se prouver par Cayley-Hamilton par exemple. Mais plus simplement que Cayley-Hamilton (ou sans doute est-ce une manière de prouver Cayley-Hamilton) :
    1) Prendre un vecteur non nul, itérer la matrice dessus jusqu'à stabiliser l'espace engendré. Soit $V \subseteq E$ le sous-espace engendré. On a $a_0 x + a_1 u(x) + \cdots + a_n u^n(x) = 0$, avec $x, u(x), \dots, u^{n-1}(x)$ une base de $V$. Ça donne un polynôme $P$ annulant $u$ sur $V$.
    2) Continuer récursivement sur $E/V$ : l'endomorphisme $u$ passe au quotient à $E/V$ et on continue sur ce passage au quotient.
    3) On dispose alors d'un polynôme $P$ annulant $u$ sur $V$ et d'un polynôme $Q$ annulant le passage au quotient de $u$ à $E/V$. Leur produit $PQ$ annule $u$ puisque $Q(u)$ est à valeurs dans $V$ et que donc ça donne $0$ quand on applique $P(u)$ au résultat de $Q(u)$.

    Mais sinon, pourquoi voudrais-tu calculer ça à la main ?
  • Parce que je ne sais pas coder d'algorithmes efficaces :-D

    Plus sérieusement, quand j'ai dit "à la main", c'était une mauvaise formulation. Ce que je voulais dire c'est "explicitement", contrairement aux raisonnements théoriques qui disent qu'un truc existe sans le déterminer explicitement.

    Mais oui, c'est Cayley-Hamilton qui dit que ça existe. Par contre, comment sait-on qu'on peut s'arrêter à $r+1$, quand $r$ est le rang de la matrice ?
  • Ah d'accord pour le "à la main". Si ta matrice est de rang $r$, ça veut dire quoi en terme d'image (ie "après une application") ?
  • Sans Cayley-Hamilton (mais donc beaucoup plus bête) l'espace des endomorphismes de $E$ de dimension $n$ s'identifie à l'espace des matrices $n \times n$ et donc est de dimension $n^2$. Donc la famille $(id, u, \dots, u^{n^2})$ est liée : il existe un polynôme annulateur de $u$ de degré au plus $n^2$. Bien sûr ça ne répond au côté explicite attendu par HT.
  • Ou alors tu as aussi ce que disait michel2 : la décomposition de Frobenius est liée à la "forme normale de Smith". Je ne sais pas comment ça se passe du côté des performances mais c'est quelque chose de "combinatoirement" assez simple, on effectue les opérations sur la matrice polynomiale les unes après les autres, et on peut oublier les étapes précédentes au fur et à mesure.
  • Champ-Pot-Lion : Je ne comprends pas vraiment. Si j'applique une application de rang $r$ à une famille de $\dim(E)$ vecteurs, ça me dit combien des images seront encore linéairement indépendantes via le théorème du rang. Mais quel est le rapport avec la recherche d'un polynôme annulateur de degré minimal ?
  • Si $u$ est de rang $r$, c'est que $u(E)$ est de dimension $r$. Et $u(E)$ est stable par $E$, donc $u$ restreint à $u(E)$ a un certain polynôme minimal $P$ de degré au plus $r$. Du coup, $u P(u) = 0$ sur $E$ tout entier.
  • Ok.

    Bon, ben je pense que je vais creuser la décomposition de Frobenius pour comprendre en détail les invariants de similitude !
  • claude : J'ai voulu fouiller un peu mes bouquins avant de lire plus en détail le PDF que tu as partagé.

    Dans mon livre d'algèbre, ils font une démonstration "purement théorique" du théorème sur les invariants de similitude, or j'ai besoin d'une démonstration qui les construit puisque ce que je veux trouver, le polynôme minimal, est l'un d'entre eux. Dans le Gourdon, la démonstration du théorème sur les invariants de similitude commence par "soit $k$ le degré du polynôme minimal", donc pour voir cette démonstration de manière constructive, il faut déjà connaître le polynôme minimal. Le serpent se mord la queue.

    Donc j'ai lu ton PDF, et c'est largement plus satisfaisant : ils décrivent un algorithme pour calculer le polynôme minimal à condition de connaître une "shift-basis" pour l'endomorphisme, et ils décrivent une manière de trouver une telle base.

    Excellente trouvaille du coup, merci ! J'essaierai de lire ça en détail pour en extraire la partie qui m'intéresse.
  • HomoTopi

    $\bullet$ Je n'ai pas regardé en détails l'article de Augot & Camion mais par contre j'avais lu assez attentivement la thèse de Ozello (1987) qui figure dans la bibliographie. Ce qui m'a ramené 30 ans en arrière, à l'époque où j'avais implémenté une partie des résultats de Ozello dans le langage ScratchPad.

    Pour parvenir à mes fins (implémentation), j'avais écrit (pour moi) une note en TeX (du TeX maison, pas du LaTeX). Mais j'ai tout perdu : la thèse de Ozello et je ne peux pas recompiler les sources TeX pour plusieurs raisons (encodage IBM des sources + TeX maison). Et enfin ScatchPad/Axiom est mort depuis belle lurette. J'ai juste réussi à retrouver dans mon merd.er un tirage papier. J'en attache la première et dernière pages scannées (rendu pas terrible).

    $\bullet$ Hier pour passer le temps, voilà ce que j'ai fait un peu près, cela ne va pas ch.er loin.

    $\blacktriangleright$ La première étape est celle qui m'a pris le plus de temps : chercher, dans le système de Calcul Formel que j'utilise actuellement, les primitives pour parvenir à mes fins. A savoir, au dessus d'un corps, exprimer un vecteur comme combinaison linéaire d'autres vecteurs (indépendants) ...etc.. . C'est un langage que je connais assez bien ainsi que les divers domaines qui interviennent ici (Algèbre linéaire, matrices, espaces vectoriels ... ). J'ai bien cherché mais je n'ai rien trouvé de vraiment satisfaisant et je me suis contenté de ce qui vient.

    $\blacktriangleright$ La deuxième étape a été d'écrire l'invariant en commentaire (la ligne où il y a du rouge) et le choix du nom des variables locales. J'ai dû vectoriser les matrices mais ça, c'est du rien car cela consiste à dire que $M_n(K) \simeq K^{n^2}$. Une fois bien convaincu de l'invariant et de la variation de $k$ entre 1 et $n$, j'ai écrit le reste. La méthode consiste donc à :
    $$
    A^k \quad \buildrel {?} \over \in \quad K.A^0 \oplus K.A^1 \oplus \cdots \oplus K.A^{k-1}
    $$en ayant stocké dans une séquence la suite $(A^0, A^1, \cdots, A^{k-1})$ où plutôt la séquence des vectorisés de ces matrices (c'est la variable Apowers avec un s).
    [color=#000000]NaiveMinimalPolynomial := function(A)
      K := BaseRing(A) ;
      KX<X> := PolynomialRing(K) ;
      n := NumberOfRows(A) ;
      Apower := One(MatrixRing(K,n)) ;
      Apowers := [Vector(Apower)] ;
      for k := 1 to n do
        // Apower = A^(k-1)  et   Apowers = [A^0, A^1, .., A^(k-1)] (vectorises) independants   [color=#FF0000]INVARIANT[/color]
        V := VectorSpaceWithBasis(Apowers) ;
        Apower := Apower * A ;
        ApowerVector := Vector(Apower) ;
        if ApowerVector in V then return X^k - KX!Coordinates(V,ApowerVector) ; end if ;
        Append(~Apowers, ApowerVector) ;
      end for ;
    end function ;
    [/color]
    
    Pourquoi ce n'est peut-être pas satisfaisant ? Ce n'est pas si facile à expliquer : il va y avoir en particulier 3 calculs les plus importants que je numérote I, II, III ci-dessous (je laisse tomber le calcul de $A^k$ à partir de $A^{k-1}$).

    J'utilise le constructeur VectorSpaceWithFixedBasis, qui j'en suis persuadé, commence par vérifier que son argument est bien constitué de vecteurs $K$-linéairement indépendants alors que MOI, JE LE SAIS : calcul I. Ensuite, je fais le test : est ce que $A^k \in K.A^0 \oplus K.A^1 \oplus \cdots \oplus K.A^{k-1}$ ? Il faut bien qu'il fasse quelque chose à ce moment là : calcul II. Et si la réponse est positive, je lui demande les coordonnées $a_0, a_1, \cdots, a_{k-1}$ de $A^k$ avec lesquelles je vais fabriquer le polynôme minimal $X^k - (a_0 + a_1 X + \cdots + a_{k-1}X^{k-1})$. Calcul III.
    J'ai l'idée qu'il y a de la redondance dans ces trois calculs I, II, III et je n'en ai pas la maîtrise.

    $\blacktriangleright$ La dernière étape a été la génération de matrices spéciales (ne pas prendre une matrice au hasard) et une rafale de milliers de tests pour vérifier la validité de la fonction (en comparant avec la fonction efficace).

    Bref, j'y ai passé un peu plus de temps que prévu à cause de la première étape.99382
    99384
  • Retrouver la thèse d'Ozello est la partie facile.
  • Bonjour !!
    Je pense que le sujet de Centrale MP sujet 1 de 2019 parle de ce sujet.

    Reno
Connectez-vous ou Inscrivez-vous pour répondre.