### Abstract

An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

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

Pages (from-to) | 87-103 |

Number of pages | 17 |

Journal | Linear Algebra and Its Applications |

Volume | 240 |

DOIs | |

State | Published - Jan 1 1996 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics

### Cite this

*Linear Algebra and Its Applications*,

*240*, 87-103. https://doi.org/10.1016/0024-3795(94)00188-X

}

*Linear Algebra and Its Applications*, vol. 240, pp. 87-103. https://doi.org/10.1016/0024-3795(94)00188-X

**On the complexity of nonnegative-matrix scaling.** / Kalantari, Bahman; Khachiyan, Leonid.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On the complexity of nonnegative-matrix scaling

AU - Kalantari, Bahman

AU - Khachiyan, Leonid

PY - 1996/1/1

Y1 - 1996/1/1

N2 - An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

AB - An n × n nonnegative matrix A is said to be (doubly stochastic) scalable if there exist two positive diagonal matrices X and Y such that XAY is doubly stochastic. We derive an upper bound on the norms of the scaling factors X and Y and give a polynomial-time complexity bound on the problem of computing the scaling factors to a prescribed accuracy.

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

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

U2 - 10.1016/0024-3795(94)00188-X

DO - 10.1016/0024-3795(94)00188-X

M3 - Article

VL - 240

SP - 87

EP - 103

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

ER -