Abstract
An n n matrix with nonnegative entries is said to be balanced if for each i = 1,...., n, the sum of the entries of its i-th row is equal to the sum of the entries of its i-th column. An n n matrix A with nonnegative entries is said to be balanceable via diagonal similarity scaling if there exists a diagonal matrix X with positive diagonal entries such that XAX1 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.