### Abstract

An n X n matrix with nonnegative entries is said to be balanced if for each i = 1, . . . , n the sum of the entries of its ith row is equal to the sum of the entries of its ith column. An n x 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.

Original language | English (US) |
---|---|

Pages (from-to) | 450-463 |

Number of pages | 14 |

Journal | SIAM Journal on Matrix Analysis and Applications |

Volume | 18 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1997 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Analysis

### Keywords

- Eigenvalue problems
- Line-sum-symmetric scaling
- Matrix balancing
- Matrix preconditioning
- Nonnegative matrices
- Polynomial-time solvability

### Cite this

*SIAM Journal on Matrix Analysis and Applications*,

*18*(2), 450-463. https://doi.org/10.1137/S0895479895289765

}

*SIAM Journal on Matrix Analysis and Applications*, vol. 18, no. 2, pp. 450-463. https://doi.org/10.1137/S0895479895289765

**On the complexity of matrix balancing.** / Kalantari, B.; Khachiyan, L.; Shokoufandeh, A.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On the complexity of matrix balancing

AU - Kalantari, B.

AU - Khachiyan, L.

AU - Shokoufandeh, A.

PY - 1997/4

Y1 - 1997/4

N2 - An n X n matrix with nonnegative entries is said to be balanced if for each i = 1, . . . , n the sum of the entries of its ith row is equal to the sum of the entries of its ith column. An n x 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.

AB - An n X n matrix with nonnegative entries is said to be balanced if for each i = 1, . . . , n the sum of the entries of its ith row is equal to the sum of the entries of its ith column. An n x 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.

KW - Eigenvalue problems

KW - Line-sum-symmetric scaling

KW - Matrix balancing

KW - Matrix preconditioning

KW - Nonnegative matrices

KW - Polynomial-time solvability

UR - http://www.scopus.com/inward/record.url?scp=0031531589&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031531589&partnerID=8YFLogxK

U2 - 10.1137/S0895479895289765

DO - 10.1137/S0895479895289765

M3 - Article

AN - SCOPUS:0031531589

VL - 18

SP - 450

EP - 463

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 2

ER -