The real nonnegative inverse eigenvalue problem is NP-hard. (English) Zbl 1361.65022
Summary: A list of complex numbers is realizable if it is the spectrum of a nonnegative matrix. In 1949 Suleǐmanova posed the nonnegative inverse eigenvalue problem (NIEP): the problem of determining which lists of complex numbers are realizable. The version for reals of the NIEP (RNIEP) asks for realizable lists of real numbers. In the literature there are many sufficient conditions or criteria for lists of real numbers to be realizable. We present an unified account of these criteria. Then we see that the decision problem associated to the RNIEP is NP-hard and we study the complexity for the decision problems associated to known criteria.
MSC:
| 65F18 | Numerical solutions to inverse eigenvalue problems |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 15A29 | Inverse problems in linear algebra |
| 65Y20 | Complexity and performance of numerical algorithms |
| 15B48 | Positive matrices and their generalizations; cones of matrices |
Keywords:
nonnegative matrix; inverse eigenvalue problem; decision problem; NP-hard; NP-complete; complexityReferences:
| [1] | Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press · Zbl 1193.68112 |
| [2] | Blum, L., Computing over the reals: where Turing meets Newton, Notices Amer. Math. Soc., 51, 9, 1024-1034 (2004) · Zbl 1159.68459 |
| [3] | Borobia, A., On the nonnegative eigenvalue problem, Special Issue Honoring Miroslav Fiedler and Vlastimil Pták. Special Issue Honoring Miroslav Fiedler and Vlastimil Pták, Linear Algebra Appl., 223/224, 131-140 (1995) · Zbl 0831.15014 |
| [4] | Borobia, A.; Moro, J.; Soto, R. L., A unified view on compensation criteria in the real nonnegative inverse eigenvalue problem, Linear Algebra Appl., 428, 11-12, 2574-2584 (2008) · Zbl 1145.15006 |
| [5] | Boyle, M.; Hendelman, D., The spectra of nonnegative matrices via symbolic dynamics, Ann. of Math. (2), 133, 2, 249-316 (1991) · Zbl 0735.15005 |
| [6] | Ciarlet, P., Some results in the theory of nonnegative matrices, Linear Algebra Appl., 1, 1, 139-152 (1968) · Zbl 0167.03101 |
| [7] | Cohen, J.; Rothblum, U., Nonnegative ranks, decompositions and factorizations of nonnegative matrices, Linear Algebra Appl., 190, 149-168 (1993) · Zbl 0784.15001 |
| [8] | Ellard, R.; Šmigoc, H., Connecting sufficient conditions for the symmetric nonnegative inverse eigenvalue problem, Linear Algebra Appl., 498, 521-552 (2016) · Zbl 1334.15028 |
| [9] | Fiedler, M., Eigenvalues of nonnegative symmetric matrices, Linear Algebra Appl., 9, 119-142 (1974) · Zbl 0322.15015 |
| [10] | Guo, W., Eigenvalues of nonnegative matrices, Linear Algebra Appl., 266, 261-270 (1997) · Zbl 0903.15003 |
| [11] | Hayes, B., Computing science: the easiest hard problem, Am. Sci., 90, 113-117 (2002) |
| [12] | Karp, R. M., Reducibility among combinatorial problems, (Proceedings of a symposium on the Complexity of Computer Computations. Proceedings of a symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972 (1972), Plenum: Plenum New York), 85-103 · Zbl 1467.68065 |
| [13] | Kellogg, R., Matrices similar to a positive or essentially positive matrix, Linear Algebra Appl., 4, 191-204 (1971) · Zbl 0215.37504 |
| [14] | Kim, K. H.; Ormes, N. S.; Roush, F. W., The spectra of nonnegative integer matrices via formal power series, J. Amer. Math. Soc., 10, 773-806 (2000) · Zbl 0968.15005 |
| [15] | Marijuán, C.; Pisonero, M.; Soto, R. L., A map of sufficient conditions for the real nonnegative inverse eigenvalue problem, Linear Algebra Appl., 426, 2-3, 690-705 (2007) · Zbl 1126.15018 |
| [16] | Perfect, H., Methods of constructing certain stochastic matrices, Duke Math. J., 20, 395-404 (1953) · Zbl 0051.35701 |
| [17] | Perfect, H., Methods of constructing certain stochastic matrices II, Duke Math. J., 22, 305-311 (1955) · Zbl 0068.32704 |
| [18] | Salzmann, F., A note on the eigenvalues of nonnegative matrices, Linear Algebra Appl., 5, 329-338 (1972) · Zbl 0255.15009 |
| [19] | Šmigoc, H., The inverse eigenvalue problem for nonnegative matrices, Special issue on Positivity in Linear Algebra. Special issue on Positivity in Linear Algebra, Linear Algebra Appl., 393, 365-374 (2004) · Zbl 1075.15012 |
| [20] | Soto, R. L., Existence and construction of nonnegative matrices with prescribed spectrum, Linear Algebra Appl., 369, 169-184 (2003) · Zbl 1031.15018 |
| [21] | Soto, R. L., A family of realizability criteria for the real and symmetric nonnegative inverse eigenvalue problem, Numer. Linear Algebra Appl., 20, 2, 336-348 (2013) · Zbl 1289.15052 |
| [22] | Soules, G., Constructing symmetric nonnegative matrices, Linear Multilinear Algebra, 13, 241-251 (1983) · Zbl 0516.15013 |
| [23] | Suleı̌manova, H., Stochastic matrices with real characteristic values, Dokl. Akad. Nauk SSSR, 66, 343-345 (1949), (in Russian) · Zbl 0035.20903 |
| [24] | Vavasis, S. A., On that complexity of nonnegative matrix factorization, SIAM J. Optim., 20, 3, 1364-1377 (2009) · Zbl 1206.65130 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
