Polynôme minimal d'un endomorphisme

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}$

Cf par exemple http://www.lix.polytechnique.fr/~augot/LAA_96.pdf

MrJ a écrit:

Le polynôme minimal est l'invariant de similitude de plus petit degré.

Nan, de plus haut degré.

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 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.

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.

Bonjour !!
Je pense que le sujet de Centrale MP sujet 1 de 2019 parle de ce sujet.

Reno