Computing Minimal Polynomials of Matrices

Max Neunhoeffer, Cheryl E. Praeger

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

We present and analyse a Monte-Carlo algorithm to compute the minimal polynomial of an n × n matrix over a finite
field that requires O(n3 ) 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(n4 ). Finally, we report the results
of practical experiments with an implementation of our algorithms in comparison with the current algorithms in the GAP
library.
Original languageEnglish
Pages (from-to)252-279
Number of pages28
JournalLMS Journal of Computation and Mathematics
Volume11
DOIs
Publication statusPublished - Jan 2008

Fingerprint

Dive into the research topics of 'Computing Minimal Polynomials of Matrices'. Together they form a unique fingerprint.

Cite this