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
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
0.92198634
0 references
0.90971196
0 references
0 references
0.8814566
0 references
0.8811948
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