  Computational problem certificates are additional data structures for each
output, which can be used by a-possibly randomized-verification algorithm that
proves the correctness of each output. In this paper, we give an algorithm that
computes a certificate for the minimal polynomial of sparse or structured nxn
matrices over an abstract field, of sufficiently large cardinality, whose Monte
Carlo verification complexity requires a single matrix-vector multiplication
and a linear number of extra field operations. We also propose a novel
preconditioner that ensures irreducibility of the characteristic polynomial of
the generically preconditioned matrix. This preconditioner takes linear time to
be applied and uses only two random entries. We then combine these two
techniques to give algorithms that compute certificates for the determinant,
and thus for the characteristic polynomial, whose Monte Carlo verification
complexity is therefore also linear.
