The asymptotic complexity of matrix reduction over finite fields

Demetres Christofides

Consider an invertible n \times n matrix over some field. The Gauss-Jordan elimination reduces this matrix to the identity matrix using at most n^2 row operations and in general th…