  Some fast algorithms for computing the eigenvalues of a block companion
matrix $A = U + XY^H$, where $U\in \mathbb C^{n\times n}$ is unitary block
circulant and $X, Y \in\mathbb{C}^{n \times k}$, have recently appeared in the
literature. Most of these algorithms rely on the decomposition of $A$ as
product of scalar companion matrices which turns into a factored representation
of the Hessenberg reduction of $A$. In this paper we generalize the approach to
encompass Hessenberg matrices of the form $A=U + XY^H$ where $U$ is a general
unitary matrix. A remarkable case is $U$ unitary diagonal which makes possible
to deal with interpolation techniques for rootfinding problems and nonlinear
eigenvalue problems. Our extension exploits the properties of a larger matrix
$\hat A$ obtained by a certain embedding of the Hessenberg reduction of $A$
suitable to maintain its structural properties. We show that $\hat A$ can be
factored as product of lower and upper unitary Hessenberg matrices possibly
perturbed in the first $k$ rows, and, moreover, such a data-sparse
representation is well suited for the design of fast eigensolvers based on the
QR/QZ iteration. The resulting algorithm is fast and backward stable.
