On complexity of matrix scaling

✍ Scribed by Arkadi Nemirovski; Uriel Rothblum

• Book ID: 104156774
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 182 KB
• Volume: 302-303
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(99)00212-8

✦ Synopsis

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 Y AZ. The matrix Balancing problem for a nonegative 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 nonnegative multiindex arrays, can be reduced to a specific Geometric Programming problem. For the latter problem, we develop a polynomialtime 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].