  One useful standard method to compute eigenvalues of matrix polynomials ${\bf
P}(z) \in \mathbb{C}^{n\times n}[z]$ of degree at most $\ell$ in $z$ (denoted
of grade $\ell$, for short) is to first transform ${\bf P}(z)$ to an equivalent
linear matrix polynomial ${\bf L}(z)=z{\bf B}-{\bf A}$, called a companion
pencil, where ${\bf A}$ and ${\bf B}$ are usually of larger dimension than
${\bf P}(z)$ but ${\bf L}(z)$ is now only of grade $1$ in $z$. The eigenvalues
and eigenvectors of ${\bf L}(z)$ can be computed numerically by, for instance,
the QZ algorithm. The eigenvectors of ${\bf P}(z)$, including those for
infinite eigenvalues, can also be recovered from eigenvectors of ${\bf L}(z)$
if ${\bf L}(z)$ is what is called a "strong linearization" of ${\bf P}(z)$.
  In this paper we show how to use algorithms for computing the Hermite Normal
Form of a companion matrix for a scalar polynomial to direct the discovery of
unimodular matrix polynomial cofactors ${\bf E}(z)$ and ${\bf F}(z)$ which, via
the equation ${\bf E}(z){\bf L}(z){\bf F}(z) = \mathrm{diag}( {\bf P}(z), {\bf
I}_n, \ldots, {\bf I}_n)$, explicitly show the equivalence of ${\bf P}(z)$ and
${\bf L}(z)$. By this method we give new explicit constructions for several
linearizations using different polynomial bases. We contrast these new
unimodular pairs with those constructed by strict equivalence, some of which
are also new to this paper. We discuss the limitations of this experimental,
computational discovery method of finding unimodular cofactors.
