Classes of matrices associated with the optimal assignment problem |
| |
Affiliation: | Department of Mathematics University of Wisconsin Madison, Wisconsin 53706, USA;Department of Mathematics California Institute of Technology Pasadena, California 91125, USA |
| |
Abstract: | Let E=[eij] be a matrix with integral elements, and let x be an indeterminate defined over the rational field Q. We investigate matrices of the form X=[xeij] (i = 1,…, m; j = 1,…, n; m ⩽ n). We may multiply the lines (rows or columns) of the matrix X by suitable integral powers of x in various ways and thereby transform X into a matrix Y=[xfij] such that the fij are nonnegative integers and each line of Y contains at least one element x0 = 1. We call Y a normalized form of X, and we denote by S(X) the class of all normalized forms associated with a given matrix X. The classes S(X) have a fascinating combinatorial structure, and the present paper is a natural outgrowth and extension of an earlier study. We introduce new concepts such as an elementary transformation called an interchange. We prove, for example, that two matrices in the same class are transformable into one another by interchanges. Our analysis of the class S(X) also yields new insights into the structure of the optimal assignments of the matrix E by way of the diagonal products of the matrix X. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|