Towards an efficient Meat-axe algorithm using f-cyclic matrices: The density of uncyclic matrices in M(n,q)

An element X in the algebra M(n,F) of all n×n matrices over a field F is said to be f-cyclic if the underlying vector space considered as an F[X]-module has at least one cyclic primary component. These are the matrices considered to be “good” in the Holt–Rees version of Norton's irreducibility test in the Meat-axe algorithm. We prove that, for any finite field Fq, the proportion of matrices in M(n,Fq) that are “not good” decays exponentially to zero as the dimension n approaches infinity. Turning this around, we prove that the density of “good” matrices in M(n,Fq) for the Meat-axe depends on the degree, showing that it is at least for q⩾4. We conjecture that the density is at least for all q and n, and confirm this conjecture for dimensions n⩽37. Finally we give a one-sided Monte Carlo algorithm called IsfCyclic to test whether a matrix is “good,” at a cost of O(Mat(n)logn) field operations, where Mat(n) is an upper bound for the number of field operations required to multiply two matrices in M(n,Fq).