Anneau de matrices sur corps finis

jaccuzzi

Bonjour à tous
Voilà,  je considère un corps fini, disons $\Bbb{F}_p$ avec $p$ premier et l'anneau $A_t$ des matrices carrées de taille $t$ sur $\Bbb{F}_p$. Je m'intéresse à la résolution d'équations non linéaires dans $A_t$. Par exemple, le nombre maximal de solutions d'une équation de degré $d$ et savoir s'il existe une méthode efficace de résolution.
Merci à vous.

nicolas.patrois

Tu peux te dire que tu cherches à trouver les matrices dont le polynôme donné est un polynôme annulateur.

À partir de là, tu peux chercher à factoriser le polynôme annulateur (il y a un algorithme qui le fait sur un corps fini) mais ça ne sera pas suffisant bien sûr.

Poirot

Les matrices solutions sont exactement celles dont le polynôme minimal fait partie des diviseurs du polynôme définissant l'équation.

Étape 1 : Factoriser le polynôme en question. Comme l'a dit nicolas.patrois, il existe des algorithmes pour faire ça, le plus connu étant l'algorithme de Berlekamp.

Étape 2 : Trouver les matrices ayant pour polynôme minimal un polynôme donné parmi les diviseurs de l'étape 1. J'imagine que c'est faisable en passant par la réduction de Frobenius.

On peut décomposer ces étapes pour donner une majoration du nombre de solutions.

jaccuzzi

Ah merci je vais réfléchir à ca ! Mais pour bien être sûr de m'être fait comprendre, je précise que les coefficients de l'équation sont aussi des matrices. Autrement dit, je cherche à résoudre des équations de la forme $M^t+A_{t-1}M^{t-1}+\ldots A_0=0$, où $A_0,\ldots,A_{t-1}$ sont des matrices. Il me semble que votre réponse suppose que les coefficients dont des éléments de $F_p$. Pouvez-vous me confirmer que je me trompe ?

Merci (vraiment) à vous.

Poirot

Ah effectivement ça complique la chose. Dans ce cas tu te retrouves avec des équations polynomiales générales, et là on rentre dans le domaine de la géométrie algébrique ! Il existe des bornes pour les solutions de telles équations sur les corps finis, ça s'appelle l'hypothèse de Riemann sur les corps finis démontrées par Deligne dans les années 70. Bref, rien d'évident...

Math Coss

Je trouve petit joueur de ne pas prendre des équations plus générales, avec des monômes de la forme $AMBMC\cdots MK$. À y être...

jaccuzzi

Ok! Merci à vous !

Sinon j'avais une autre question ! $A_t$ est donc un anneau non commutatif. Je considère une matrice carrée $M$ de taille $n$ à coefficients dans $A_t$. Je me demandais à quelle condition une telle matrice possède un inverse et comment trouver $M'$ tel que $M'M=Id$ (les techniques classiques sur les anneaux commutatifs n'étant pas opérationnelles). Il me semble qu'il suffit de résoudre un système linéaire à coefficients dans $F_p$ à $t\times n$ variables/équations.

Encore merci.

Poirot

C'est plutôt $n^2 t^2$ variables et équations ! Et ton problème est équivalent à déterminer l'inversibilité d'une matrice carrée de taille $n \times t$, donc le déterminant est la clé.