Given a matrix group $G$ by its generators i.e. $G =\langle A\_1,A\_2,...,A\_k \rangle \leq GL\_n(q)$, where each $A\_i$'s are matrix in $GL\_n(q)$



> 
> **Q.** Does there exist a polynomial time (polynomial in input size) algorithm to find a minimal normal subgroup of $G$ if it exists otherwise it returns $G$ is simple?
> 
> 
> 


There is an algorithm when group is given by permutation representation. Kindly share any reference if there is such algorithm for matrix group representation.


Thank you!



Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
In the paper



```
Holt, D., Leedham-Green, C. R., & O'Brien EA (2020). Constructing composition factors for a linear group in polynomial time. JOURNAL OF ALGEBRA, 561, 215-236. 10.1016/j.jalgebra.2020.02.018 

```

the authors consider the question of finding a composition series of a subgroup of ${\rm GL}(n,q)$ - I think that finding a minimal normal subgroup is of the same difficulty.


There is lots of earlier literature on this topic: Babai and various co-authors have made many theoretical contributions. The paper by Holt, Leedham-Green and O'Brien is geared more towards finding practical algorithms, and the $\mathtt{CompositionTree}$ function in Magma is very effective and improving all the time.


To have any chance of an affirmative answer to the question, you need to assume the availability of certain oracles. If your group is a cyclic subgroup of ${\rm GL}(n,q)$ of order dividing $q^n-1$, then you need to be able to factorize $q^n-1$ to proceed. There are also simple examples of subgroups of ${\rm GL}(2n,q)$ in which you need a discrete log oracle to decide whether the given group is $C\_p$ or $C\_p \times C\_p$ for a prime $p$ dividing $q^n-1$.


The current situation is that, subject to the availability of certain oracles, there is a polynomial-time Las Vegas algorithm to find a composition series of the group provided that it has no composition factors isomorphic to $^2B\_2(2^{2k+1})$, $^2F\_4(2^{2k+1})$, $^3D\_4(2^k)$, or $^2G\_2(3^{2k+1})$ for any $k$.


The problem with these families of exceptional groups is that there is currently no known polynomial-time constructive recognition algorithm, and it is to be hoped that this situation will be remedied in the future. But the case $^2G\_2(3^{2k+1})$ (Ree groups) looks particularly challenging.


Incidentally, the need for the oracles rarely if ever results in bottlenecks in practical calculations, mainly because of the amount of effort that has gone into finding effective implementations of the discrete log and integer factorization problems.


