Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-30T19:00:18.042Z Has data issue: false hasContentIssue false

Algorithms for matrix groups

Published online by Cambridge University Press:  05 July 2011

By
E. A. O'Brien
Edited by
C. M. Campbell ,
M. R. Quick ,
E. F. Robertson ,
C. M. Roney-Dougal ,
G. C. Smith  and
G. Traustason
E. A. O'Brien
Affiliation:
University of Auckland
C. M. Campbell
Affiliation:
University of St Andrews, Scotland
M. R. Quick
Affiliation:
University of St Andrews, Scotland
E. F. Robertson
Affiliation:
University of St Andrews, Scotland
C. M. Roney-Dougal
Affiliation:
University of St Andrews, Scotland
G. C. Smith
Affiliation:
University of Bath
G. Traustason
Affiliation:
University of Bath
Get access

Summary

Abstract

Existing algorithms have only limited ability to answer structural questions about subgroups G of GL(d, F), where F is a finite field. We discuss new and promising algorithmic approaches, both theoretical and practical, which as a first step construct a chief series for G.

Introduction

Research in Computational Group Theory has concentrated on four primary areas: permutation groups, finitely-presented groups, soluble groups, and matrix groups. It is now possible to study the structure of permutation groups having degrees up to about ten million; Seress [97] describes in detail the relevant algorithms. We can compute useful descriptions for quotients of finitely-presented groups; as one example, O'Brien & Vaughan-Lee [90] computed a power-conjugate presentation for the largest finite 2-generator group of exponent 7, showing that it has order 720416. Practical algorithms for the study of polycyclic groups are described in [59, Chapter 8].

We contrast the success in these areas with the paucity of algorithms to investigate the structure of matrix groups. Let G = 〈X〉 ≤ GL(d, F) where F = GF(q). Natural questions of interest to group-theorists include: What is the order of G? What are its composition factors? How many conjugacy classes of elements does it have? Such questions about a subgroup of Sn, the symmetric group of degree n, are answered both theoretically and practically using highly effective polynomialtime algorithms.

Type
Chapter
Information
Groups St Andrews 2009 in Bath , pp. 297 - 323
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Christine, Altseimer and Alexandre V., Borovik. Probabilistic recognition of orthogonal and symplectic groups. In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 1–20. De Gruyter, Berlin, 2001.Google Scholar
[2] Sophie, Ambrose. Matrix Groups: Theory, Algorithms and Applications. PhD thesis, University of Western Australia, 2006.
[3] M., Aschbacher. On the maximal subgroups of the finite classical groups. Invent. Math. 76, 469–514, 1984.Google Scholar
[4] László, Babai. Local expansion of vertex-transitive graphs and random generation in finite groups. Theory of Computing, (Los Angeles, 1991), pp. 164–174. Association for Computing Machinery, New York, 1991.Google Scholar
[5] László, Babai. Randomization in group algorithms: conceptual questions. In Groups and Computation, II (New Brunswick, NJ, 1995), 1–17, Amer. Math. Soc., Providence, RI, 1–17, 1997.Google Scholar
[6] László, Babai and Endre, Szemerédi. On the complexity of matrix group problems, I. In Proc. 25th IEEE Sympos. Foundations Comp. Sci., pages 229–240, 1984.Google Scholar
[7] László, Babai and Robert, Beals. A polynomial-time theory of black box groups. I. In Groups St. Andrews 1997 in Bath, I, volume 260 of London Math. Soc. Lecture Note Ser., pages 30–64, 1999. Cambridge Univ. Press.Google Scholar
[8] László, Babai, William M., Kantor, Péter P., Pálfy and Ákos, Seress. Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5, 383–401, 2002.Google Scholar
[9] László, Babai, Péter P., Pálfy and Jan, Saxl. On the number of p-regular elements in finite simple groups. LMS J. Comput. Math. 12, 82–119, 2009.Google Scholar
[10] László, Babai, Robert, Beals and Ákos, Seress. Polynomial-time Theory of Matrix Groups. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, pages 55–64, 2009.Google Scholar
[11] Henrik, Bäärnhielm. Algorithmic problems in twisted groups of Lie type. PhD thesis, Queen Mary, University of London, 2006.
[12] Henrik, Bäärnhielm. Recognising the Suzuki groups in their natural representations. J. Algebra 300, 171–198, 2006.
[13] Robert, Beals, Charles R., Leedham-Green, Alice C., Niemeyer, Cheryl E., Praeger and Ákos, Seress. A black-box group algorithm for recognizing finite symmetric and alternating groups. I. Trans. Amer. Math. Soc. 355, 2097–2113, 2003.Google Scholar
[14] Robert, Beals, Charles R., Leedham-Green, Alice C., Niemeyer, Cheryl E., Praeger and Ákos, Seress. Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules. J. Algebra 292, 4–46, 2005.Google Scholar
[15] Alexandre V., Borovik. Centralisers of involutions in black box groups. In Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), 7–20, Contemp. Math., 298, Amer. Math. Soc., Providence, RI, 2002.Google Scholar
[16] Wieb, Bosma, John, Cannon and Catherine, Playoust. The MAGMA algebra system I: The user language. J. Symbolic Comput. 24, 235–265, 1997.Google Scholar
[17] Sergey, Bratus and Igor, Pak. Fast constructive recognition of a black box group isomorphic to Sn or An using Goldbach's conjecture. J. Symbolic Comput. 29, 33–57, 2000.Google Scholar
[18] John N., Bray. An improved method for generating the centralizer of an involution. Arch. Math. (Basel) 74, 241–245, 2000.Google Scholar
[19] John, Bray, M.D.E., Conder, C.R., Leedham-Green and E.A., O'Brien. Short presentations for alternating and symmetric groups. To appear Trans. Amer. Math. Soc. 2010.Google Scholar
[20] John, Brillhart, D.H., Lehmer, J.L., Selfridge, Bryant, Tuckerman, and S.S., Wagstaff Jr., Factorizations of bn ± 1, volume 22 of Contemporary Mathematics. American Mathematical Society, Providence, RI, second edition, 1988. www.cerias.purdue.edu/homes/ssw/cun/index.html.Google Scholar
[21] Peter A., Brooksbank. A constructive recognition algorithm for the matrix group Ω(d, q). In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 79–93. De Gruyter, Berlin, 2001.Google Scholar
[22] Peter A., Brooksbank and William M., Kantor. On constructive recognition of a black box PSL(d, q). In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 95–111. De Gruyter, Berlin, 2001.Google Scholar
[23] Peter A., Brooksbank. Constructive recognition of classical groups in their natural representation. J. Symbolic Comput. 35, 195–239, 2003.Google Scholar
[24] Peter A., Brooksbank. Fast constructive recognition of black-box unitary groups. LMS J. Comput. Math. 6, 162–197, 2003.Google Scholar
[25] Peter, Brooksbank, Alice C., Niemeyer and Ákos, Seress. A reduction algorithm for matrix groups with an extraspecial normal subgroup. Finite Geometries, Groups and Computation, (Colorado), pp. 1–16. De Gruyter, Berlin, 2006.Google Scholar
[26] Peter A., Brooksbank and William M., Kantor. Fast constructive recognition of black box orthogonal groups. J. Algebra 300, 256–288, 2006.Google Scholar
[27] C.M., Campbell, E.F., Robertson and P.D., Williams. On Presentations of PSL (2, pn). J. Austral. Math. Soc. 48, 333–346, 1990.Google Scholar
[28] John J., Cannon. Construction of defining relators for finite groups. Discrete Math. 5, 105–129, 1973.Google Scholar
[29] John, Cannon and Bernd, Souvignier. On the computation of conjugacy classes in permutation groups. In Proceedings of International Symposium on Symbolic and Algebraic Computation, Hawaii, 1997, pages 392–399. Association for Computing Machinery, 1997.Google Scholar
[30] John J., Cannon, Bruce C., Cox and Derek F., Holt. Computing the subgroups of a permutation group. J. Symbolic Comput. 31, 149–161, 2001.Google Scholar
[31] John J., Cannon and Derek F., Holt. Automorphism group computation and isomorphism testing in finite groups. J. Symbolic Comput. 35, 241–267, 2003.Google Scholar
[32] John J., Cannon and Derek F., Holt. Computing maximal subgroups of finite groups. J. Symbolic Comput. 37, 589–609, 2004.Google Scholar
[33] Jon F., Carlson, Max, Neunhöffer and Colva M., Roney-Dougal. A polynomial-time reduction algorithm for groups of semilinear or subfield class. J. Algebra 322, 613–617, 2009.Google Scholar
[34] Frank, Celler, Charles R., Leedham-Green, Scott H., Murray, Alice C., Niemeyer and E.A., O'Brien. Generating random elements of a finite group. Comm. Algebra 23, 4931–4948, 1995.Google Scholar
[35] Frank, Celler and C.R., Leedham-Green. Calculating the order of an invertible matrix. In Groups and Computation II, volume 28 of Amer. Math. Soc. DIMACS Series, pages 55–60. (DIMACS, 1995), 1997.Google Scholar
[36] A.H., Clifford. Representations induced in an invariant subgroup. Ann. of Math. 38, 533–550, 1937.Google Scholar
[37] Marston, Conder and Charles R., Leedham-Green. Fast recognition of classical groups over large fields. In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 113–121. De Gruyter, Berlin, 2001.Google Scholar
[38] M.D.E., Conder, C.R., Leedham-Green and E.A., O'Brien. Constructive recognition of PSL(2, q). Trans. Amer. Math. Soc. 358, 1203–1221, 2006.Google Scholar
[39] Gene, Cooperman. Towards a practical, theoretically sound algorithm for random generation in finite groups. Posted on arXiv:math, May 2002.
[40] Don, Coppersmith and Shmuel, Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9, 251–280, 1990.Google Scholar
[41] Elliot, Costi. Constructive membership testing in classical groups. PhD thesis, Queen Mary, University of London, 2009.
[42] H.S.M., Coxeter and W.O.J., Moser. Generators and Relations for Discrete Groups, 4th ed. Springer-Verlag (Berlin), 1980, ix+169 pp.Google Scholar
[43] A.S., Detinko, B., Eick and D.L., Flannery. Computing with matrix groups over infinite fields. These Proceedings.
[44] John D., Dixon. Generating random elements in finite groups. Electron. J. Combin. 15 (2008), no. 1, Research Paper 94, 13 pp.Google Scholar
[45] Bettina, Eick and Alexander, Hulpke. Computing the maximal subgroups of a permutation group. I. In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 155–168. De Gruyter, Berlin, 2001.Google Scholar
[46] The GAP Group. GAP – Groups, Algorithms, and Programming, Version 4.4.12; 2008. www.gap-system.org.
[47] Mark, Giesbrecht. Nearly optimal algorithms for canonical matrix forms. PhD thesis, University of Toronto, 1993.
[48] S.P., Glasby, C.R., Leedham-Green and E.A., O'Brien. Writing projective representations over subfields. J. Algebra 295, 51–61, 2006.Google Scholar
[49] S.P., Glasby and Cheryl E., Praeger. Towards an efficient MEAT-AXE algorithm using f-cyclic matrices: The density of uncyclic matrices in M(n, q). J. Algebra 322, 766–790, 2009.Google Scholar
[50] Daniel, Gorenstein, Richard, Lyons and Ronald, Solomon. The classification of the finite simple groups. Number 3. American Mathematical Society, Providence, RI, 1998.Google Scholar
[51] Robert, Guralnick, Tim, Penttila, Cheryl E., Praeger and Jan, Saxl. Linear groups with orders having certain large prime divisors. Proc. London Math. Soc. 78, 167–214, 1999.Google Scholar
[52] R.M., Guralnick and F., Lübeck. On p-singular elements in Chevalley groups in characteristic p. In Groups and Computation, III (Columbus, OH, 1999), volume 8 of Ohio State Univ. Math. Res. Inst. Publ., pages 169–182, De Gruyter, Berlin, 2001.Google Scholar
[53] R.M., Guralnick, W.M., Kantor, M., Kassabov and A., Lubotzky. Presentations of finite simple groups: a quantitative approach. J. Amer. Math. Soc. 21, 711–774, 2008.Google Scholar
[54] R.M., Guralnick, W.M., Kantor, M., Kassabov and A., Lubotzky. Presentations of finite simple groups: a computational approach. To appearJ. European Math. Soc., 2010.Google Scholar
[55] G., Hiss and G., Malle. Low-dimensional representations of quasi-simple groups. LMS J. Comput. Math., 4:22–63, 2001. Also: Corrigenda LMS J. Comput. Math.5, 95–126, 2002.Google Scholar
[56] P.E., Holmes, S.A., Linton, E.A., O'Brien, A.J.E., Ryba and R.A., Wilson. Constructive membership in black-box groups. J. Group Theory 11, 747–763, 2008.Google Scholar
[57] Derek F., Holt and Sarah, Rees. Testing modules for irreducibility. J. Austral. Math. Soc. Ser. A 57, 1–16, 1994.Google Scholar
[58] Derek F., Holt, C.R., Leedham-Green, E.A., O'Brien and Sarah, Rees. Computing matrix group decompositions with respect to a normal subgroup. J. Algebra 184, 818–838, 1996.Google Scholar
[59] Derek F., Holt, Bettina, Eick and Eamonn A., O'Brien. Handbook of computational group theory. Chapman and Hall/CRC, London, 2005.Google Scholar
[60] Derek F., Holt and Colva M., Roney-Dougal. Constructing maximal subgroups of classical groups. LMS J. Comput. Math. 8, 46–79, 2005.Google Scholar
[61] Derek F., Holt and Colva M., Roney-Dougal. Constructing maximal subgroups of orthogonal groups. LMS J. Comput. Math. 13, 164–191, 2010.Google Scholar
[62] Alexander, Hulpke and Ákos, Seress. Short presentations for three-dimensional unitary groups. J. Algebra 245, 719–729, 2001.Google Scholar
[63] I.M., Isaacs, W.M., Kantor and N., Spaltenstein. On the probability that a group element is p-singular. J. Algebra 176, 139–181, 1995.Google Scholar
[64] Gábor, Ivanyos and Klaus, Lux. Treating the exceptional cases of the MeatAxe. Experiment. Math. 9, 373–381, 2000.Google Scholar
[65] William M., Kantor and Ákos, Seress. Black box classical groups. Mem. Amer. Math. Soc., 149 (708):viii+168, 2001.Google Scholar
[66] William M., Kantor and Ákos, Seress. Computing with matrix groups. In Groups, Combinatorics & Geometry (Durham, 2001), 123–137, World Sci. Publishing, River Edge, NJ, 2003.Google Scholar
[67] William M., Kantor and Ákos, Seress. Large element orders and the characteristic of Lie-type simple groups. J. Algebra 322, 802–832, 2009.Google Scholar
[68] William M., Kantor and Kay, Magaard. Black box exceptional groups of Lie type. Preprint 2009.
[69] W., Keller-Gehrig. Fast algorithms for the characteristic polynomial. Theoret. Comput. Sci. 36, 309–317, 1985.Google Scholar
[70] Peter, Kleidman and Martin, Liebeck. The subgroup structure of the finite classical groups. London Mathematical Society Lecture Note Series, 129. Cambridge University Press, Cambridge, 1990.
[71] Vicente, Landazuri and Gary M., Seitz. On the minimal degrees of projective representations of the finite Chevalley groups. J. Algebra 32, 418–443, 1974.Google Scholar
[72] C.R., Leedham-Green. The computational matrix group project. In Groups and Computation, III (Columbus, OH, 1999), 229–248. De Gruyter, Berlin, 2001.Google Scholar
[73] C.R., Leedham-Green and E.A., O'Brien. Constructive recognition of classical groups in odd characteristic. J. Algebra 322, 833–881, 2009.Google Scholar
[74] Martin W., Liebeck. On the orders of maximal subgroups of the finite classical groups. Proc. London Math. Soc. (3) 50, 426–446, 1985.Google Scholar
[75] Martin W., Liebeck and Aner, Shalev. The probability of generating a finite simple group. Geom. Ded. 56, 103–113, 1995.Google Scholar
[76] Martin W., Liebeck and E.A., O'Brien. Finding the characteristic of a group of Lie type. J. Lond. Math. Soc. 75, 741–754, 2007.Google Scholar
[77] S.A., Linton. The art and science of computing in large groups. Computational Algebra and Number Theory (Sydney, 1992), pp. 91–109, 1995. Kluwer Academic Publishers, Dordrecht.Google Scholar
[78] F., Lübeck. Small degree representations of finite Chevalley groups in defining characteristic. LMS J. Comput. Math. 4, 135–169, 2001.Google Scholar
[79] F., Lübeck, K., Magaard and E.A., O'Brien. Constructive recognition of SL3 (p). J. Algebra 316, 619–633, 2007.Google Scholar
[80] Frank, Lübeck, Alice C., Niemeyer and Cheryl E., Praeger. Finding involutions in finite Lie type groups of odd characteristic. J. Algebra 321, 3397–3417, 2009.Google Scholar
[81] Eugene M., Luks. Computing in solvable matrix groups. In Proc. 33rd IEEE Sympos. Foundations Comp. Sci., 111–120, 1992.Google Scholar
[82] Kay, Magaard, E.A., O'Brien and Ákos, Seress. Recognition of small dimensional representations of general linear groups. J. Aust. Math. Soc. 85, 229–250, 2008.Google Scholar
[83] E.H., Moore. Concerning the abstract groups of order k! and ½ k!. Proc. London Math. Soc. 28, 357–366, 1897.Google Scholar
[84] Peter M., Neumann and Cheryl E., Praeger. A recognition algorithm for special linear groups. Proc. London Math. Soc. (3), 65, 555–603, 1992.Google Scholar
[85] Max, Neunhöffer and Ákos, Seress. A data structure for a uniform approach to computations with finite groups. In Proceedings of ISSAC 2006, ACM, New York, 2006, pp. 254–261.Google Scholar
[86] Max, Neunhöffer. Constructive Recognition of Finite Groups. Habilitationsschrift, RWTH Aachen, 2009.Google Scholar
[87] Max, Neunhöffer and Cheryl E., Praeger. Computing minimal polynomials of matrices. LMS J. Comput. Math. 11, 252–279, 2008.Google Scholar
[88] Alice C., Niemeyer and Cheryl E., Praeger. A recognition algorithm for classical groups over finite fields. Proc. London Math. Soc., 77:117–169, 1998.Google Scholar
[89] Alice C., Niemeyer. Constructive recognition of normalisers of small extra-special matrix groups. Internat. J. Algebra Comput., 15, 367–394, 2005.Google Scholar
[90] E.A., O'Brien and M.R., Vaughan-Lee. The 2-generator restricted Burnside group of exponent 7. Internat. J. Algebra Comput., 12, 575–592, 2002.Google Scholar
[91] E.A., O'Brien. Towards effective algorithms for linear groups. Finite Geometries, Groups and Computation, (Colorado), pp. 163–190. De Gruyter, Berlin, 2006.Google Scholar
[92] Igor, Pak. The product replacement algorithm is polynomial. In 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000), 476–485, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000.Google Scholar
[93] Christopher W., Parker and Robert A., Wilson. Recognising simplicity of black-box groups by constructing involutions and their centralisers. To appear J. Algebra, 2010.Google Scholar
[94] Cheryl E., Praeger. Primitive prime divisor elements in finite classical groups. In Groups St. Andrews 1997 in Bath, II, 605–623, Cambridge University Press, 1999.Google Scholar
[95] Alexander J.E., Ryba. Identification of matrix generators of a Chevalley group. J. Algebra 309, 484–496, 2007.Google Scholar
[96] Gary M., Seitz and Alexander E., Zalesskii. On the minimal degrees of projective representations of the finite Chevalley groups. II. J. Algebra 158, 233–243, 1993.
[97] Ákos, Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003.
[98] Igor E., Shparlinski. Finite fields: theory and computation. The meeting point of number theory, computer science, coding theory and cryptography. Mathematics and its Applications, 477. Kluwer Academic Publishers, Dordrecht, 1999.Google Scholar
[99] Charles C., Sims. Computational methods in the study of permutation groups. In Computational problems in abstract algebra (Proc. Conf., Oxford, 1967), pages 169–183, Pergamon Press, Oxford, 1970.Google Scholar
[100] V., Strassen. Gaussian elimination is not optimal. Numer. Math. 13, 354–356, 1969.Google Scholar
[101] Joachim von zur, Gathen and Jürgen, Gerhard. Modern Computer Algebra, Cambridge University Press, 2002.Google Scholar
[102] G.E., Wall. On the conjugacy classes in the unitary, symplectic and orthogonal groups. J. Austral. Math. Soc. 3, 1–62, 1963.Google Scholar
[103] Robert A., Wilson. Standard generators for sporadic simple groups. J. Algebra 184, 505–515, 1996.Google Scholar
[104] R.A., Wilsonet al. ATLAS of Finite Group Representations. brauer.maths.qmul.ac.uk/Atlas.
[105] R.A., Wilson. Computing in the Monster. In Groups, Combinatorics & Geometry (Durham, 2001), 327–335, World Sci. Publishing, River Edge, NJ, 2003.Google Scholar
[106] Şükrü, Yalçinkaya. Black box groups. Turkish J. Math. 31, 171–210, 2007.Google Scholar
[107] K., Zsigmondy. Zur Theorie der Potenzreste. Monatsh. für Math. u. Phys. 3, 265–284, 1892.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×