Characterizations of optimal scalings of matrices

A scaling of a non-negative, square matrixA ≠ 0 is a matrix of the formDAD ^?1, whereD is a non-negative, non-singular, diagonal, square matrix. For a non-negative, rectangular matrixB ≠ 0 we define a scaling to be a matrixCBE ^?1 whereC andE are non-negative, non-singular, diagonal, square matrices of the corresponding dimension. (For square matrices the latter definition allows more scalings.) A measure of the goodness of a scalingX is the maximal ratio of non-zero elements ofX. We characterize the minimal value of this measure over the set of all scalings of a given matrix. This is obtained in terms of cyclic products associated with a graph corresponding to the matrix. Our analysis is based on converting the scaling problem into a linear program. We then characterize the extreme points of the polytope which occurs in the linear program.