On complexity of matrix scaling

The Line Sum Scaling problem for a nonnegative matrix A is to find positive definite diagonal matrices Y, Z which result in prescribed row and column sums of the scaled matrix YAZ. The matrix Balancing problem for a nonegativ e square matrix A is to find a positive definite diagonal Matrix X such tha t the row sums in the scaled matrix XAX are equal to the corresponding colu mn sums. We demonstrate that epsilon-versions of both these problems, same as those of other scaling problems for nonnegative multiindex arrays, can b e reduced to a specific Geometric Programming problem. For the latter probl em, we develop a polynomial-time algorithm, thus deriving polynomial time s olvability of a number of generic scaling problems for nonnegative multiind ex arrays. Our results extend those previously known for the problems of ma trix balancing [3] and of double-stochastic scaling of a square nonnegative matrix [2]. (C) 1999 Published by Elsevier Science Inc. All rights reserve d.