2014/06/23 by Demetres Christofides, Christofides, Demetres
Computer Science · Engineering · Mathematics · #05A16 #15A09 #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #cs.DS #graph theory and CDMA systems #math.CO #msc:05A16 #msc:15A09
paper · pdf · doi:10.48550/arxiv.1406.5826
arxiv created 2014/06/23 · openalex publication_date 2014/06/23 · arxiv updated 2014/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Consider an invertible n × n matrix over some field. The Gauss-Jordan elimination reduces this matrix to the identity matrix using at most n2 row operations and in general that many operations might be needed. In [1] the authors considered matrices in GL(n;q), the set of n × n invertible matrices in the finite field of q elements, and provided an algorithm using only row operations which performs asymptotically better than the Gauss-Jordan elimination. More specifically their `striped elimination algorithm' has asymptotic complexity \fracn2logqn. Furthermore they proved that up to a constant factor this algorithm is best possible as almost all matrices in GL(n;g) need asymptotically at least \fracn22logqn operations. In this short note we show that the `striped elimination algorithm' is asymptotically optimal by proving that almost all matrices in GL(n;q) need asymptotically at least fracn2logqn operations.