The real nonnegative inverse eigenvalue problem is NP-hard

DOI10.1016/j.laa.2017.02.010zbMath1361.65022arXiv1608.00931OpenAlexW2475492209MaRDI QIDQ518113

Alberto Borobia, Roberto Canogar

Publication date: 28 March 2017

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

Full work available at URL: https://arxiv.org/abs/1608.00931

zbMATH Keywords

complexitynonnegative matrixNP-hardinverse eigenvalue problemNP-completedecision problem

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Inverse problems in linear algebra (15A29) Positive matrices and their generalizations; cones of matrices (15B48) Complexity and performance of numerical algorithms (65Y20) Numerical solutions to inverse eigenvalue problems (65F18)

Related Items (3)

A Riemannian inexact Newton-CG method for constructing a nonnegative matrix with prescribed realizable spectrum ⋮ Minimal positive realizations: A survey ⋮ Inverse eigenvalue problems for centrosymmetric matrices under a central principal submatrix constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Connecting sufficient conditions for the symmetric nonnegative inverse eigenvalue problem
• Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
• The inverse eigenvalue problem for nonnegative matrices
• Methods of constructing certain stochastic matrices. II
• A unified view on compensation criteria in the real nonnegative inverse eigenvalue problem
• A map of sufficient conditions for the real nonnegative inverse eigenvalue problem
• The spectra of nonnegative matrices via symbolic dynamics
• Eigenvalues of nonnegative symmetric matrices
• Eigenvalues of nonnegative matrices
• Existence and construction of nonnegative matrices with prescribed spectrum
• On the nonnegative eigenvalue problem
• Some results in the theory of nonnegative matrices
• Matrices similar to a positive or essentially positive matrix
• A note on eigenvalues of nonnegative matrices
• Methods of constructing certain stochastic matrices
• On the Complexity of Nonnegative Matrix Factorization
• Constructing symmetric nonnegative matrices
• The spectra of nonnegative integer matrices via formal power series
• Reducibility among Combinatorial Problems
• Computational Complexity
• A family of realizability criteria for the real and symmetric nonnegative inverse eigenvalue problem

This page was built for publication: The real nonnegative inverse eigenvalue problem is NP-hard