On the Complexity of Matrix Balancing
Bahman Kalantari, Leonid Khachiyan, A. Shokoufandeh · SIAM Journal on Matrix Analysis and Applications · 1997
An $n \times n$ matrix with nonnegative entries is said to be $balanced$ if for each $i=1,\dots,n$ the sum of the entries of its ith row is equal to the sum of the entries of its ith column. An $n \times n$ matrix A with nonnegative entries is said to be $balancable$ $via$ $diagonal$ $similarity$ $scaling$ if there exists a diagonal matrix X with positive diagonal entries such that $XAX^{-1}$ is balanced. We give upper and lower bounds on the entries of X and prove the necessary sensitivity analysis in the required accuracy of the minimization of an associated convex programming problem. These results are used to prove the polynomial-time solvability of computing X to any prescribed accuracy.