1. Introduction
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 [1]-[2].
The
Two main subproblems of the
The first sufficient conditions for the existence of a nonnegative
matrix with a given real spectrum (
The first sufficient conditions for the
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 [3]. Necessary condition which is a refinement of is due to Laffey and Meehan [24]. The list for instance, satisfies all above necessary conditions, except condition Therefore is not a realizable list. In [25] 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
2. Brauer and Rado Theorems
A real matrix is said to have
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 [26]). 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 [27], while in [28], 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
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 [30].
Let a nonsingular matrix with
and
Thus,
and we have
3. Real nonnegative inverse eigenvalue problem.
Regarding the
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 [13] 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:
Then, an appropriate nonnegative matrix is
where
For we only have a sufficient condition:
with the following matrix having eigenvalues and diagonal entries and respectively:
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
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
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
Then
has the desired spectrum
4. Symmetric nonnegative inverse eigenvalue problem
Several realizability criteria which were first obtained for the
Since the columns of are an orthonormal set, we may complete to an
orthogonal matrix that is, Then
Therefore,
and is symmetric with eigenvalues
By using Theorem ▭, the following sufficient condition was proved in [22]:
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 [35]:
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:
are necessary and sufficient for the existence of a symmetric nonnegative matrix with eigenvalues and diagonal entries
In [22], the following symmetric nonnegative matrix satisfying conditions (▭), it was constructed:
where
For we have only a sufficient condition:
then there exists a symmetric nonnegative matrix with eigenvalues and diagonal entries
Observe that
has eigenvalues but
We look for a symmetric nonnegative matrix with eigenvalues and diagonal entries Then conditions (▭) are satisfied and from (▭) we compute
where The symmetric matrices
realize Then
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:
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.
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
If then there exists a symmetric nonnegative matrix of order with spectrum
If then there exists a symmetric nonnegative matrix of order with spectrum
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 [37]). 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 the
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 with
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 [38].
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.
Observe that Theorem ▭ gives no information about the realizability of
The list was given in [38]. It
does not satisfy conditions (▭): and
Theorem ▭ (in section 3), can also be extended to the complex case:
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.
We look for a nonnegative matrix with eigenvalues and diagonal entries and a nonnegative matrix realizing They are
Then
has the spectrum
6. Fiedler and Guo results
One of the most important works about the
has eigenvalues where are eigenvalues of the matrix
is also symmetrically realizable.
is symmetrically realizable by a positive matrix.
which is symmetric with eigenvalues where are eigenvalues of
Now we consider a relevant result due to Guo [39]:
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 [40] and also in [41] that Question 1 has an affirmative answer.
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 [42]. The use of circulant matrices has been shown to be very
useful for the
A necessary and sufficient condition for to be the spectrum of a symmetric nonnegative circulant matrix is
is the spectrum of a symmetric nonnegative circulant matrix.
7. Some open questions
We finish this chapter by setting two open questions:
Question 1:
Some progress has been done about this question. In [42], 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 [43] it was shown that if then Theorem ▭ holds for positive stochastic, positive doubly stochastic and positive symmetric matrices.
Question 2:
The famous Boyle-Handelman Theorem [44] 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 [38]
Laffey and Šmigoc completely solve the
8. Conclusion
The
References
- 1.
A. Berman, R. J. Plemmons (1994) Nonnegative Matrices in the Mathematical Sciences. In: Classics in Applied Mathematics 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. - 2.
M. T. Chu, G. H. Golub (2005) Inverse eigenvalue problems: theory, algorithms and applications, Oxford University Press, New York. - 3.
H. Minc (1988) Nonnegative Matrices, John Wiley & Sons, New York. - 4.
R. Loewy, D. London (1978) A note on an inverse problem for nonnegative matrices. In: Linear and Multilinear Algebra 6 83-90. - 5.
M.E. Meehan (1998) Some results on matrix spectra, Ph. D. Thesis, National University of Ireland, Dublin. - 6.
J. Torre-Mayo, M.R. Abril-Raymundo, E. Alarcia-Estévez, C. Marijuán, M. Pisonero (2007) The nonnegative inverse eigenvalue problem from the coefficients of the characteristic polynomial. EBL digraphs In: Linear Algebra Appl. 426 729-773. - 7.
T. J. Laffey, E. Meehan (1999) A characterization of trace zero nonnegative 5x5 matrices. In: Linear Algebra Appl. 302-303 295-302. - 8.
N. Radwan (1996) An inverse eigenvalue problem for symmetric and normal matrices. In: Linear Algebra Appl. 248 101-109. - 9.
O. Rojo, R. L. Soto (2003) Existence and construction of nonnegative matrices with complex spectrum. In: Linear Algebra Appl. 368 53-69 - 10.
A. Borobia, J. Moro, R. L. Soto (2004) Negativity compensation in the nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 393 73-89. - 11.
T. J. Laffey, H. Šmigoc (2006) Nonnegative realization of spectra having negative real parts. In: Linear Algebra Appl. 416 148-159. - 12.
T. J. Laffey (2005) Perturbing non-real eigenvalues of nonnegative real matrices. In: Electronic Journal of Linear Algebra 12 73-76. - 13.
R.L. Soto, M. Salas, C. Manzaneda (2010) Nonnegative realization of complex spectra. In: Electronic Journal of Linear Algebra 20 595-609. - 14.
W. Guo (1996) An inverse eigenvalue problem for nonnegative matrices. In: Linear Algebra Appl. 249 67-78. - 15.
C. R. Johnson, T. J. Laffey, R. Loewy (1996) The real and the symmetric nonnegative inverse eigenvalue problems are different. In: Proc. AMS 124 3647-3651. - 16.
H. R. Suleimanova (1949) Stochastic matrices with real characteristic values. In: Dokl. Akad. Nauk SSSR 66 343-345. - 17.
H. Perfect (1953) Methods of constructing certain stochastic matrices. In: Duke Math. J. 20 395-404. - 18.
H. Perfect (1955) Methods of constructing certain stochastic matrices II. In: Duke Math. J. 22 305-311. - 19.
R. Kellogg (1971) Matrices similar to a positive or essentially positive matrix. In: Linear Algebra Appl. 4 191-204. - 20.
F. Salzmann (1972) A note on eigenvalues of nonnegative matrices. In: Linear Algebra Appl. 5.329-338. - 21.
A. Borobia (1995) On the Nonnegative Eigenvalue Problem. In: Linear Algebra Appl. 223-224 131-140. - 22.
R. L. Soto (2003) Existence and construction of nonnegative matrices with prescribed spectrum. In: Linear Algebra Appl. 369 169-184. - 23.
H. Šmigoc (2005) Construction of nonnegative matrices and the inverse eigenvalue problem. In: Linear and Multilinear Algebra 53 88-96. - 24.
R. L. Soto, O. Rojo (2006) Applications of a Brauer Theorem in the nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 416 (2-3) (2006) 844-856. - 25.
A. Borobia, J. Moro, R. L. Soto (2008) A unified view on compensation criteria the real nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 428 2574-2584. - 26.
R.L. Soto (2011) A family of realizability criteria for the real and symmetric nonnegative inverse eigenvalue problem. In: Numerical Linear Algebra with Appl. (2011). DOI: 10.1002/nla.835. - 27.
P. Egleston, T. Lenker, S. Narayan (2004) The nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 379 475-490. - 28.
C. Marijuán, M. Pisonero, R. L. Soto (2007) A map of sufficient conditions for the real nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 426 (2007) 690-705. - 29.
M. Fiedler (1974) Eigenvalues of nonnegative symmetric matrices. In: Linear Algebra Appl. 9 119-142. - 30.
G. Soules (1983) Constructing symmetric nonnegative matrices. In: Linear and Multilinear Algebra 13 241-251. - 31.
R. Reams (2002) Constructions of trace zero symmetric stochastic matrices for the inverse eigenvalue problem. In: Electronic Journal of Linear Algebra 9 270-275. - 32.
R. Loewy, J. J. McDonald (2004) The symmetric nonnegative inverse eigenvalue problem for matrices. In: Linear Algebra Appl. 393 275-298. - 33.
R. L. Soto (2006) Realizability criterion for the symmetric nonnegative inverse eigenvalue problem. In: Linear Algebra Appl. 416 (2-3) 783-794. - 34.
R. L. Soto, O. Rojo, J. Moro, A. Borobia (2007) Symmetric nonnegative realization of spectra. In: Electronic Journal of Linear Algebra 16 1-18. - 35.
T. J. Laffey, H. Šmigoc (2007) Construction of nonnegative symmetric matrices with given spectrum. In: Linear Algebra Appl. 421 97-109. - 36.
R.L. Soto, O. Rojo, C.B. Manzaneda (2011) On nonnegative realization of partitioned spectra. In: Electronic Journal of Linear Algebra 22 557-572. - 37.
O. Spector (2011) A characterization of trace zero symmetric nonnegative matrices. In: Linear Algebra Appl. 434 1000-1017. - 38.
T. J. Laffey, E. Meehan (1998) A refinament of an inequality of Johnson, Loewy and London on nonnegative matrices and some applications. In: Electronic Journal of Linear Algebra 3 119-128. - 39.
O. Holtz (2004) M-matrices satisfy Newton's inequalities. In: Proceedings of the AMS 133 (3) (2004) 711-717. - 40.
C. R. Johnson (1981) Row stochastic matrices similar to doubly stochastic matrices. In: Linear and Multilinear Algebra 10 113-130. - 41.
A. Brauer (1952) Limits for the characteristic roots of a matrix. IV: Aplications to stochastic matrices. In: Duke Math. J., 19 75-91. - 42.
R. Reams (1996) An inequality for nonnegative matrices and the inverse eigenvalue problem. In: Linear and Multilinear Algebra 41 367-375. - 43.
R. A. Horn, C. R. Johnson (1991) Matrix Analysis, Cambridge University Press, Cambridge. - 44.
R.L. Soto, A.I. Julio (2011) A note on the symmetric nonnegative inverse eigenvalue problem. In: International Mathematical Forum 6 N 50, 2447-2460. - 45.
W. Guo (1997) Eigenvalues of nonnegative matrices. In: Linear Algebra Appl. 266 261-270. - 46.
S. Guo, W. Guo (2007) Perturbing non-real eigenvalues of nonnegative real matrices. In: Linear Algebra Appl. 426 199-203. - 47.
O. Rojo, R. L. Soto (2009) Guo perturbations for symmetric nonnegative circulant matrices. In: Linear Algebra Appl. 431 594-607. - 48.
J. Ccapa, R.L. Soto (2009) On spectra perturbation and elementary divisors of positive matrices. In: Electron. J. of Linear Algebra 18 462-481. - 49.
M. Boyle and D. Handelman, The spectra of nonnegative matrices via symbolic dynamics, Ann.of Math . 133: 249-316 (1991).