On the complexity of matrix reduction over finite fields

In this paper we study the complexity of matrix elimination over finite fields in terms of row operations, or equivalently in terms of the distance in the Cayley graph of GLn(Fq) generated by the elementary matrices. We present an algorithm called striped matrix elimination which is asymptotically faster than traditional Gauss–Jordan elimination. The new algorithm achieves a complexity of O(n2/logqn) row operations, and O(n3/logqn) operations in total, thanks to being able to eliminate many matrix positions with a single row operation. We also bound the average and worst-case complexity for the problem, proving that our algorithm is close to being optimal, and show related concentration results for random matrices. Next we present the results of a large computational study of the complexities for small matrices and fields. Here we determine the exact distribution of the complexity for matrices from GLn(Fq), with n and q small. Finally we consider an extension from finite fields to finite semifields of the matrix reduction problem. We give a conjecture on the behaviour of a natural analogue of GLn for semifields and prove this for a certain class of semifields.