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

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.