A Recognition Algorithm for Special Linear Groups (Q4024980)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 120246
Language Label Description Also known as
default for all languages
No label defined
    English
    A Recognition Algorithm for Special Linear Groups
    scientific article; zbMATH DE number 120246

      Statements

      A Recognition Algorithm for Special Linear Groups (English)
      0 references
      0 references
      0 references
      18 February 1993
      0 references
      \(GL(d,q)\)
      0 references
      \(SL(d,q)\)
      0 references
      non-singular \(d\times d\)-matrices
      0 references
      efficient algorithms
      0 references
      subgroups
      0 references
      nearly irreducible elements
      0 references
      complexity
      0 references
      This paper deals with the following question: Suppose \(X\) is a set of non-singular \(d\times d\)-matrices in \(G = GL(d,q)\). Is there an efficient algorithm to decide whether \(S = SL(d,q)\) is a subgroup of \(\langle X\rangle\)? This problem is related to a similar question where \(G\) is replaced by \(Sym(n)\) and \(S\) by \(Alt(n)\) [see \textit{P. Neumann}, Berechnungen in Gruppen (Lect. Notes, ETH Zürich 1987)]. The paper splits into a group theoretic part and a part on computations. In the first part subgroups of \(G\) are determined which contain irreducible and nearly irreducible elements. Here an element is called nearly irreducible if it decomposes the underlying \(d\)-space into two invariant, irreducible spaces of dimensions 1 and \(d-1\). These results overlap in part with some work of the reviewer [Rend. Semin. Mat. Univ. Padova 77, 69-113 (1987; Zbl 0624.20008)]. However the methods used in the paper under review are completely different. Main ingredient is \textit{M. Aschbacher}'s description of subgroups of \(GL(d,q)\) [in Invent. Math. 76, 469-514 (1984; Zbl 0537.20023)]. Together with a detailed study of the action of irreducible and nearly irreducible elements this yields a precise list of groups \(\langle X\rangle\) as above. In part two of the paper an outline for the explicit algorithm of a test on the inclusion of \(S\) in \(\langle X\rangle\) is given. In the first part of this algorithm it is described how suitable irreducible \(x\) and nearly irreducible matrices \(y\) are detected in a given set \(X\). In the second part special procedures are explained which detect groups \(\langle x,y\rangle\) not containing \(S\). The paper also contains a discussion on a priori estimates on the size of \(X\) to guarantee with probability \(1- \varepsilon\) the existence of \(S\). Moreover the complexity of this problem is discussed. Thus far the authors give no practical implementation of their algorithm but promise to do so.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references