The density of uncyclic matrices

Publication date 22 May 2014

Abstract: An element

X

in the algebra

m M (n, m a t h b b F)

of all

n i m e s n

matrices over a field

m a t h b b F

is said to be

f

-cyclic if the underlying vector space considered as an

m a t h b b 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

m a t h b b F_{q}

, the proportion of matrices in

m M (n, m a t h b b 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 M (n, m a t h b b F_{q})

for the MeatAxe depends on the degree, showing that it is at least

1 - f r a c 2 q (f r a c 1 q + f r a c 1 q^{2} + f r a c 2 q^{3})^{n}

for

q g e q 4

. We conjecture that the density is at least

1 - f r a c 1 q (f r a c 1 q + f r a c 1 2 q^{2})^{n}

for all

q

and

n

, and confirm this conjecture for dimensions

n l e q 37

. Finally we give a one-sided Monte Carlo algorithm called IsfCyclic to test whether a matrix is `good', at a cost of

m O (m M a t (n) l o g n)

field operations, where

m M a t (n)

is an upper bound for the number of field operations required to multiply two matrices in

m M (n, m a t h b b F_{q})

.

This page was built for publication: The density of uncyclic matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6251727)