Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules

Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, Ákos Seress

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We present a Las Vegas algorithm which, for a given matrix group known to be isomorphic modulo scalars to a finite alternating or symmetric group acting on the fully deleted permutation module, produces an explicit isomorphism with the standard permutation representation of the group. This algorithm exploits information available from the matrix representation and thereby is faster than existing 'black-box' recognition algorithms applied to these groups. In particular, it uses the fact that certain types of elements in these groups can be identified and constructed from the structure of their characteristic polynomials. The algorithm forms part of a large-scale program for computing with groups of matrices over finite fields. When combined with existing 'black-box' recognition algorithms, the results of this paper prove that any d-dimensional absolutely irreducible matrix representation of a finite alternating or symmetric group, over a finite field, can be recognised with O(d1/2) random group elements and O(d1/2) matrix multiplications, up to some logarithmic factors.

Original languageEnglish (US)
Pages (from-to)4-46
Number of pages43
JournalJournal of Algebra
Volume292
Issue number1 SPEC. ISS.
DOIs
StatePublished - Oct 1 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory

Keywords

  • Alternating and symmetric groups
  • Constructive recognition
  • Matrix groups
  • Probabilistic method

Fingerprint

Dive into the research topics of 'Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules'. Together they form a unique fingerprint.

Cite this