The density of uncyclic matrices

Abstract

An element $X$ in the algebra $\mathrm{M}(n,\mathbb{F})$ of all $n\times n$ matrices over a field $\mathbb{F}$ is said to be $f$-cyclic if the underlying vector space considered as an $\mathbb{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 MeatAxe algorithm. We prove that, for any finite field ${\mathbb{F}}_q$, the proportion of matrices in $\mathrm{M}(n,{\mathbb{F}}_q)$ 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 $\mathrm{M}(n,{\mathbb{F}}_q)$ for the MeatAxe depends on the degree, showing that it is at least $1-\frac{2}{q}(\frac{1}{q}+\frac{1}{q^2}+\frac{2}{q^3}{)}^n$ for $q\ge 4$. We conjecture that the density is at least $1-\frac{1}{q}(\frac{1}{q}+\frac{1}{2q^2}{)}^n$ for all $q$ and $n$, and confirm this conjecture for dimensions $n\le 37$. Finally we give a one-sided Monte Carlo algorithm called IsfCyclic to test whether a matrix is `good', at a cost of $\mathrm{O}(\mathrm{Mat}(n)\log n)$ field operations, where $\mathrm{Mat}(n)$ is an upper bound for the number of field operations required to multiply two matrices in $\mathrm{M}(n,{\mathbb{F}}_q)$.

30 pages, 1 figure