A practical model for computation with matrix groups.
In computational problems with finite groups, typically the group \(G\) is described very economically by providing a set of generators of \(G\) from some larger well-known group; for example, the generators are permutations from a symmetric group, or matrices from a general linear group over a finite field. The object is then to use this description to determine various group theoretic properties of \(G\) such as: order, Sylow subgroups, solvability, simplicity, etc. In the 1960s Charles Sims introduced the idea of a basis and strong generating set to deal with (what were then) very large groups. This technique is based on the existence of a chain of subgroups of \(G\) in which successive indices are small compared to the size of the group. When \(G\) is a permutation group, such subgroup chains occur naturally by computing stabilizers, and Sims' ideas have been central in computing with such groups. For matrix groups, however, Sims' method will often fail because there is no suitable subgroup chain; for example, in some matrix groups, every maximal subgroup has a large index. This has led to the ``matrix group recognition program [see \textit{C. R. Leedham-Green}, in: Groups and computation III. Proceedings of the international conference at the Ohio State University, Columbus, OH, USA, 1999. Berlin: Walter de Gruyter. Ohio State Univ. Math. Res. Inst. Publ. 8, 229-247 (2001; Zbl 1052.20034)] in which the subgroup chain is replaced by a subnormal subgroup chain and recognizing the factor groups plays a central role. In the present paper, the authors define a composition tree for \(G\) to be a full binary tree whose vertices are labelled by subnormal sections of \(G\). The root is labelled \(G\) and a non-leaf node labelled \(H\), say, has two children \(H_0\) and \(H_1\) and an associated exact sequence \(H_0\hookrightarrow H\twoheadrightarrow H_1\). The tree is constructed recursively and the data structure used enables rewriting in sections of \(G\). The process of constructing a composition tree for a characteristic series for \(G\) uses detailed knowledge about the simple groups and their automorphisms. The algorithms and their implementation incorporate work of many authors, and the technical details are involved. The algorithms have been implemented in MAGMA, and the paper ends by describing how well the program works in solving some challenge problems.
- scientific article; zbMATH DE number 1981751
- Complexity and computation in matrix groups.
- Computing in Nilpotent Matrix Groups
- Computing with matrix groups over infinite fields.
- A unified approach to computations with permutation and matrix groups.
- scientific article; zbMATH DE number 475364
- scientific article; zbMATH DE number 1256646
- scientific article; zbMATH DE number 5976624
- A computer-assisted analysis of some matrix groups.
- A data structure for a uniform approach to computations with finite groups
- A polynomial-time reduction algorithm for groups of semilinear or subfield class.
- A Recognition Algorithm For Classical Groups Over Finite Fields
- A Reduction Algorithm for Large-Base Primitive Permutation Groups
- Algorithms for the Tits alternative and related problems.
- An improved method for generating the centralizer of an involution
- Black box classical groups.
- Black box exceptional groups of Lie type.
- Black-box recognition of finite simple groups of Lie type by statistics of element orders
- Chains of Subgroups in Groups of Lie Type III
- Chains of subgroups in symmetric groups
- Computing a chief series and the soluble radical of a matrix group over a finite field.
- Computing conjugacy classes of elements in matrix groups.
- Computing in groups of Lie type
- Computing matrix group decompositions with respect to a normal subgroup
- Computing minimal polynomials of matrices
- Construction of defining relators for finite groups
- Constructive homomorphisms for classical groups.
- Constructive membership in black-box groups
- Constructive membership testing in black-box classical groups.
- Constructive recognition of \(\text{SL}_3(q)\).
- Constructive recognition of classical groups in even characteristic.
- Constructive recognition of classical groups in odd characteristic.
- CONSTRUCTIVE RECOGNITION OF NORMALIZERS OF SMALL EXTRA-SPECIAL MATRIX GROUPS
- Constructive recognition of 𝑃𝑆𝐿(2,𝑞)
- Constructive Sylow theorems for the classical groups.
- ESTIMATION AND COMPUTATION WITH MATRICES OVER FINITE FIELDS
- Fast constructive recognition of a black box group isomorphic to \(S_n\) or \(A_n\) using Goldbach's conjecture
- Fast constructive recognition of black box orthogonal groups.
- Fast constructive recognition of black box symplectic groups.
- Fast Constructive Recognition of Black-Box Unitary Groups
- Fast recognition of alternating groups of unknown degree.
- Finding the characteristic of a group of Lie type
- Generating Finite Completely Reducible Linear Groups
- Generating random elements of a finite group
- scientific article; zbMATH DE number 5976624 (Why is no real title available?)
- scientific article; zbMATH DE number 3884354 (Why is no real title available?)
- scientific article; zbMATH DE number 3906699 (Why is no real title available?)
- scientific article; zbMATH DE number 1187240 (Why is no real title available?)
- scientific article; zbMATH DE number 46357 (Why is no real title available?)
- scientific article; zbMATH DE number 108109 (Why is no real title available?)
- scientific article; zbMATH DE number 194089 (Why is no real title available?)
- scientific article; zbMATH DE number 1284153 (Why is no real title available?)
- scientific article; zbMATH DE number 475356 (Why is no real title available?)
- scientific article; zbMATH DE number 682071 (Why is no real title available?)
- scientific article; zbMATH DE number 1004929 (Why is no real title available?)
- scientific article; zbMATH DE number 2133330 (Why is no real title available?)
- scientific article; zbMATH DE number 1361739 (Why is no real title available?)
- scientific article; zbMATH DE number 1370596 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 5043412 (Why is no real title available?)
- Large element orders and the characteristic of Lie-type simple groups.
- Matrix generators for exceptional groups of Lie type
- Minimal and random generation of permutation and matrix groups.
- On the maximal subgroups of the finite classical groups
- Polynomial-time theory of matrix groups
- Presentations of finite simple groups: a quantitative approach.
- Recognising Tensor Products of Matrix Groups
- Recognising tensor-induced matrix groups.
- Recognising the small Ree groups in their natural representations.
- Recognising the Suzuki groups in their natural representations.
- Recognition of finite exceptional groups of Lie type.
- RECOGNITION OF SMALL DIMENSIONAL REPRESENTATIONS OF GENERAL LINEAR GROUPS
- Recognizing finite matrix groups over infinite fields.
- Recognizing simplicity of black-box groups and the frequency of p-singular elements in affine groups.
- Short presentations for alternating and symmetric groups
- Short presentations for finite groups
- Standard generators for sporadic simple groups
- Testing matrix groups for primitivity
- The computational matrix group project.
- The expected number of random elements to generate a finite group.
- The Magma algebra system. I: The user language
- Towards effective algorithms for linear groups.
- Treating the Exceptional Cases of the MeatAxe
- Writing projective representations over subfields.
- A new method for recognising Suzuki groups
- Regular orbits of sporadic simple groups
- Selecting base points for the Schreier-Sims algorithm for matrix groups
- The use of permutation representations in structural computations in large finite matrix groups
- Constructing composition factors for a linear group in polynomial time
- Presentations on standard generators for classical groups
- Linear groups and computation
- A note on involution centralizers in black box groups
- Computing conjugacy classes of elements in matrix groups.
- A computer-assisted analysis of some matrix groups.
- Groups with a solvable subgroup of prime-power index
- Lengths of involutions in finite Coxeter groups
- Recognition of absolutely irreducible matrix groups that are tensor decomposable or induced
- The computational matrix group project.
- Constructing all composition series of a finite group.
- Regular orbits of symmetric and alternating groups
- Computing a chief series and the soluble radical of a matrix group over a finite field.
- scientific article; zbMATH DE number 5976624 (Why is no real title available?)
- Computing in Nilpotent Matrix Groups
- Recognising the small Ree groups in their natural representations.
- scientific article; zbMATH DE number 1302483 (Why is no real title available?)
- scientific article; zbMATH DE number 475364 (Why is no real title available?)
- scientific article; zbMATH DE number 1981751 (Why is no real title available?)
- How programming was used to determine factorizations of self-similar groups associated to the first Grigorchuk group
- Effective black-box constructive recognition of classical groups.
- Orbit Computation for Atomically Generated Subgroups of Isometries of $\mathbb{Z}^n$
- scientific article; zbMATH DE number 7196252 (Why is no real title available?)
- Automorphism group orbits on finite simple groups
- Gaussian elimination in split unitary groups with an application to public-key cryptography
- Proving infinite index for a subgroup of matrices
- Practical Computation with Linear Groups Over Infinite Domains
- On soluble subgroups of sporadic groups
- Calculating subgroups with GAP
- On the depth of subgroups of simple groups
- Computational group theory. Abstracts from the workshop held June 1--6, 2025
- Computational group theory: bedrock and new frontiers
- The maximal subgroups of the monster
- Identification of matrix generators of a Chevalley group.
This page was built for publication: A practical model for computation with matrix groups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q480641)
