 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 [1] 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 [2]. Suleimanova [3] extended Kolmogorov’s question in 1949 to the following well known problems which are called the nonnegative inverse eigenvaluese problems (NIEP) (also see [4]). 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. nn Problem 1 is open for . The case is easy while then is due to Loewy and London [5] (R.Loewy and D.D.London, A note on an inverse prob- lem for nonnegative matrices, Linear and Multilinear algebra, 6 (1978), 83-90). 4n2n 3n In the same paper [3] 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. n Problem 2 is open for. Fiedler [6] 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. R CProblem 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 [7] (Moody T. Chu, Gene H. Golub, Inverse Eigenvalue Problems: Theory, Algorithms, and Applica- tions, Oxford University press. P 93-122) and article [8] (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 [7]. Also See the survey paper [26] 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 spectrumand 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 ,,,,,,,,,,, kl rrrzz zzz z where 0,0 i rRik kn , , j zC z is con- jugation of z 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 [3], 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 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: 1 n i i fx 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 1 11 nn n fxxaxaxa n (3.2) Then 12 ,,, n aa a ,,, n are real numbers and (3.2) has roots 12 . We use 12 ,,, n aa a to construct companion matrix of (3.2): 12 2 01 000 00 100 00 001 nn n aa aaa 1 A (3.3) It is not difficult to test that the characteristic polyno- mial of is (3.2) and (3.1) exactly. It means that 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 n nn 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 P 12 ,, , if it has closed property under complex conjugation and there exist invertible real matrix makes, then also has spectrum nn B 1PAP , n B , where 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 with spectrum is that 12 13 1 3 1242,, 1 0 0 0 0isaodd num 0isa even nuer n n nn j ij ij n nn ijk ijk ijk n n n 12 12 12 ,1 1 ber mb i n (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: 1 n i i fx x (4.2) By expanding and merging similar items, we suppose (4.2) become s 1 11 nn n then 12 ,,, n aa a 12 ,,, n are 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 1 12 1312 ,1 1231242 13 ,,1 12 ,, 1 n n nn ij ij ij n nnn ijk ijk ijk n nn a a a a (4.4) It is clear that if (4.1) holds, we can deduce that 12 0,0, ,0 n aa a ,,,aaa . If we use 12 n to construct real matrix as (3.3), is a nonnegative matrix and its characteristic polynomial is the same with (4.3) and (4.2). That is, 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 1234 11 1, 1,3, 22 ii 1 we have 12 34 00 12 13 1423 24 3423 0 4 123 124 134 234 17 0 2 12 3415 0 2 It is clear that 0100 0010 0001 15 1723 0 424 Ais a nonnegative matrix and it has spectrum 11 1,1,3,1 22 ii n xxax 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 12 12 131,1 1231242 1,, 1 12 0 0 0 0isaoddnumber 0isa even number n n nn ij ij ij n nnn ijk ijk ijk n n n 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 B B 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 12 A ,, . Further, if there exist nn invertible real matrixmakes and P1PAP B is nonnegative symmetric matrix,also has spectrum B , where 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 , whe- ther there must be an invertible real matrix makes and also makesto be a nonnegative matrix? nnP 1PAP BB 2) For any a givennonnegative matrixnn , whe- ther there must be aninvertible real matrix makes nnP 1 PAP B and also makes to be a symmet- ric matrix? B 3) For any a given nn nonnegative matrix , whe- ther there must be an nn invertible real matrix makes P 1 PAP B and also makes a both non- negative matrix and symmetric matrix; B From 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 is a known nonnegative matrix, in nu- merous real matrices, there must be invertible real ma- trix makes P1 PAP B and a both nonnegative matrix and symmetric matrix. B To avoid adrift from the subject of this paper, we leaves the question to readers first. 5. References [1] A. N. Kolmogorov, “Markov Chains with Countably Many Possible States,” Bull University, Moscow, 1937, pp. 1-16. [2] H. Minc, “Nonnegative Matrices,” John Wiley and Sons, New York, 1988, p. 166. [3] K. R. Suleimanova, “Stochastic Matrices with Real Ei- genvalues,” Soviet Mathematics Doklady, Vol. 66, 1949, pp. 343-345. [4] M. Fiedler, “Eigenvalues of Nonnegative Symmetric Matrices,” Linear Algebra Applied, Vol. 9, 1974, pp. 119-142. doi:10.1016/0024-3795(74)90031-7. [5] M. T. Chu and G. H. Golub, “Inverse Eigenvalue Prob- lems: Theory, Algorithms, and Applications,” Oxford University, Oxford, pp. 93-122. [6] R. L. SoTo, “Reliability by Symmetric Nonnegative Ma- trices,” http://www.scielo.cl/pdf/proy/v24n1/art06.pdf. [7] 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. [8] 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 [9] X. Z. Zhan, “Matrix Theory,” Academic Press, Chinese, 2008, p. 127. [10] P. Egleston, “Nonnegative Matrices with Prescribed Spe- ctra,” Dissertation, Central Michigan University, 2001. [11] 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 [12] 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 [13] 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. [14] 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 [15] 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. [16] T. Laffey, “Realizing Matrices in the Nonnegative In- verse Eigenvalue Problem,” Texts in Mathematics ,Series B, University, Coimbra, 1999, pp. 21-32. [17] 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. [18] 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 [19] 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. [20] 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 [21] 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 [22] 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 [23] 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 [24] 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 [25] 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. [26] 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.
|
