Matrix Groups and Computational Group Theory

Can one rotate only one corner piece in Rubik’s cube? What are the energy levels of the buckyball molecule? What is the Galois group of the polynomial x^8 + 2x^7 + 28x^6 + 1728x + 3456? What are the possible symmetry groups of crystals?

These are all questions which, directly or in a not so obvious way, lead to problems in computational group theory.

 

Algebraic structures are well suited for machine computations as we can describe large objects concisely by a set of generators: for example, 50 bits are enough to define the group of 5x5 invertible matrices over the field of order 2, a group of order 9,999,360, by just using two 0-1 matrices.

Computational group theory (CGT) is one of the oldest and most developed branches of Computational Algebra. Its most important subareas correspond to the most frequently used representations of groups (permutation groups, matrix groups, and groups defined by generators and relators), as well as to the most powerful tool for investigating groups: representation theory..

 

Research


Matrix groups are important and very compact representations of groups, but pose serious computational problems. Researchers in the CMSC are in the vanguard of recent progress designing algorithms for matrix group computation and analysing their complexity.
 
Some highlights
 

  1. Recognising that a given group of matrices generates a finite classical group was one of the first major achievements of the international matrix group recognition project, and this fundamental problem was solved by Cheryl Praeger working with Peter Neumann (P1), Alice Niemeyer (P2) and Bob Guralnick, Tim Penttila and Jan Saxl (P3). 

  2. The finite classical groups occur as critical components in general purpose matrix group computational systems. They must be recognised in completely arbitrary (non-standard) representations. They are usually modelled as “black-box groups”, where only basic group operations can be assumed available – and no special features of matrices can be used (such as finding determinants or characteristic polynomials). The challenging problem is to construct standard generators for such black-box finite classical groups, thereby allowing efficient computation. For such groups over finite fields of odd order  effective polynomial time algorithms have been developed by Leedham-Green, O’Brien and others. Providing rigorous, optimal analyses of their procedures has proved even more of a challenge. The majority of their procedures have been successfully analysed through papers by Praeger working jointly with  Frank Lubeck, Alice Niemeyer (P4), Akos Seress (P5, P6), and John Dixon (P7). Completing this task for all remaining types of classical groups is an on-going research project of Praeger with Stephen Glasby and Colva Roney-Dougal.

  3. Efficient procedures have also been for black-box finite classical groups over fields of even order by Dietrich, Leedham-Green, Lubeck and O’Brien, relying on analyses by Praeger, Seress and Yalcinkaya (P8). The possibility of even more efficient algorithms is hinted at in the analyses in (P8) and also in work with Niemeyer (P9). This is part of on-going research.

 
 

  • (P1) 1992  A recognition algorithm for special linear groups, (with P.M. Neumann), Proc. London Math. Soc.(3) 65, 555-603.

  • (P2) 1998  A recognition algorithm for classical groups over finite fields, (with A. Niemeyer), Proc. London Math. Soc. (3) 77, 117--169.

  • (P3) 1999 Linear groups with orders having certain large prime divisors, (with R. Guralnick, T. Penttila, and J. Saxl), Proc. London Math. Soc. (3) 78, 167--214.

  • (P4) 2009  Finding involutions in finite Lie type groups of odd characteristic, (with Frank Lubeck and Alice C Niemeyer), J. Algebra 321,  3397–3417. http://www.sciencedirect.com/scidirimg/clear.gifdoi:10.1016/j.jalgebra.2008.05.009   

  • (P5) 2011 Probabilistic generation of finite classical groups in odd characteristic by involutions, (with Akos Seress). J. Group Theory. 14, 521-545.   doi: 10.1515/JGT.2010.061

  • (P6) 2012  Regular semisimple elements and involutions in finite general linear groups of odd characteristic. (with Akos Seress). Proc. Amer. Math. Soc. 140, 3003-3015.   doi: 10.1090/S0002-9939-2012-11491-1

  • (P7)  2018  Strong involutions in finite special linear groups of odd characteristic. (with John D. Dixon and Akos Seress).   J. Alg.  498, 413-447.   doi: 10.1016/j.jalgebra.2017.11.047

  • (P8)  2015 Generation of finite classical groups by pairs of elements with large fixed point spaces, (with Akos Seress and Sukru Yalcinkaya). J. Alg. 421, 56-101.    doi: 10.1016/j.jalgebra.2014.08.020,    arXiv: 1403.2057 

  • (P9) 2014  Elements in finite classical groups whose powers have large 1-Eigenspaces (with Alice C. Niemeyer). Disc. Math. and Theor. Comp. Sci. 16, 303-312.    arXiv:1405.2385.

 
 
 
CherylPraeger_img.jpeg

Cheryl Praeger

Stephen_Glasby.jpg

Stephen Glasby

 

RESEARCHERS

FURTHER INFORMATION

An Introduction to Computational Group Theory, by Ákos Seress, published in Notices - July 1997, Volume 44, Number 6. It is available in PDF format [22KB]from the Notices website.

 

University of Western Australia, Crawley, Western Australia, 6009

CRICOS Code: 00126G

©2018 by Centre for the Mathematics of Symmetry and Computation. Proudly created with Wix.com