  The problem of finding the distance from a given $n \times n$ matrix
polynomial of degree $k$ to the set of matrix polynomials having the elementary
divisor $(\lambda-\lambda_0)^j, \, j \geqslant r,$ for a fixed scalar
$\lambda_0$ and $2 \leqslant r \leqslant kn$ is considered. It is established
that polynomials that are not regular are arbitrarily close to a regular matrix
polynomial with the desired elementary divisor. For regular matrix polynomials
the problem is shown to be equivalent to finding minimal structure preserving
perturbations such that a certain block Toeplitz matrix becomes suitably rank
deficient. This is then used to characterize the distance via two different
optimizations. The first one shows that if $\lambda_0$ is not already an
eigenvalue of the matrix polynomial, then the problem is equivalent to
computing a generalized notion of a structured singular value. The distance is
computed via algorithms like BFGS and Matlab's globalsearch algorithm from the
second optimization. Upper and lower bounds of the distance are also derived
and numerical experiments are performed to compare them with the computed
values of the distance.
