On the computation of minimal polynomials, cyclic vectors, and Frobenius forms (Q1361771)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the computation of minimal polynomials, cyclic vectors, and Frobenius forms |
scientific article |
Statements
On the computation of minimal polynomials, cyclic vectors, and Frobenius forms (English)
0 references
8 December 1997
0 references
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)\).
0 references
minimal polynomial
0 references
complexity
0 references
factorization
0 references
characteristic polynomial
0 references
iterative algorithm
0 references
shift Hessenberg matrix
0 references
cyclic vector
0 references
Frobenius form
0 references
0 references