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
j
z is con-
jugation of
j
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
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:

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
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
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
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
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
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
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
f
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
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 12
A
,,

 . Further, if there exist nn
invertible real matrixmakes and
P1PAP B
B
is
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?
nnP
1PAP BB
2) For any a givennonnegative matrixnn
A
, 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
A
, 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
A
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.