On the computation of minimal polynomials, cyclic vectors, and Frobenius forms

Daniel Augot 1 Paul Camion 1
1 CODES - Coding and cryptography
Inria Paris-Rocquencourt
Abstract : Various algorithms connected with the computation of the minimal polynomial of an n × n matrix over a field K are presented here. The complexity of the first algorithm, where the complete factorization of the characteristic polynomial is needed, is O(√nn3). It produces the minimal polynomial and all characteristic subspaces of a matrix of size n. Furthermore, an iterative algorithm for the minimal polynomial is presented with complexity O(n^3 + n^2m^2), where m is a parameter of the shift Hessenberg matrix used. It does not require knowledge of the characteristic polynomial. Important here is the fact that the average value of m or mA is O(log n). Next we are concerned with the topic of finding a cyclic vector for a matrix. We first consider the case where its characteristic polynomial is square-free. Using the shift Hessenberg form leads to an algorithm at cost O(n^3 + m^2n^2). A more sophisticated recurrent procedure gives the result in O(n^3) steps. In particular, a normal basis for an extended finite field of size qn will be obtained with deterministic complexity O(n^3 + n^2log q). Finally, the Frobenius form is obtained with asymptotic average complexity O(n^3log n). All algorithms are deterministic. In all four cases, the complexity obtained is better than for the heretofore best known deterministic algorithm.
Type de document :
Article dans une revue
Linear Algebra and its Applications, Elsevier, 1997, 260, pp.61-94. 〈10.1016/S0024-3795(97)80005-5〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00541318
Contributeur : Daniel Augot <>
Soumis le : mardi 30 novembre 2010 - 12:58:35
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : mardi 1 mars 2011 - 02:50:57

Fichier

LAA_96.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Daniel Augot, Paul Camion. On the computation of minimal polynomials, cyclic vectors, and Frobenius forms. Linear Algebra and its Applications, Elsevier, 1997, 260, pp.61-94. 〈10.1016/S0024-3795(97)80005-5〉. 〈inria-00541318〉

Partager

Métriques

Consultations de la notice

201

Téléchargements de fichiers

175