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 ?
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 ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Edit : Merci GaBuZoMeu!
Évidemment en pratique, à la main, ça devient vite intenable en grandes dimension pour des matrices "génériques"
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}$. 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. 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. 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 !
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 !
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 ?
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 ?
Bon, ben je pense que je vais creuser la décomposition de Frobenius pour comprendre en détail les invariants de similitude !
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.
$\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). 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.
Je pense que le sujet de Centrale MP sujet 1 de 2019 parle de ce sujet.
Reno