Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-29T06:05:58.625Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing Minimal Polynomials of Matrices

Published online by Cambridge University Press:  01 February 2010

Max Neunhöffer  and
Cheryl E. Praeger
Max Neunhöffer
Affiliation:
University of St Andrews, School of Mathematics and Statistics, North Haugh, St Andrews, Fife KY16 9SS, Scotland, United Kingdom, [email protected]
Cheryl E. Praeger
Affiliation:
University of Western Australia, School of Mathematics and Statistics (M019), 35 Stirling Highway, Crawley 6009, Western Australia, Australia, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 11 , 2008 , pp. 252 - 279
Copyright
Copyright © London Mathematical Society 2008

References

1.Augot, D. and Camion, P., ‘On the computation of minimal polynomials, cyclic vectors, and Frobenius forms’, Linear Algebra Appl. 260 (1997) 61–94.CrossRefGoogle Scholar
2.Bosma, W. and Cannon, J. J., Magma, Handbook of Magma Functions, edn 2.14 (2007), http://magma.maths.usyd.edu.au/magma/htmlhelp/MAGMA.htm.Google Scholar
3.Eberly, W., ‘Asymptotically efficient algorithms for the Frobenius form’, Department of Computer Science, University of Calgary Technical Report (2000), http://pages.cpsc.ucalgary.ca/~eberly/Research/publications.php.Google Scholar
4.The GAP Group, GAP – Groups, Algorithms, and Programming, version 4.4.10 (2007), http://www.gap-system.org/.Google Scholar
5.Giesbrecht, M., ‘Nearly optimal algorithms for canonical matrix forms’, SIAM J. Comput. 24 (1995) 948–969.CrossRefGoogle Scholar
6.Holt, D. F. and Rees, S., ‘Testing modules for irreducibility’, J. Austral. Math. Soc. Ser. A 57 (1994) 1–16.CrossRefGoogle Scholar
7.Jacobson, N., Basic algebra. I (W. H. Freeman & Co., San Francisco, CA, 1974).Google Scholar
8.Keller-Gehrig, W., ‘Fast algorithms for the characteristic polynomial’, Theoret. Comput. Sci. 36 (1985) 309–317.CrossRefGoogle Scholar
9.Knuth, D. E., The art of computer programming, vol. 2, Seminumerical algorithms, 3rd edn, Addison-Wesley Series in Computer Science and Information Processing (Addison-Wesley, Reading, MA, 1998).Google Scholar
10.O'Brien, E. A., ‘Towards effective algorithms for linear groups’, Finite geometries, groups, and computation (de Gruyter, Berlin, 2006) 163–190.CrossRefGoogle Scholar
11.Parker, R. A., ‘The computer calculation of modular characters (the Meat-Axe)’, Computational group theory, Durham, 1982 (Academic Press, London, 1984) 267–274.Google Scholar
12.Steel, A., ‘A new algorithm for the computation of canonical forms of matrices over fields’, Computational algebra and number theory, London, 1993, J. Symbolic Comput. 24 (1997) 409–432.CrossRefGoogle Scholar
13.Storjohann, A., ‘An O(n 3) algorithm for the Frobenius normal form’, Proceedings of the International Symposium on Symbolic and Algebraic Computation, Rostock, 1998 (ACM, New York, 1998) 101–104 (electronic).Google Scholar
14.Storjohann, A., ‘Deterministic computation of the Frobenius form (extended abstract)’, 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2001 (IEEE Computer Society, Los Alamitos, CA, 2001) 368–377.CrossRefGoogle Scholar
15.von zur Gathen, J. and Gerhard, J., Modern computer algebra, 2nd edn (Cambridge University Press, Cambridge, 2003), ISBN 0-521-82646-2.Google Scholar
16.Wilson, R., Walsh, P., Tripp, J., Suneiman, I., Rogers, S., Parker, R., Norton, S., Nickerson, S., Linton, S., Bray, J. and Abbott, R., ‘The WWW Atlas of Finite Group Representations’ (1999), http://brauer.maths.qmul.ac.uk/Atlas/.CrossRefGoogle Scholar