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

This is a continuation of research of the meat-axe algorithm using \(f\)-cyclic matrices, see \textit{S. P. Glasby} [J. Algebra 300, No.~1, 77--90 (2006; Zbl 1108.15015)]. The lower and upper bounds for the density of uncyclic matrices in \(\text{M}(n,\mathbb{F}_q)\) are obtained. The authors give a practical Monte Carlo algorithm to test whether a given matrix is \(f\)-cyclic relative to some irreducible divisor of its characteristic polynomial. Also the algorithm outputs a witness vector which can be used when applying Norton's irreducibility test; see \textit{D. F. Holt} and \textit{S. Rees} [J. Aust. Math. Soc., Ser. A 57, No.~1, 1--16 (1994; Zbl 0833.20021)]. The work is written understandable for nonspecialists; the references to available programs are present.