  We solve the problem of characterizing the existence of a polynomial matrix
of fixed degree when its eigenstructure (or part of it) and some of its rows
(columns) are prescribed. More specifically, we present a solution to the row
(column) completion problem of a polynomial matrix of given degree under
different prescribed invariants: the whole eigenstructure, all of it but the
row (column) minimal indices, and the finite and/or infinite structures.
Moreover, we characterize the existence of a polynomial matrix with prescribed
degree and eigenstructure over an arbitrary field.
