Block LU factors of generalized companion matrix pencils

We present formulas for computations involving companion matrix pencils as may arise in considering polynomial eigenvalue problems. In particular, we provide explicit companion matrix pencils for matrix polynomials expressed in a variety of polynomial bases including monomial, orthogonal, Newton, Lagrange, and Bernstein/Bezier bases. Additionally, we give a pair of explicit LU factors associated with each pencil and a prescription for block pivoting when required.