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

JOURNAL OF ALGEBRA

卷:322

Article

Glasby, S. P.¹  Praeger, Cheryl E.² 

[1] Cent Washington Univ, Dept Math, Ellensburg, WA 98926 USA

[2] Univ Western Australia, Sch Math & Stat, Crawley, WA 6009, Australia

关键词: MEAT-AXE;    f-Cyclic;    Uncyclic;    Algorithm;    Complexity analysis;   

DOI  :  10.1016/j.jalgebra.2009.02.021

来源: Elsevier

【 摘 要 】

An element X in the algebra M(n, F) of all n x n matrices over a field IF is said to be f-cyclic if the underlying vector space considered as an F vertical bar X vertical bar-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, 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 M(n. F(q)) for the MEAT-AXE depends oil the degree, showing that it is at least 1 - 2/q (1/q + 1/q(2) + 2/q(3))(n) for q >= 4. We conjecture that the density is at least 1 - 1/q + 1/2q(2))(n) for all q and n, and confirm this conjecture for dimensions n 37. Finally we give a one-sided Monte Carlo algorithm called Is f CYCLIC to test whether a matrix is good, at a cost of O(Mat(n) log n) field operations, where Mat(n) is an upper bound for the number of held operations required to multiply two matrices in M(n, F(q)). Published by Elsevier Inc.

【 授权许可】

Free