On the computation of minimal polynomials, cyclic vectors, and Frobenius forms
type: Item
instance of: scholarly article
title: On the computation of minimal polynomials, cyclic vectors, and Frobenius forms
zbMATH Open document ID: 0877.65022
DOI: 10.1016/S0024-3795(97)80005-5
author: Daniel Augot
author: Paul Camion
published in: Linear Algebra and its Applications
publication date: 1997-12-08T00:00:00Z
review text: Algorithms related to the computation of the minimal polynomial of an \(n\times n\) matrix over a field \(K\) are introduced. The complexity of the first algorithm, where the complete factorization of the characteristic polynomial is needed, is \(O(\sqrt n\cdot n^3)\). An iterative algorithm for finding the minimal polynomial has complexity \(O(n^3+ n^2m^2)\), where \(m\) is a parameter of the shift Hessenberg matrix used. The method does not require the knowledge of the characteristic polynomial. The average value of \(m\) is \(O(\log n)\). Next methods are discussed for finding a cyclic vector for a matrix. The authors first consider the case when its characteristic polynomial is squarefree. Using the shift Hessenberg form leads to an algorithm at cost \(O(n^3+ n^2m^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 \(q^n\) will be obtained with complexity \(O(n^3+ n^2\log q)\). Finally, the Frobenius form is obtained with asymptotic average complexity \(O(n^3\log n)\).
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A21
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 1040489
zbMATH Keywords: minimal polynomial
zbMATH Keywords: complexity
zbMATH Keywords: factorization
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: iterative algorithm
zbMATH Keywords: shift Hessenberg matrix
zbMATH Keywords: cyclic vector
zbMATH Keywords: Frobenius form
reviewed by: F. Szidarovszky
describes a project that uses: AXIOM
MaRDI profile type: Publication
cites work: Q3236675
cites work: Q3136478
cites work: Q3139838
cites work: Q3254327
cites work: Nearly Optimal Algorithms for Canonical Matrix Forms
cites work: Q4234328
cites work: Q4234235
cites work: Q4023355
cites work: Q3773973
cites work: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
cites work: A deterministic construction of normal bases with complexity \(O(n^ 3+n\log n\log(\log n)\log q)\)
cites work: Some asymptotic results on finite vector spaces
cites work: Q4234329
cites work: Constructing normal bases in finite fields
cites work: Computing Frobenius maps and factoring polynomials
cites work: Q5599376
description: scientific article; zbMATH DE number 1040489