Nonnegative matrices have long been a sorce of interesting and challenging mathematical problems. They are real matrices with all their entries being nonnegative and arise in a number of important application areas: communications systems, biological systems, economics, ecology, computer sciences, machine learning, and many other engineering systems. Inverse eigenvalue problems constitute an important subclass of inverse problems that arise in the context of mathematical modeling and parameter identification. A simple application of such problems is the construction of Leontief models in economics -.
The nonnegative inverse eigenvalue problemNIEPis the problem of characterizing those lists of complex numbers which can be the spectra of entrywise nonnegative matrices. If there exists a nonnegative matrix with spectrum we say that is realized by and that is the realizing matrix. A set of conditions is said to be a realizability criterionif any list real or complex, satisfying conditions is realizable. The NIEP is an open problem.A full solution is unlikely in the near future. The problem has only been solved for by Loewy and London (, 1978) and for by Meehan (, 1998) and Torre-Mayo et al.(, 2007). The case has been solved for matrices of trace zero in (, 1999). Other results, mostly in terms of sufficient conditions for the problem to have a solution (in the case of a complex list ), have been obtained, in chronological order, in -.
Two main subproblems of the NIEPare of great interest: the real nonnegative inverse eigenvalue problem(RNIEP), in which is a list of real numbers, and the symmetric nonnegative inverse eigenvalue problem(SNIEP), in which the realizing matrix must be symmetric. Both problems, RNIEPand SNIEPare equivalent for (see ), but they are different otherwise (see ). Moreover, both problems remains unsolved for The NIEPis also of interest for nonnegative matrices with a particular structure, like stochastic and doubly stochastic, circulant, persymmetric, centrosymmetric, Hermitian, Toeplitz, etc.
The first sufficient conditions for the existence of a nonnegative matrix with a given real spectrum (RNIEP) were obtained by Suleimanova (, 1949) and Perfect (, , 1953 and 1955). Other sufficient conditions have also been obtained, in chronological order in -, (see also , , and references therein for a comprehensive survey).
The first sufficient conditions for the SNIEPwere obtained by Fiedler (, 1974). Other results for symmetric realizability have been obtained in ,  and -. Recently, new sufficient conditions for the SNIEPhave been given in -.
1.1. Necessary conditions
Let be a nonnegative matrix with spectrum Then, from the Perron Frobenius theory we have the following basic necessary conditions
where means that is closed under complex comjugation.
Moreover, we have
Necessary condition is due to Loewy and London . Necessary condition which is a refinement of is due to Laffey and Meehan . The list for instance, satisfies all above necessary conditions, except condition Therefore is not a realizable list. In  it was obtained a new necessary condition, which is independent of the previous ones. This result is based on the Newton's inequalities associated to the normalized coefficients of the characteristic polynomial of an M-matrix or an inverse M-matrix.
The chapter is organized as follows: In section 2 we introduce two important matrix results, due to Brauer and Rado, which have allowed to obtain many of the most general sufficient conditions for the RNIEP, the SNIEPand the complex case. In section 3 we consider the real case and we introduce, without proof (we indicate where the the proofs can be found), two sufficient conditions with illustrative examples. We consider, in section 4, the symmetric case. Here we introduce a symmetric version of the Rado result, Theorem ▭, and we set, without proof (see the appropriate references), three sufficient conditions, which are, as far as we know, the most general sufficient conditions for the SNIEP. In section we discuss the complex (non real) case. Here we present several results with illustrative examples. Section 6 is devoted to discuss some Fiedler results and Guo results, which are very related with the problem and have been employed with success to derive sufficient conditions. Finally, in section 7, we introduce some open questions.
2. Brauer and Rado Theorems
A real matrix is said to have constant row sumsif all its rows sum up to the same constant, say, that is,The set of all real matrices with constant row sums equal to is denoted by It is clear that any matrix in has eigenvector corresponding to the eigenvalue Denote by the dimensional vector with one in the position and zeros elsewhere.
It is well known that the problem of finding a nonnegative matrix with spectrum is equivalent to the problem of finding a nonnegative matrix in with spectrum (see ). This will allow us to exploit the advantages of two important theorems, Brauer Theorem and Rado Theorem, which will be introduced in this section.
The spectra of circulant nonnegative matrices have been characterized in , while in , a simple complex generalization of Suleimanova result has been proved, and efficient and general sufficient conditions for the realizability of partitioned spectra, with the partition allowing some of its pieces to be nonrealizable, provided there are other pieces, which are realizable and, in certain way, compensate the nonnrealizability of the former, have been obtained. This is the procedure which we call negativity compensation. This strategy, based in the use of the following two perturbation results, together with the properties of real matrices with constant row sums, has proved to be successful.
Theorem 1Brauer Letbe anarbitrary matrix with eigenvaluesLetan eigenvector ofassociated with the eigenvalueand letbe any-dimensional vector. Then the matrixhas eigenvalues
Let be an nonsingular matrix such that
is an upper triangular matrix, where we choose the first column of as (there exists from a well known result of Schur). Then,
and the result follows.
This proof is due to Reams .
Theorem 2RadoLetbe anarbitrary matrix with eigenvaluesand letfor someLetbe anmatrix with ranksuch that its columnssatisfyLetbe anarbitrary matrix. Then the matrixhas eigenvalueswhereare eigenvalues of the matrix
Let a nonsingular matrix withThen and Let Then, since
and we have
3. Real nonnegative inverse eigenvalue problem.
Regarding the RNIEP,by applying Brauer Theorem and Rado Theorem, efficient and general sufficient conditions have been obtained in , , , .
Theorem 3 Let be a given list of real numbers. Suppose that:
There exists a partition where
such that for each sublist we associate a corresponding list
which is realizable by a nonnegative matrix of order
There exists a nonnegative matrix with eigenvalues (the first elements of the lists ) and diagonal entries (the first elements of the lists ).
Then is realizable by a nonnegative matrix
Perfect  gave conditions under which and are the eigenvalues and the diagonal entries, respectively, of a nonnegative matrix For it is necessary and sufficient that with For Perfect gave the following result:
Theorem 4 The real numbers and are the eigenvalues and the diagonal entries, respectively, of a nonnegative matrix if and only if:
Then, an appropriate nonnegative matrix is
For we only have a sufficient condition:
with the following matrix having eigenvalues and diagonal entries and respectively:
Example 1Let us consider the list with the partition
and the realizable associated lists
From (▭) we compute the nonnegative matrix
with eigenvalues and diagonal entries Then
is nonnegative with spectrum
A map of sufficient conditions for the RNIEPit was constructed in,There, the sufficient conditions were compared to establish inclusion or independence relations between them. It is also shown in  that the criterion given by Theorem ▭ contains all realizability criteria for lists of real numbers studied therein. In , from a new special partition, Theorem ▭ is extended. Now, the first element of the sublist need not to be nonnegative and the realizable auxiliar list contains one more element. Moreover, the number of lists of the partition depend on the number of elements of the first list and some lists can be empty.
Theorem 5 Let be a list of real numbers and let the partition be such that
where is the number of elements of the list and some of the lists can be empty. Let be real numbers satisfying Suppose that the following conditions hold:
For each there exists a nonnegative matrix with spectrum
There exists a nonnegative matrix with spectrum and with diagonal entries
Then is realizable by a nonnegative matrix
Example 2With this extension, the authors show for instance, that the list
is realizable, which can not be done from the criterion given by Theorem ▭. In fact, let the partition
The nonnegative matrix
has spectrum and diagonal entries It is clear that
has the desired spectrum
4. Symmetric nonnegative inverse eigenvalue problem
Several realizability criteria which were first obtained for the RNIEPhave later been shown to be symmetric realizability criteria as well. For example, Kellogg criterion  was showed by Fiedler  to imply symmetric realizability. It was proved by Radwan  that Borobia's criterion  is also a symmetric realizability criterion, and it was proved in  that Soto's criterion for the RNIEPis also a criterion for the SNIEP.In this section we shall consider the most general and efficient symmetric realizability criteria for the SNIEP(as far as we know they are). We start by introducing a symmetric version of the Rado Theorem:.
Theorem 6 Let be an symmetric matrix with spectrum and for some let be an orthonormal set of eigenvectors of spanning the invariant subspace associated with Let be the matrix with column let and let be any symmetric matrix. Then the symmetric matrix has eigenvalues where are the eigenvalues of the matrix
Since the columns of are an orthonormal set, we may complete to an orthogonal matrix that is, Then
and is symmetric with eigenvalues
By using Theorem ▭, the following sufficient condition was proved in :
Theorem 7 Let be a list of real numbers with and, for some let be real numbers satisfying Suppose there exists:
a partition with
such that for each the list is realizable by a symmetric nonnegative matrix of order and
a symmetric nonnegative matrix with eigenvalues and with diagonal entries
Then is realizable by a symmetric nonnegative matrix.
Since is a symmetric nonnegative matrix realizing then is symmetric nonnegative with spectrum Let be an orthonormal set of eigenvectors of associated with respectively. Then the matrix with column satisfies for Moreover, is entrywise nonnegative, since each contains the Perron eigenvector of and zeros. Now, if we set the matrix is symmetric nonnegative and has eigenvalues Therefore, by Theorem ▭ the symmetric matrix has spectrum Besides, it is nonnegative since all the entries of and are nonnegative.
Theorem ▭ not only ensures the existence of a realizing matrix, but it also allows to construct the realizing matrix. Of course, the key is to know under which conditions does there exists a symmetrix nonnegative matrix with eigenvalues and diagonal entries
The following conditions for the existence of a real symmetric matrix, not necessarily nonnegative, with prescribed eigenvalues and diagonal entries are due to Horn : There exists a real symmetric matrix with eigenvaluesand diagonal entriesif and only if
For the conditions (▭) become
and they are also sufficient for the existence of a symmetric nonnegative matrix with eigenvalues and diagonal entries namely,
For we have the following conditions:
Lemma 1 The conditions
are necessary and sufficient for the existence of a symmetric nonnegative matrix with eigenvalues and diagonal entries
In , the following symmetric nonnegative matrix satisfying conditions (▭), it was constructed:
For we have only a sufficient condition:
Theorem 8Fiedler  If and satisfy
then there exists a symmetric nonnegative matrix with eigenvalues and diagonal entries
has eigenvalues but
Example 3Let us consider the list with the partition
We look for a symmetric nonnegative matrix with eigenvalues and diagonal entries Then conditions (▭) are satisfied and from (▭) we compute
where The symmetric matrices
is symmetric nonnegative with spectrum
In the same way as Theorem ▭ was extended to Theorem ▭ (in the real case), Theorem ▭ was also extended to the following result:
Theorem 9 Let be a list of real numbers and let the partition be such that
where is symmetrically realizable, is the number of elements of and some lists can be empty. Let be real numbers satisfying Suppose that the following conditions hold:
For each there exists a symmetric nonnegative matrix with spectrum
There exists a symmetric nonnegative matrix with spectrum and with diagonal entries
Then is symmetrically realizable.
Example 4Now, from Theorem ▭, we can see that there exists a symmetric nonnegative matrix with spectrum , which can not be seen from Theorem ▭. Moreover, we can compute a realizing matrix. In fact, let the partition
The symmetric nonnegative matrix
has spectrum and diagonal entries Let and
Then, from Theorem ▭ we obtain
which is symmetric nonnegative with spectrum
The following result, although is not written in the fashion of a sufficient condition, is indeed a very general and efficient sufficient condition for the SNIEP.
Theorem 10 Let be an irreducible symmetric nonnegative matrix with spectrum Perron eigenvalue and a diagonal element Let be an symmetric nonnegative matrix with spectrum and Perron eigenvalue
If then there exists a symmetric nonnegative matrix of order with spectrum
If then there exists a symmetric nonnegative matrix of order with spectrum
Example 5The following example, given in , shows that
with the partition
satisfies conditions of Theorem ▭, where
is symmetric nonnegative with spectrum Then there exists a symmetric nonnegative matrix with spectrum and a diagonal element By applying again Theorem ▭ to the lists and we obtain the desired symmetric nonnegative matrix.
It is not hard to show that both results, Theorem ▭ and Theorem ▭, are equivalent (see ). Thus, the list in the Example ▭ is also realizable from Theorem ▭, while the list in the example ▭ is also realizable from Theorem ▭.
5. List of complex numbers
In this section we consider lists of complex nonreal numbers. We start with a complex generalization of a well known result of Suleimanova, usually considered as one of the important results in theRNIEP (see): The listis the spectrum of a nonnegative matrix if and only if
Theorem 11 Let be a list of complex numbers closed under complex conjugation, with
Then is realizable if and only if
Suppose that the elements of are ordered in such a way that are real and are complex nonreal, with
for Consider the matrix
It is clear that with spectrum and all the entries on its first column are nonnegative. Define withand
Then, from the Brauer Theorem ▭ is nonnegative with spectrum
In the case when all numbers in the given list, except one (the Perron eigenvalue), have real parts smaller than or equal to zero, remarkably simple necessary and sufficient conditions were obtained in .
Theorem 12 Let be nonzero complex numbers with real parts less than or equal to zero and let be a positive real number. Then the list is the nonzero spectrum of a nonnegative matrix if the following conditions are satisfied:
The minimal number of zeros that need to be added to to make it realizable is the smallest nonnegative integer for which the following inequality is satisfied:
Furthermore, the list can be realized by where is a nonnegative companion matrix with trace zero, is a nonnegative scalar and is the identity matrix.
Corollary 1 Let be complex numbers with real parts less than or equal to zero and let be a positive real number. Then the list is the spectrum of a nonnegative matrix if and only if the following conditions are satisfied:
Example 6The list satisfies conditions (▭). Then is the spectrum of the nonnegative companion matrix
Observe that Theorem ▭ gives no information about the realizability of
The list was given in . It does not satisfy conditions (▭): andThe inequality is satisfied for Then we need to add 6 zeros to the list to make it realizable.
Theorem ▭ (in section 3), can also be extended to the complex case:
Theorem 13 Let be a list of complex numbers such that andSuppose that:
there exists a partition with
such that is realizable by a nonnegative matrix and
there exists a nonnegative matrix with eigenvalues
(the first elements of the lists and with diagonal entries (the Perron eigenvalues of the lists
Then is realizable.
Example 7Let Consider the partition
We look for a nonnegative matrix with eigenvalues and diagonal entries and a nonnegative matrix realizing They are
has the spectrum
6. Fiedler and Guo results
One of the most important works about the SNIEPis due to Fiedler . In  Fiedler showed, as it was said before, that Kellogg sufficient conditions for the RNIEPare also sufficient for the SNIEP. Three important and very useful results of Fiedler are:
Lemma 2 Let be a symmetric matrix with eigenvalues Let be a symmetric matrix with eigenvalues Then for any the matrix
has eigenvalues where are eigenvalues of the matrix
Lemma 3 If and are lists symmetrically realizable and , then for any the list
is also symmetrically realizable.
Lemma 4 If is symmetrically realizable by a nonnegative matrix and if then
is symmetrically realizable by a positive matrix.
Remark 1It is not hard to see that Lemma ▭ can be obtained from Theorem ▭. In fact, it is enough to consider
which is symmetric with eigenvalues where are eigenvalues of
Now we consider a relevant result due to Guo :
Theorem 14 If the list of complex numbers is realizable, where is the Perron eigenvalue and then for any the list is also realizable.
Corollary 2 If the list of real numbers is realizable andwith then the list is also realizable.
Example 8Let be a given list. Since the lists are both realizable (see  to apply a simple criterion, which shows the realizability of ), then
is also realizable. Now, from Theorem ▭, with is realizable.
Guo also sets the following two questions:
Question 1: Do complex eigenvalues of nonnegative matrices have a property similar to Theorem ▭?
Question 2: If the list is symmetrically realizable, and is the list symmetrically realizable?.
It was shown in  and also in  that Question 1 has an affirmative answer.
Theorem 15 Let be a realizable list of complex numbers. Then for all the perturbed list
is also realizable.
Question 2, however, remains open. An affirmative answer to Question 2, in the case that the symmetric realizing matrix is a nonnegative circulant matrix or it is a nonnegative left circulant matrix, it was given in . The use of circulant matrices has been shown to be very useful for the NIEP, . In  it was given a necessary and sufficient condition for a list of5 real numbers, which corresponds to a even-conjugate vector, to be the spectrum of symmetric nonnegative circulant matrix:
Lemma 5Letbe a vector of real numbers (even-conjugate) such that
A necessary and sufficient condition for to be the spectrum of a symmetric nonnegative circulant matrix is
Example 9From Lemma ▭ we may know, for instance, that the list
is the spectrum of a symmetric nonnegative circulant matrix.
7. Some open questions
We finish this chapter by setting two open questions:
Question 1: If the list of real numbersis symmetrically realizable, andis the listalso symmetrically realizable?
Some progress has been done about this question. In , it was given an affirmative answer to Question 1, in the case that the realizing matrix is symmetric nonnegative circulant matrix or it is nonnegative left circulant matrix. In  it was shown that if then Theorem ▭ holds for positive stochastic, positive doubly stochastic and positive symmetric matrices.
Question 2: How adding one or more zeros to a list can lead to its symmetric realizability by different symmetric patterned matrices?
The famous Boyle-Handelman Theorem  gives a nonconstructive proof of the fact that if for then there exists a nonnegative number for which the list with zeros added, is realizable. In  Laffey and Šmigoc completely solve the NIEPfor lists of complex numbers closed under conjugation, with having real parts smaller than or equal to zero. They show the existence of for which with zeros added is realizable and show how to compute the least such The situation for symmetrically realizable spectra is different and even less is known.
The nonnegativeinverse eigenvalue problem is an open and difficult problem. A full solution is unlikely in the near future. A number of partial results are known in the literature about the problem, most of them in terms of sufficient conditions. Some matrix results, like Brauer Theorem (Theorem ▭), Rado Theorem (Theorem ▭), and its symmetric version (Theorem ▭) have been shown to be very useful to derive good sufficient conditions. This way, however, seems to be quite narrow and may be other techniques should be explored and applied.