Bounding the Nullities of Random Block Hankel Matrices: An Alternative Approach
Date
2005-05-10
Authors
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