Companion based matrix functions: description and minimal factorization

Companion based matrix functions are rational matrix functions admitting a minimal realization involving state space matrices that are first companions. Necessary and sufficient conditions are given for a rational matrix function to be companion based. Minimal factorization of such functions is discussed in detail. It is shown that the property of being companion based is hereditary with respect to minimal factorization. Also, the issue of minimal factorization is reduced to a division problem for pairs of monic polynomials of the same degree. In this context, a connection with the Euclidean algorithm is made. The results apply to canonical Wiener-Hopf factorization as well as to complete factorization. The analysis of the latter leads to a combinatorial problem involving the eigenvalues of the state space matrices. The algorithmic aspects of this problem are intimately related to the two machine flow shop problem and Johnson's rule from job scheduling theory