Structured strong linearizations from Fiedler pencils with repetition I

In many applications, the polynomial eigenvalue problem, P(λ)x=0, arises with P(λ) being a structured matrix polynomial (for example, palindromic, symmetric, skew-symmetric). In order to solve a structured polynomial eigenvalue problem it is convenient to use strong linearizations with the same structure as P(λ) to ensure that the symmetries in the eigenvalues due to that structure are preserved in numerical computations. In this paper we characterize all the pencils in the family of the Fiedler pencils with repetition, introduced by Vologiannidis and Antoniou [25], associated with a square matrix polynomial P(λ) that are block-symmetric for every matrix polynomial P(λ). We show that this family of pencils is precisely the set of all Fiedler pencils with repetition that are symmetric when P(λ) is. When some generic nonsingularity conditions are satisfied, these pencils are strong linearizations of P(λ). In particular, our family strictly contains the standard basis for DL(P), a k-dimensional vector space of symmetric pencils introduced by Mackey, Mackey, Mehl, and Mehrmann [20].