A new look at the optimal assignment problem

AbstractLet E=[eij] be a matrix with integral elements. We study matrices of the form X=[eeij], where x is an indeterminate defined over the rational field Q. There is a fascinating interplay between the combinatorial structures of the matrices E and X. For example, in the case of square matrices the number of optimal assignments in the matrix E is precisely the coefficient of the term of highest degree in the polynomial per(X). We allow the multiplication of rows and columns of X by arbitrary integral powers of x, and we study topics such as the diagonal products of X. We apply certain familiar results to this “exponential” setting, and we also introduce some new concepts, such as the class of matrices S(X) generated by a matrix X and the notion of an invariant 1 within such a class