 Advances in Pure Mathematics, 2011, 1, 128-132 doi:10.4236/apm.2011.14025 Published Online July 2011 (http://www.SciRP.org/journal/apm) Copyright © 2011 SciRes. APM On Open Problems of Nonnegative Inverse Eigenvalues Problem* Junliang Wu College of Mathematics and Statistics of Chongqing University, Chongqing, China E-mail: jlwu678@tom.com Received March 15, 2011; revised June 19, 2011; accepted June 25, 2011 Abstract In this paper, we give solvability conditions for three open problems of nonnegative inverse eigenvalues problem (NIEP) which were left hanging in the air up to seventy years. It will offer effective ways to judge an NIEP whether is solvable. Keywords: Inverse Eigenvalues Problem, Nonnegative Inverse Eigenvalues Problem, Solvability, Nonnegative Matrix, Spectrum of Matrix 1. Introduction In 1937, Kolmogorov  asked the question: When is a given complex number an eigenvalues of some (en-try-wise) nonnegative matrix? The answer is: Every complex number is an eigenvalue of some nonnegative matrix . Suleimanova  extended Kolmogorov’s question in 1949 to the following well known problems which are called the nonnegative inverse eigenvaluese problems (NIEP) (also see ). Problem 1 (NIEP). Determine necessary and suffi-cient conditions for a set of complex numbers to be the eigenvalues of a nonnegative matrix of order. nnProblem 1 is open for . The case is easy while then is due to Loewy and London  (R.Loewy and D.D.London, A note on an inverse prob-lem for nonnegative matrices, Linear and Multilinear algebra, 6 (1978), 83-90). 4n2n3nIn the same paper  Suleimanova also considered the following real nonnegative inverse eigenvalues problem and gave a sufficient condition. Problem 2 (RNIEP). Determine necessary and suffi-cient conditions for a set of real number to be the eigenvalues of a nonnegative matrix of ordern. nProblem 2 is open for. Fiedler  posed the fol-lowing symmetric nonnegative inverse eigenvalues pro- blem in 1974. 5nProblem 3 (SNIEP). Determine necessary and suffi-cient conditions for a set of n real number to be the ei-genvalues of a symmetric nonnegative matrix of order n. Throughout the article, denotes set of real numbers, denotes set of complex numbers. RCProblem 1, Problem 2 and Problem 3 have not been solved yet since they were presented. To find the solv-ability of these three problems, people have been study-ing them in the recent 70 years (refer to the references), the achievements people have got and their limitations and practical application depict were evaluated in schol-arly treatise  (Moody T. Chu, Gene H. Golub, Inverse Eigenvalue Problems: Theory, Algorithms, and Applica-tions, Oxford University press. P 93-122) and article  (Ricardo L.SoTo, Reliability by symmetric nonnegative matrces, http://www.scielo.cl/pdf/proy/v24n1/art06. pdf). Readers also may refer to [9-26] for some previous re-sults. In some articles, some necessary conditions and sufficient conditions for the three problems above have been given under some small dimension or special cases . Also See the survey paper  and the book [2, Chapter VII]. The earliest study on the subject of NIEP was perhaps due to the Russian mathematician Suleima- nova (1949) on stochastic matrices, followed by Perfect (1953, 1955). The first systematic treatment of eigenval-ues of symmetric nonnegative matrices can probably be attributed to Fiedler (1974). A more comprehensive study was conducted by Boyle and Handelman (1991) using the notion of symbolic dynamics to characterize the conditions under which a given set is a portion of the spectrum of a nonnegative matrix or primitive matrix. *This work is supported by national natural science foundations of China (Grant No. 70872123). J. L. WU 129General treatises on nonnegative matrices and applica-tions include the classics by Berman and Plemmons (1979) and Minc (1988). Both books devote extensive discussion to the NIEPs as well. As [7, p94] said, most of the discussions in the litera-ture center around finding conditions to qualify a given set of values as the spectrum of some nonnegative ma-trices. A short list of references giving various necessary or sufficient conditions includesBarrett and Johnson (1984), Boyle and Handelman (1991), Friedland (1978), Friedland and Melkman (1979), Loewy and London (1978), de Oliveira (1983), and Reams (1996). The dif-ficulty is that the necessary condition is usually too general and the sufficient condition too specific. Under a few special sufficient conditions, the nonnegative ma-trices can be constructed numerically (Soules, 1983). In this paper, we will use a general method to give the solvability conditions of Problem 1 and Problem 2, we also discuss problem 3 and pose some new topics which caused by the Problem 3. Our approach is quite straight-forward, but it offers an effective way to judge whether an NIEP is solvable. To facilitate discuss the solvability condition of NIEP, we will integrate NIEP with IEP, is the following prob-lem 4. Firstly we will solve problem 4, and then with some additional conditions, the solvability conditions of Problem 1 and Problem 2 can be give accordingly. Problem 4. (Inverse eigenvalue problem-IEP) Given a list of complex numbers 12,,,n , investigate whether there is a nn real matrix with spectrumand how to d etermine such a matrix. 2. Basic Requirement of the Existence of the Solutions to IEP and NIEP For any a given list of numbers 12,,,n binn, if it have odd number elements which are pure complex numbers (a complex number ais said to be a pure complex if ) or even number pure complex num-bers with at least a complex number’s conjugation are not in the list, we can assert that any real matrix can not satisfy the demand of Problem 1-4. Because any real matrix’s spectrum always depends on a real coeffi-cient polynomial, but the complex roots of a real coeffi-cient polynomial always comes in pairs. 0bIt means that for the existence of the matrices which present in problem 1-4, the list 12,,,n  must appear as follows: 1212 12,,,,,,,,,,,klrrrzz zzz z where 0,0irRik kn, , jzCjz is con- jugation of jz 0,0jl ln, . When 2kln0k, it means that all of 12,,,n are pure com-plex numbers. When 0l, it means that all of 12,,,n are real num bers. That is, 12,,,n must be closed under complex con- jugation, the closed conception has been presented by some articles (see , p. 476, [7 ], p. 93). Next, we will begin our work with a basic result re-lated to Problem 4. 3. An Answer to the IEP Compared with the NIEP, the IEP-inverse eigenvalue problem seems to be easier one, so we discuss it firstly. Theorem 3.1. For a given list of complex numbers 12,,,n, if it has closed property under com-plex conjugation, there must be at least one real matrix A with spectrum . Proof. Since 12,,,n has closed property under complex conjugation, it has form (2.1). So, we can use it to construct th e following polynomial: 1niifx x (3.1) We note that (3.1 ) is a symmetry real coefficient poly-nomial. By expanding, merging similar items and sim-plifying, we suppose (3.1) becomes 111nn nfxxaxaxan (3.2) Then 12,,,naa a,,,n are real numbers and (3.2) has roots 12 . We use 12,,,naa a to construct companion matrix of (3.2): 12 201 00000 10000 001nn naa aaa1 A (3.3) It is not difficult to test that the characteristic polyno-mial of A is (3.2) and (3.1) exactly. It means that A has spectrum 12,,,n. Thus, we can draw the conclusion. The proof is com-plete. l (2.1) We note that using given numbers to determine nnn unknown variables (a matrix) maybe a problem of indeterminate equations, which shows that nnCopyright © 2011 SciRes. APM 130 J. L. WU there may be the relation of many to one between the two of unknown variables andngiven numbers. That is, the solution of IEP and its form may not be unique. In fact, we have the following theorem: nnTheorem 3.2. For a given list of complex num-bers12,,,nP12,, , if it has closed property under complex conjugation and there exist invertible real matrix makes, then also has spectrumnnB1PAP,nB , where A is the matrix which is constructed in the proof of Theorem 3.1. 4. Solvability Condition of Problem 1 and Problem 2 In this section we will discuss the key problem that is the solvability condition of Problem 1 and Problem 2 of NIEP. We note that the difference between IEP and NIEP is that, NIEP needs people to find at least one nonnegative matrix with a given list of complex nu mbers 12,,,n as its spectrum rather than others. Based on this requirement, we give the following Theo-rem: Theorem 4.1. For a given list of complex num-bers12,,,n , if it has closed property under complex conjugation, then the sufficient condition that has at least one nonnegative matrix A with spectrum is that 1213 13 1242,, 10000isaodd num0isa even nuernnnn jijijnnn ijkijkijknnn      121212,11bermbin (4.1) Proof. It is similar to prove the IEP in Theorem 3.1, we use12,,,nto construct the following symmetry real coefficient polynomial: 1niifxx (4.2) By expanding and merging similar items, we suppose (4.2) become s 111nn nthen 12,,,naa a12,,,nare real numbers and (4.3) has roots  . According to an algebra basic theorem of real coeffi-cient polynomial, we can get the following equalities: 12 112 1312,11231242 13,,112,,1nnnn ijijijnnnn ijkijkijknnnaaaa       (4.4) It is clear that if (4.1) holds, we can deduce that 120,0, ,0naa a,,,aaa . If we use 12 n to construct real matrix A as (3.3), A is a nonnegative matrix and its characteristic polynomial is the same with (4.3) and (4.2). That is, A has spectrum 12,,,n. Thus, the proof is complete. Obviously, Theorem 4.1 gives a solvability condition of Problem 1. In theorem 4.1, the verifying terms are simpler and easy to be actualized. For instance, if we let 1234111, 1,3,22ii1   we have 12 340012 13 142324 3423 04  123 124 134 234 17 02  12 3415 02  It is clear that01000010000115 1723 0424Ais a nonnegative matrix and it has spectrum 111,1,3,122ii  nfxxax axa (4.3) Copyright © 2011 SciRes. APM J. L. WU 131Theorem 4.1 shows that for a given list of complex numbers12,,,n, people can construct a non-negative matrix through the sufficient condition above and make this matrix have spectrum12,,,n. It is obvious that if 12,,,n,n is a given list of real numbers, it is the special case of list of complex numbers n12,,  , so we have the following Theorem: Theorem 4.2. For any a given list of real numbers 12,,,n, the sufficient condition that has at least one nonnegative matrixwith spectrumis that A1212 131,11231242 1,, 1120000isaoddnumber0isa even numbernnnn ijijijnnnn ijkijkijknnn       The proof of Theorem 4.2 can refer to Theorem 4.1, so it is omitted. Theorem 4.2 gives a solvability condition of Problem 2. Theorem 4.3. For a given list of complex num-bers12,,,n P, if it has closed property under complex conjugation and there exist invertible real matrix makesnn1PAP B and is nonnega-tive matrix, also has spectrum , where BBA is the matrix which is constructed in the proof of Theorem 4.1. Theorem 4.3 also shows that the solution to NIEP may not be unique. Next, we will discuss Problem 3. According to Theorem 4.2 and Theorem 4.3, we know that as long as 12,,,n ,n satisfy (4.1), then there must be at least one nonnegative matrixhas spec-trum 12A,, . Further, if there exist nn invertible real matrixmakes andP1PAP BBis nonnegative symmetric matrix,also has spectrum B, where A is the matrix which is constructed in the proof of Theorem 4.1. If that were true, a solvability condition of Problem 3 would be give. The question is that it needs people to prove the following th ree new topics of matrix theory further: 1) For any a givennonnegative matrixnnA, whe- ther there must be an invertible real matrix makes and also makesto be a nonnegative matrix? nnP1PAP BB2) For any a givennonnegative matrixnnA, whe- ther there must be aninvertible real matrix makes nnP1PAP Band also makes to be a symmet-ric matrix? B3) For any a given nn nonnegative matrixA, whe- ther there must be an nn invertible real matrix makes P1PAP B and also makes a both non-negative matrix and symmetric matrix; BFrom the evidence we have heard so far, there are no existing conclusions for the above problems. But we conjecture each of three new propo sitions abov e is holds. In fact, since A is a known nonnegative matrix, in nu-merous real matrices, there must be invertible real ma-trix makes P1PAP Band a both nonnegative matrix and symmetric matrix. BTo avoid adrift from the subject of this paper, we leaves the question to readers first. 5. References  A. N. Kolmogorov, “Markov Chains with Countably Many Possible States,” Bull University, Moscow, 1937, pp. 1-16.  H. Minc, “Nonnegative Matrices,” John Wiley and Sons, New York, 1988, p. 166.  K. R. Suleimanova, “Stochastic Matrices with Real Ei-genvalues,” Soviet Mathematics Doklady, Vol. 66, 1949, pp. 343-345.  M. Fiedler, “Eigenvalues of Nonnegative Symmetric Matrices,” Linear Algebra Applied, Vol. 9, 1974, pp. 119-142. doi:10.1016/0024-3795(74)90031-7.  M. T. Chu and G. H. Golub, “Inverse Eigenvalue Prob-lems: Theory, Algorithms, and Applications,” Oxford University, Oxford, pp. 93-122.  R. L. SoTo, “Reliability by Symmetric Nonnegative Ma-trices,” http://www.scielo.cl/pdf/proy/v24n1/art06.pdf.  A. Borobia, “On the Nonnegative Eigenvalue Problem,” Linear Algebra Applied, Vol. 223-224, 1995, pp. 131-140. doi:10.1016/0024-3795(94)00343-C.  M. Boyle and D. Handelman, “The Spectra of Nonnega-tive Matrices via Symbolic Dynamics,” Annals of Math-ematics, Vol. 133, 1991, pp. 249-316. doi:10.2307/2944339  X. Z. Zhan, “Matrix Theory,” Academic Press, Chinese, 2008, p. 127.  P. Egleston, “Nonnegative Matrices with Prescribed Spe- ctra,” Dissertation, Central Michigan University, 2001.  C. Johnson, “Row Stochastic Matrices Similar to Doubly Stochastic Matrices,” Linear and Multilinear Algebra, Vol. 10, No. 2, 1981, pp. 113-130. doi:10.1080/03081088108817402  C. Johnson, T. J. Laffey and R. Loewy, “The Real and the Symmetric Nonnegative Inverse Eigenvalue Problems are Different,” Proceedings of the American Mathematical Society, Vol. 124, 1996, pp. 3647-3651. doi:10.1090/S0002-9939-96-03587-3  F. Karpelevich, “On the Eigenvalues of a Matrix with Copyright © 2011 SciRes. APM J. L. WU Copyright © 2011 SciRes. APM 132 Nonnegative Elements,” Izvestia Akademii Nauk SSSR Metally, Vol. 15, 1951, pp. 361-383.  R. B. Kellogg, “Matrices Similar to a Positive or Essen-tially Positive Matrix,” Linear Algebra Applied, Vol. 4, No. 3, 1971, pp. 191-204. doi:10.1016/0024-3795(71)90015-2  C. Knudsen and J. J. McDonald, “A Note on THE Con-vexity of the Realizable set of Eigenvalues for Nonnega-tive Symmetric Matrices,” Electronic Journal Linear Al-gebra, Vol. 8, 2001, pp. 110-114.  T. Laffey, “Realizing Matrices in the Nonnegative In-verse Eigenvalue Problem,” Texts in Mathematics ,Series B, University, Coimbra, 1999, pp. 21-32.  T. Laffey and E. Meehan, “A refinement of an inequality of Johnson, Loewy, and London on Nonnegative Matri-ces and Some Applications,” Electron Journal Linear Algebra, Vol. 3, 1998, pp. 119-128.  T. Laffey and E. Meehan, “A Characterization of Trace zero Nonnegative 5×5 Matrices,” Linear Algebra Applied, Vol. 302-303, No. 1, 1999, pp. 295-302. doi:10.1016/S0024-3795(99)00099-3  J. J. McDonald and M. Neumann, “The Soules Approach to the Inverse Eigenvalue Problem for Nonnegative Sym-metric Matrices of Order n-5,” Contemporary Mathe-matics, Vol. 259, 2000, pp. 387-407.  L. Mirsky and H. Perfect, “Spectral Properties of Doubly Stochastic Matrices,” Mathematics and Statistics, Vol. 69 No. 1, 1965, pp. 35-57. doi:10.1007/BF01313442  H. Perfect, “Methods of Constructing Certain Stochastic Matrices,” Duke Mathematical Journal, Vol. 20, No. 3, 1953, pp. 395-404. doi:10.1215/S0012-7094-53-02040-7  N. Radwan, “An Inverse Eigenvalue Problem for Sym-metric and Normal Matrices,” Linear Algebra Applied, Vol. 248, No. 15, 1996, pp. 101-109. doi:10.1016/0024-3795(95)00162-X  R. Reams, “An Inequality for Nonnegative Matrices and the Inverse Eigenvalue Problem,” Linear and Multilinear Algebra, Vol. 41, No. 4, 1996, pp. 367-375. doi:10.1080/03081089608818485  G. Wuwen, “Eigenvalues of Nonnegative Matrices,” Linear Algebra Applied, Vol. 266, No. 15 1997, pp. 261-270. doi:10.1016/S0024-3795(96)00007-9  R. Loewy and D. London, “A Note on an Inverse Prob-lem for Nonnegative Matrices,” Linear and Multilinear Algebra, Vol. 6, No. 1, 1978, pp. 83-90. doi:10.1080/03081087808817226.  P. D. Egleston and T. D. Lenker, “Sivaram K. Narayan, the Nonnegative Inverse Eigenvalue Problem,” Linear Algebra and Its Applications, Vol. 379, No. 1, 2004, pp. 475-490.