  Blackbox algorithms for linear algebra problems start with projection of the
sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence
of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such
algorithms usually depend on the minimal polynomial of the resulting sequence
being that of the given matrix. Here exact formulas are given for the
probability that this occurs. They are based on the generalized Jordan normal
form (direct sum of companion matrices of the elementary divisors) of the
matrix. Sharp bounds follow from this for matrices of unknown elementary
divisors. The bounds are valid for all finite field sizes and show that a small
blocking factor can give high probability of success for all cardinalities and
matrix dimensions.
