Computing Minimal Polynomials of Matrices

Details Computing Minimal Polynomials of Matrices Computing Minimal Polynomials of Matrices

2007-05-07

arxiv.org/abs/0705.0933v2

Mathematics

Rings and Algebras

Scientific paper

We present and analyse a Monte-Carlo algorithm to compute the minimal polynomial of an $n\times n$ matrix over a finite field that requires $O(n^3)$ field operations and O(n) random vectors, and is well suited for successful practical implementation. The algorithm, and its complexity analysis, use standard algorithms for polynomial and matrix operations. We compare features of the algorithm with several other algorithms in the literature. In addition we present a deterministic verification procedure which is similarly efficient in most cases but has a worst-case complexity of $O(n^4)$. Finally, we report the results of practical experiments with an implementation of our algorithms in comparison with the current algorithms in the {\sf GAP} library.

Affiliated with

Also associated with

No associations

Rating

Computing Minimal Polynomials of Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Minimal Polynomials of Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Minimal Polynomials of Matrices will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-598761