Diagonal matrix scaling is NP-hard

DOI10.1016/0024-3795(94)00099-9MaRDI QIDQ1908195zbMATH OpenOpenAlexFDO

Authors Leonid G. Khachiyan

Publication date 30 June 1996

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(94)00099-9

zbMATH Keywords

diagonal matrix scalinglogarithmic barrier functionNP-hardsymmetric matrix

Mathematics Subject Classification ID

Conditioning of matrices (15A12) Numerical computation of matrix norms, conditioning, scaling (65F35) Complexity and performance of numerical algorithms (65Y20)

Review text

The author shows that the general scaling problem \(XAX e = e\), \(X = \text{diag} \{x_1,\dots,x_n\} > 0\), where \(e\) is the vector of all ones, \(X\) is a positive diagonal matrix and \(A\) is a symmetric \(n \times n\) matrix, is NP-hard. Equivalently, it is NP-hard to check for a given symmetric matrix \(A\) whether the logarithmic barrier function \({1 \over 2} x^T Ax - \Sigma \ln x_i\) has a stationary point in the positive orthant \(x > 0\).

Recommendations

• Diagonal Matrix Scaling and Linear Programming
• On the complexity of nonnegative-matrix scaling
• On complexity of matrix scaling
• Semidefinite programming and matrix scaling over the semidefinite cone.
• scientific article; zbMATH DE number 733109

Cites work

• Concerning nonnegative matrices and doubly stochastic matrices
• Diagonal Matrix Scaling and Linear Programming
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4197755 (Why is no real title available?)
• Note on Nonnegative Matrices
• On matrices with doubly stochastic pattern
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix

Cited in

(7)

• Finding well-conditioned similarities to block-diagonalize nonsymmetric matrices is NP-hard
• A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices
• An information theory perspective on the balanced minimum evolution problem
• A tutorial on the balanced minimum evolution problem
• Diagonal Matrix Scaling and Linear Programming
• Tensors in computations
• Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: Diagonal matrix scaling is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908195)