On the complexity of matrix balancing

Bahman Kalantari, L. Khachiyan, A. Shokoufandeh

Research output: Contribution to journalArticle

17 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)450-463
Number of pages14
JournalSIAM Journal on Matrix Analysis and Applications
Volume18
Issue number2
DOIs
StatePublished - Jan 1 1997

Fingerprint

Balancing
Non-negative
Convex Programming
Diagonal matrix
Sensitivity Analysis
Solvability
Upper and Lower Bounds
Polynomial time
Scaling
Necessary
Computing
Similarity

All Science Journal Classification (ASJC) codes

  • Analysis

Cite this

Kalantari, Bahman ; Khachiyan, L. ; Shokoufandeh, A. / On the complexity of matrix balancing. In: SIAM Journal on Matrix Analysis and Applications. 1997 ; Vol. 18, No. 2. pp. 450-463.
@article{da9c61967e414cba9ce416f9c71681aa,
title = "On the complexity of matrix balancing",
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.",
author = "Bahman Kalantari and L. Khachiyan and A. Shokoufandeh",
year = "1997",
month = "1",
day = "1",
doi = "10.1137/S0895479895289765",
language = "English (US)",
volume = "18",
pages = "450--463",
journal = "SIAM Journal on Matrix Analysis and Applications",
issn = "0895-4798",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

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

In: SIAM Journal on Matrix Analysis and Applications, Vol. 18, No. 2, 01.01.1997, p. 450-463.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the complexity of matrix balancing

AU - Kalantari, Bahman

AU - Khachiyan, L.

AU - Shokoufandeh, A.

PY - 1997/1/1

Y1 - 1997/1/1

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.

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

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 -