Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-16T17:18:04.587Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing in Nilpotent Matrix Groups

Published online by Cambridge University Press:  01 February 2010

A.S. Detinko  and
D.L. Flannery
A.S. Detinko
Affiliation:
Department of Mathematics, National University of Ireland, Galway, Ireland, [email protected]
D.L. Flannery
Affiliation:
Department of Mathematics, National University of Ireland, Galway, Ireland, [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 algorithms for testing nilpotency of matrix groups over finite fields, and for deciding irreducibility and primitivity of nilpotent matrix groups. The algorithms also construct modules and imprimitivity systems for nilpotent groups. In order to justify our algorithms, we prove several structural results for nilpotent linear groups, and computational and theoretical results for abstract nil-potent groups, which are of independent interest.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 9 , 2006 , pp. 104 - 134
Copyright
Copyright © London Mathematical Society 2006

References

1. Babai, László, Beals, Robert, yi Cai, Jin, Ivanyos, Gábor and Luks, Eugene M., ‘Multiplicative equations over commuting matrices’. Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, 1996 (ACM. New York. 1996) 498–507.Google Scholar
2. Beals, R., ‘Towards polynomial time algorithms for matrix groups’, DIMACS II, Series in Discrete Mathematics and Theoretical Computer Science 28 (Amer. Math. Soc. Providence, RI 1997) 31–54.Google Scholar
3. Beals, R., ‘Algorithms for matrix groups and the Tits alternative’, J. Comput. System Set 58 (1999) 260–279.Google Scholar
4. Berger, T. R., Kovács, L. G. and Newman, M. F., ‘Groups of prime power order with cyclic Frattini subgroup’, Nederl. Akad. Wetensch. Indag. Math. 42 (1980) 13–18.Google Scholar
5. Bialostocki, A., The nilpotency class of the p-Sylow subgroups of GL(n, q) where (p, q) = 1’, Canadian Math. Bull. 29 (1986) 218–223.Google Scholar
6. Celler, F. and Leedham-Green, C. R., ‘Calculating the order of an invertible matrix’, DIMACS II, Series in Discrete Mathematics and Theoretical Computer Science 28 (Amer. Math. Soc., Providence. RI, 1997) 55–60.Google Scholar
7. Cooperman, G. and Finkelstein, L., ‘Combinatorial tools for computational group theory’, DIM ACS II, Series in Discrete Mathematics and Theoretical Computer Science 11 (Amer. Math. Soc., Providence. RI. 1993) 31–54.Google Scholar
8. Detinko, A. S. and Flannery, D. L., ‘Classification of nilpotent primitive linear groups over finite fields’, Glasgow Math. J. 46 (2004) 585–594.Google Scholar
9. Detinko, A. S. and Flannery, D. L., ‘Nilpotent primitive linear groups over finite fields’, Comm. Algebra 33 (2005) 1–9.Google Scholar
10. Dixon, John D., The structure of linear groups (Van Nostrand Reinhold, London, 1971).Google Scholar
11. Eick, B. and Ostheimer, G., ‘On the orbit-stabilizer problem for integral matrix actions of polycyclic groups’, Math. Comp. 72 (2003) 1511–1529.Google Scholar
12. Holt, Derek F., Eick, Bettina and A., Eamonn O'Brien. Handbook of computational group theory (Chapman & Hall/CRC Press, Boca Raton/London/New York/Washington. 2005).CrossRefGoogle Scholar
13. Holt, D., Leedham-Green, C. R., O'Brien, E. A. and Rees, S., ‘Computing matrix group decompositions with respect to a normal subgroup’, J. Algebra 184 (1996) 818–838.Google Scholar
14. Holt, D., Leedham-Green, C. R., O'Brien, E. A. and Rees, S., ‘Testing matrix groups for primitivity’. J. Algebra 184 (1996) 795–817.Google Scholar
15. Holt, D. and Rees, S., ‘Testing modules for irreducibility’, J. Austral. Math. Soc. Ser A 57 (1994) 1–16.Google Scholar
16. Huppert, B., Endiiche gruppen I (Springer, Berlin. 1967).Google Scholar
17. Lo, E., ‘Finding intersections and normalisers in finitely generated nilpotent groups’, J. Symbolic Comput. 25 (1998)45–59.Google Scholar
18. Luks, E., ‘Computing in solvable matrix groups’, Proc. 33rd IEEE Symposium on Foundations of Computer Science (IEEE Computer Society Press, Washington, DC. 1992) 111–120.Google Scholar
19. Ostheimer, G., ‘Practical algorithms for polycyclic matrix groups’, J. Symbolic Comput. 28 (1999) 361–379.CrossRefGoogle Scholar
20. Robinson, Derek J. S., A course in the theory of groups, Graduate Texts in Mathematics 80 (Springer, New York. 1996).Google Scholar
21. Rónyai, L., Computations in associative algebras, DIMACS Series in Discrete Mathematics 11 (Amer. Math. Soc.. Providence. RI. 1993) 221–243.Google Scholar
22. Segal, D., Polycyclic groups (Cambridge University Press, Cambridge, 1983).Google Scholar
23. Seress, Á., ‘An introduction to computational group theory’, Notices Amer. Math. Soc. 44 (1997) 671–679.Google Scholar
24. Seress, Á., Permutation group algorithms (Cambridge University Press, Cambridge. 2003).CrossRefGoogle Scholar
25. Sims, C. C., Computation with finitely presented groups, Encyclopedia of Math. Appl. 48 (Cambridge University Press, New York, 1994).Google Scholar
26. Suprunenko, D. A., Soluble and nilpotent linear groups, Transl. Math. Monogr. 9 (Amer. Math. Soc, Providence, RI, 1963).Google Scholar
27. Suprunenko, D. A., Matrix groups, Transl. Math. Monogr. 45 (Amer. Math. Soc. Providence, RI. 1976).Google Scholar
28. Wehrfritz, B. A. F., Infinite linear groups (Springer, Berlin/Heidelherg/New York, 1973).CrossRefGoogle Scholar