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.