Random Krylov Spaces over Finite Fields
Richard P. Brent, Shuhong Gao, Alan G. B. Lauder · SIAM Journal on Discrete Mathematics · 2003
Motivated by a connection with block iterative methods for solving linear systems over finite fields, we consider the probability that the Krylov space generated by a fixed linear mapping and a random set of elements in a vector space over a finite field equals the space itself. We obtain an exact formula for this probability and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.