Testing matrix groups for primitivity (Q1815003)

The authors describe an algorithm which seeks to decide whether or not a given irreducible matrix group of finite dimension defined over a finite field preserves a nontrivial system of blocks of imprimitivity in its action on the underlying vector space. In most cases the algorithm will either find at least one block system, or it will prove that the group acts primitively. In some instances however, it may find that the group is semilinear over an extension field before resolving the (im)primitivity problem, in which case it does not conclusively settle the question of (im)primitivity. The algorithm presented is a contribution to the `recognition project' for matrix groups defined over finite fields. The authors aimed to design a `practical' algorithm capable of dealing with matrix groups of dimension up to about 100 over fields of moderate size. Implementations of the algorithm are publicly available in the computer algebra systems GAP and MAGMA.