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

DOI10.1016/S0024-3795(97)80005-5MaRDI QIDQ1361771zbMATH OpenFDO

Publication date 8 December 1997

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0024-3795(97)80005-5

characteristic polynomial complexity cyclic vector factorization Frobenius form iterative algorithm minimal polynomial shift Hessenberg matrix

Mathematics Subject Classification ID

Canonical forms, reductions, classification (15A21) Complexity and performance of numerical algorithms (65Y20)

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

Recommendations

Cites work

Cited in

(14)

Describes a project that uses

Uses Software

AXIOM

This page was built for publication: On the computation of minimal polynomials, cyclic vectors, and Frobenius forms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361771)