Bounding the Nullities of Random Block Hankel Matrices: An Alternative Approach

Date
2005-05-10
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Bounds are developed for the probability that various randomly generated block Hankel matrices are rank-deficient. These bounds are potentially of use to analyze the efficiency and reliability of various randomized block Wiedemann and block Lanczos algorithms, that are either currently under development or now in use, when these are applied to solve systems of linear equations and sample from the null space of matrices over small finite fields. The bounds that are presented here resemble ones that have previously been obtained using other arguments or that could likely be obtained by straightforward extensions of arguments that have recently been presented. The method used to obtain these bounds in this report is rather different and may be of some interest in its own right: It relies only on estimates of the number of irreducible polynomials of a given degree over a finite field and on elementary linear algebra.
Description
Keywords
Computer Science
Citation