## Abstract

Efficient methods for computing with matrices over finite fields often involve randomised algorithms, where matrices with a certain property are sought via repeated random selection. Complexity analyses for such algorithms require knowledge of the proportion of relevant matrices in the ambient group or algebra. We introduce a method for estimating proportions of families N of elements in the algebra of all d × d matrices over a field of order q, where membership of a matrix in N depends only on its 'invertible part'. The method is based on the availability of estimates for proportions of certain non-singular matrices depending on N, so that existing estimation techniques for non-singular matrices can be used to deal with families containing singular matrices. As an application, we investigate primary cyclic matrices, which are used in the Holt-Rees MEATAXE algorithm for testing irreducibility of matrix algebras.

Original language | English |
---|---|

Pages (from-to) | 404-418 |

Number of pages | 15 |

Journal | LMS Journal of Computation and Mathematics |

Volume | 18 |

Issue number | 1 |

DOIs | |

Publication status | Published - 10 Apr 2015 |

Externally published | Yes |