On complexity of matrix scaling Original Research Article

Line Sun 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 nonnegative square matrix A is to find a positive definite diagonal matrix X such that the row sums in the scaled matrix XAX are equal to the corresponding column sums. We demonstrate that ε-versions of both these problems, same as those of other scaling problems for non-negative multiindex arrays, can be reduced to a specific Geometric Programming problem. For the latter problem, we develop a polynomial-time algorithm, thus deriving polynomial time solvability of a number of generic scaling problems for nonnegative multiindex arrays. Our results extend those previously known for the problems of matrix balancing [3] and of double-stochastic scaling of a square nonnegative matrix [2].