©2016 American Mathematical SocietyVarious generalizations of companion matrices to companion pencils are presented. Companion matrices link to monic polynomials, whereas companion pencils do not require monicity of the corresponding polynomial. In the classical companion pencil case (A, B) only the coefficient of the highest degree appears in B’s lower right corner. We will show, however, that all coefficients of the polynomial can be distributed over both A and B creating additional flexibility. Companion matrices admit a so-called Fiedler factorization into essentially 2 × 2 matrices. These Fiedler factors can be reordered without affecting the eigenvalues (which equal the polynomial roots) of the assembled matrix. We will propose a generalization of this factorization and the reshuffling property for companion pencils. Special examples of the factorizations and extensions to matrix polynomials and product eigenvalue problems are included.