کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4586698 1334110 2009 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Towards an efficient Meat-axe algorithm using f-cyclic matrices: The density of uncyclic matrices in M(n,q)
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algebra - Volume 322, Issue 3, 1 August 2009, Pages 766-790