Polynôme minimal¶

Note

Soit $E$ une $K$-algèbre, et $A\in E$. Le polynôme minimal $m_A(X)\in K[x]$ de $A$ est le polynôme unitaire de plus petit degré qui annule $A$.

C’est le générateur unitaire de l’idéal annulateur $I_A=\set{P(x)\in K[x],P(A)=0}$.
Si $E$ est de dimension finie, il est toujours non nul.
Si $E$ est intègre, c’est un polynôme irréductible.
Si $E=M_n(K)$, c’est un diviseur du polynôme caractéristique $\chi_A(X)$ (d’après Cayley-Hamilton).

(remarque : définition plus agréable en termes de $K[x]$-module)

Polynômes¶

Créer une liste à 8 éléments. Comment la transformer en polynôme ?
solution xcas ⇲ ⇱ solution xcas
l:=[seq(k,k=1..8)]; poly2symb(l,x);
Comment renverser la liste ?
solution xcas ⇲ ⇱ solution xcas
revlist(l);
Comment évaluer un polynôme sous forme symbolique ?
solution xcas ⇲ ⇱ solution xcas
P:=x^2+1; subst(P,x=sqrt(2)); unapply(P,x)(sqrt(2));
la seconde méthode crée une fonction au passage
Comment évaluer un polynôme sous forme d’une liste de coefficients ? Dans quel ordre sont-ils rangés ?
solution xcas ⇲ ⇱ solution xcas
l:=[1,0,1]; peval(l,sqrt(2));

Minimal selon un vecteur¶

Soit $A\in M_n(K)$ et $v\in K^n$. Par définition, le minimal $m_{A,v}(X)$ de $A$ selon $v$ est le minimal de $A$ sur l’espace engendré par les itérés $A^kv$, c’est-à-dire le polynôme générateur de l’idéal $\set{P, P(A)(v)=0}$.

Définir une matrice aléatoire $A\in M_8(\Z)$, et choisir $v\in \Z^8$. Expliquer comment calculer $m_{A,v}(X)$ à l’aide d’un calcul de noyau.
solution xcas ⇲ ⇱ solution xcas
n:=8; v:=[seq(k,k=1..n)]; A := ranm(n,n);
Il s’agit de trouver une famille liée $v,Av,\dots A^dv$ minimale, c’est-à-dire un noyau non nul d’une matrice formée des colonnes $[v,Av,\dots A^dv]$.

En construit cette matrice, attention en xcas une matrice est une liste de lignes, donc il faut transposer avant de prendre le noyau.
M:=v; AA:=v; for(ii:=1;ii<=n;ii++){ AA:=A*AA;M:=M,AA;} N:=nullspace(transpose([B]))[0];
Attention, les polynômes commencent a la puissance maximale, il faut inverser l’ordre
P:=poly2symb(revlist(N),x); normal(subst(P,x=A));

Déterminer un vecteur $v$ pour lequel $m_{A,v}$ est de degré inférieur à $m_A$.

solution xcas ⇲ ⇱ solution xcas

A:=diag(companion(x^4-1,x),companion((x^2-1)^2,x));
B:=v; AA:=v
for(ii:=1;ii<=n;ii++){ AA:=A*AA;B:=B,AA;}
nullspace(B);
N:=nullspace(transpose([B]))[0];
P:=poly2symb(revlist(N),x);
normal(subst(P,x=A));

Montrer qu’il existe toujours un vecteur $v$ pour lequel $m_{A,v}=m_A$, tandis que les vecteurs $v$ pour lesquels $m_{A,v}\neq m_A$ sont dans une union finie de sous-espaces vectoriels.

solution ⇲ ⇱ solution
les vecteurs a eviter sont dans ker(P(u)) ou P divise pmin, donc nombre fini d’espaces vectoriels stricts à eviter.
Quelle est la complexité du calcul du polynôme minimal ?

solution ⇲ ⇱ solution
On a calculé les $A^kv$ par récurrence. $AA$ est un vecteur donc le produit $A*AA$ est en O(n^2), et l’on fait $n$ tours, donc c’est en $O(n^3)$.

Suites récurrentes¶

On considère une suite donnée par une relation de récurrence d’ordre $d$

\[\forall n\geq 0, \sum_{i=0}^d u_{n+i}r_i = 0\]

dont on donne un annulateur unitaire $R(x)=\sum_{i=0}^d r_i x^i$ et les valeurs initiales $u=(u_0,\dots u_{d-1})$.

En considérant l’espace $E=K^\N$ des suites à coefficients dans $K$ muni de l’opérateur de décalage $T:(u_n)\mapsto (u_{n+1})$, que peut-on dire de $R(x)$ ?

Montrer que le polynôme minimal $m_{T,u}$ de la suite $u$ divise $R$.

solution ⇲ ⇱ solution
$R(x)$ est un annulateur, donc le minimal $m_{T,u}$ le divise.
Écrire une fonction linrec(R,u,n) qui calcule les $n$ premiers termes d’une suite annulée par $R$ et de premiers termes $u$.
solution ⇲ ⇱ solution
On considère que $R$ est donné sous forme de polynôme unitaire. On le convertit en liste $[c_d,\dots c_0]$ dans la fonction
linrec(R,u,n):= { local c,k,l,j; c := symb2poly(R); l := length(c)-1; for(k:=length(u);k<n;k++) { u := append(u,-sum(c[j]*u[k-j],j,1,l)); } return u; }:;
Les suites récurrentes à coefficients dans des corps finis sont ultimement périodiques, pourquoi ? Trouver la période des suites récurrentes sur $\F_2$ données par les valeurs initiales $1,1,\dots 1$ et les polynômes

\[\begin{split}R_1(x) &= x^5+x^4+x \\ R_2(x) &= x^5+x^3+1\end{split}\]
solution ⇲ ⇱ solution
Sur un corps fini $\F_q$, on n’a qu’un nombre fini d’états $u_n,u_{n+1},\dots u_{n+d-1}$ possibles, donc on repasse par le même état, donc la suite est périodique à partir d’un certain rang.
linrec(x^5+x^4+x, [seq(1%2,5)], 40)%0
Cette suite est de période 15 à partir du rang $6$.
linrec(x^5+x^3+1, [seq(1%2,5)], 40)%0
Cette suite est de période $31$.
Quelle est la période maximale d’une suite de degré $n$ sur $\F_p$ ?

solution ⇲ ⇱ solution
Il y a $p^n$ états, parmi lesquels l’état nul donne la suite nulle, donc la période est au plus $p^n-1$. L’exemple précédent montre que la borne est atteinte pour $p=2$ et $n=5$.
Montrer qu’une suite admet $\ell$ pour période si et seulement si son polynôme minimal divise $x^\ell-1$.

solution xcas ⇲ ⇱ solution xcas
La suite est de période $\ell$ si et seulement si $T^n(u)=u, donc ssi $x^\ell-1$ est annulateur, ssi le minimal le divise.
Pour quels polynômes obtient-on une période maximale ? Construire une suite récurrente de période $127$.
solution xcas ⇲ ⇱ solution xcas
Soit $n$ le degré, on cherche une suite de période $p^n-1$, il faut donc que le minimal divise $x^{p^n-1}-1$ mais pas $x^d-1$ pour $d\mid p^n-1$, ce doit donc être un facteur de $\Phi_{p^n-1}(x)$, lequels sont bien de degré $n$ sur $\F_p$.

Pour $127=2^7-1$,
factor( poly2symb(cyclotomic(127)) % 2 )
le polynôme $x^7+x+1$ convient.
Montrer qu’un annulateur d’une suite de degré $d$ est déterminé par les $2d$ premiers termes de la suite. Retrouver l’annulateur de la suite de période $127$ à partir des premiers termes de la suite.

solution xcas ⇲ ⇱ solution xcas
On a $d$ coefficients du polynôme à déterminer, les $d$ équations de récurrence donnant $u_d,\dots u_{2d-1}$ les déterminent.
Écrire une fonction annulateur_suite(u) qui renvoie un annulateur de degré $\leq d$ d’une suite à partir de $2d$ coefficients.

Algorithme de Berlekamp-Massey¶

Note

Soit $(u_n)$ une suite récurrente linéaire, on construit la série formelle

\[g(x) = \sum_n u_n x^n.\]

Soit $P(x)=\sum_i c_ix^i$ un annuleur de $(u_n)$. On exprime l’annulation de la récurrence en terme de produit de séries formelle via le polynôme réciproque

\[\tilde P(x) = x^dP(1/x) = \sum_i c_i x^{n-i}.\]

On a alors

\[\tilde P(x)g(x) = r(x)\]

où $r(x)$ est un polynôme de degré inférieur ou égal à $d-1$.

Réciproquement, la théorie des approximants de Padé affirme que pour tout couple $m,n$, et toute série $g(x)$ telle que $g(0)\neq 0$, il existe une unique fraction rationnelle

\[\frac {r(x)}{v(x)}\equiv g(x)\bmod x^{m+n+1}\]

avec $\deg v\leq m$ et $\deg r\leq n$.

Dans le cas qui nous intéresse, si $(u_n)$ est une suite récurrente linéaire d’ordre $d$, le théorème affirme que l’approximant de Padé de niveau $(d-1,d)$ de $g(x)\bmod x^{2d}$ est égal au couple $(r(x),\tilde P(x))$.

Enfin, le calcul des approximants de Padé peut se faire en résolvant un système linéaire (en complexité $(n+m)^3$), ou bien via l’algorithme d’Euclide étendu en complexité quadratique.

Ce calcul est disponible sous xcas via la fonction pade.

On considère la suite de valeurs initiales $1,2,3,4,5$ et de polynôme générateur $x^5-x^4+x^3-2x^2+2x-1$. Former la série $b(x)=\sum_k b_kx^x$ tronquée à l’ordre $10$.
solution ⇲ ⇱ solution
b := linrec(x^5-x^4+x^3-2x^2+2x-1,[1,2,3,4,5],10) P := sum(b[k]*x^k,k,0,9)
À l’aide de la fonction pade, retrouver le polynôme générateur à partir de $b(x)$.
solution xcas ⇲ ⇱ solution xcas
R := pade(P,x,9,5)
le dénominateur est bien le polynôme réciproque du minimal

Algorithme de Wiedemann¶

Cet algorithme de résolution des systèmes linéaires $Ax=b$ est particulièrement intéressant dans le cas de matrices sur les corps finis, de grandes dimension et «creuses», c’est-à-dire avec peu de coefficients non-nuls.

C’est le cas par exemple pour l’algorithme page-rank de google, ou pour les algorithmes de factorisation par crible (matrices de dimension plusieurs millions, mais avec moins d’une centaine de coefficients non-nuls par ligne).

Dans ce genre de cas, on ne stocke pas toute la matrice mais seulement l’emplacement de ses coefficients non-nuls. Inverser $A$ par une technique de pivot de Gauss est hors de question, puisque le pivot a tendance à remplir la matrice.

La technique de Wiedemann consiste à calculer le polynôme minimal de l’endomorphisme $A$ restreint au sous-espace de Krylov engendré par les itérés de $b$ par $A$. Ce polynôme permet alors d’exprimer $A^{-1}b$ comme un polynôme en les $A^kb$.

Construire une matrice $A$ aléatoire sur $\F_2$.
Pour tout couple de vecteurs $u,v\in K^n$, on considère la suite $a_n={}^tuA^nv$ et son minimal polynôme minimal $P_{u,v}$.
Avec les notations ci-dessus, montrer que $P_{u,v}\mid m_{A,v}\mid m_A(x)$.
Montrer qu’il existe $u,v$ tels que $P_{u,v}=m_A$.
En déduire un algorithme de calcul (probabiliste) du polynôme minimal.

En réalité, on ne trouve pas le polynôme minimal de $A$ mais un annulateur de la trace (relativement à la forme linéaire $u^T$) du minimal de $A$ sur le sous-espace engendré par les itérés de $v$ (appelé sous-espace de Krylov).

Une approche probabiliste consiste à prendre le ppcm des annulateurs trouvés via divers couples $(u,v)$ jusqu’à vérifier que l’on annule $A$. Pour montrer que c’est efficace, on peut montrer des résultats de densité sur les vecteurs $u$ et $v$ qui fournissent le résultat.

L’algorithme de Wiedemann ne s’intéresse en réalité pas au polynôme minimal de $A$, mais bien au minimal sur l’espace de Krylov des $A^kv$, le but étant de calculer $A^{-1}v$.

Polynôme minimal¶

Polynômes¶

Minimal selon un vecteur¶

Suites récurrentes¶

Algorithme de Berlekamp-Massey¶

Algorithme de Wiedemann¶

Table Of Contents

Plan

Langage