Open access peer-reviewed chapter

Nonnegative Inverse Eigenvalue Problem

By Ricardo L. Soto

Submitted: November 17th 2011Reviewed: April 25th 2012Published: July 11th 2012

DOI: 10.5772/48279

Downloaded: 2199

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 nonnegative inverse eigenvalue problem (NIEP)is the problem of characterizing those lists Λ={λ1,λ2,...,λn}of complex numbers which can be the spectra of n×nentrywise nonnegative matrices. If there exists a nonnegative matrix Awith spectrum Λwe say that Λis realized by Aand that Ais the realizing matrix. A set Kof conditions is said to be a realizability criterion if any list Λ={λ1,λ2,...,λn},real or complex, satisfying conditions Kis realizable. The NIEP is an open problem. A full solution is unlikely in the near future. The problem has only been solved for n=3by Loewy and London ([3], 1978) and for n=4by Meehan ([4], 1998) and Torre-Mayo et al.([5], 2007). The case n=5has been solved for matrices of trace zero in ([6], 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 [7]-[8].

Two main subproblems of the NIEP are 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, RNIEP and SNIEP are equivalent for n4(see [9]), but they are different otherwise (see [10]). Moreover, both problems remains unsolved for n5.The NIEP is 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 ([11], 1949) and Perfect ([12], [13], 1953 and 1955). Other sufficient conditions have also been obtained, in chronological order in [14]-[15], (see also [16], [17], and references therein for a comprehensive survey).

The first sufficient conditions for the SNIEP were obtained by Fiedler ([18], 1974). Other results for symmetric realizability have been obtained in [19], [7] and [20]-[21]. Recently, new sufficient conditions for the SNIEP have been given in [22]-[23].

1.1. Necessary conditions

Let Abe a nonnegative matrix with spectrum Λ={λ1,λ2,...,λn}.Then, from the Perron Frobenius theory we have the following basic necessary conditions

(1)Λ¯={λ1¯,...,λn¯}=Λ(2)maxj{λj}Λ(3)sm(Λ)=j=1nλjm0,m=1,2,...,uid2

where Λ¯=Λmeans that Λis closed under complex comjugation.

Moreover, we have

(4)(sk(Λ))mnm-1skm(Λ),k,m=1,2,...(5)(s2(Λ))2(n-1)s4(Λ),nodd,tr(A)=0.uid3

Necessary condition (4)is due to Loewy and London [3]. Necessary condition (5),which is a refinement of (4),is due to Laffey and Meehan [24]. The list Λ={5,4,-3,-3,-3}for instance, satisfies all above necessary conditions, except condition (5).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 RNIEP, the SNIEP and 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 5,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 A=(aij)i=1nis said to have constant row sums if all its rows sum up to the same constant, say, α,that is,j=1naij=α,i=1,...,n.The set of all real matrices with constant row sums equal to αis denoted by 𝒞𝒮α.It is clear that any matrix in 𝒞𝒮αhas eigenvector 𝐞=(1,1,...,1)Tcorresponding to the eigenvalue α.Denote by 𝐞kthe n-dimensional vector with one in the k-thposition and zeros elsewhere.

It is well known that the problem of finding a nonnegative matrix with spectrum Λ={λ1,...,λn}is equivalent to the problem of finding a nonnegative matrix in 𝒞𝒮λ1with 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 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 1 Brauer [29] Let Abe an n×narbitrary matrix with eigenvalues λ1,...,λn.Let 𝐯=(v1,...,vn)Tan eigenvector of Aassociated with the eigenvalue λkand let 𝐪=(q1,...,qn)Tbe any n-dimensional vector. Then the matrix A+𝐯𝐪Thas eigenvalues λ1,...,λk-1,λk+vTq,λk+1,...,λn.

Let Ube an n×nnonsingular matrix such that

U-1AU=λ1**λ2*λn

is an upper triangular matrix, where we choose the first column of Uas 𝐯(Uthere exists from a well known result of Schur). Then,

U-1(A+𝐯𝐪T)U=U-1AU+q1q2qnU=λ1+𝐪T𝐯**λ2*λn.

and the result follows.

This proof is due to Reams [30].

Theorem 2 Rado [13] Let Abe an n×narbitrary matrix with eigenvalues λ1,...,λnand let Ω=diag{λ1,...,λr}for some rn.Let Xbe an n×rmatrix with rank rsuch that its columns x1,x2,...,xrsatisfy Axi=λixi,i=1,...,r.Let Cbe an r×narbitrary matrix. Then the matrix A+XChas eigenvalues μ1,...,μr,λr+1,...,λn,where μ1,...,μrare eigenvalues of the matrix Ω+CX.

Let S=XYa nonsingular matrix withS-1=[]UV.Then UX=Ir,VY=In-rand VX=0,UY=0.Let C=C1C2,X=[]X1X2,Y=[]Y1Y2.Then, since AX=XΩ,

S-1AS=[]UVXΩAY=ΩUAY0VAY

and

S-1XCS=[]Ir0C1C2S=C1C200X1Y1X2Y2=CXCY00.

Thus,

S-1(A+XC)S=S-1AS+S-1XCS=Ω+CXUAY+CY0VAY,

and we have σ(A+XC)=σ(Ω+CX)+σ(A)-σ(Ω).

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 [13], [31], [32], [33].

Theorem 3 [32] Let Λ={λ1,λ2,...,λn}be a given list of real numbers. Suppose that:

i)There exists a partition Λ=Λ1...Λt,where

Λk={λk1,λk2,...λkpk},λ11=λ1,λk1λkpk,λk10,

k=1,...,t,such that for each sublist Λkwe associate a corresponding list

Γk={ωk,λk2,...,λkpk},0ωkλ1,

which is realizable by a nonnegative matrix AkCSωkof order pk.

ii)There exists a nonnegative matrix BCSλ1with eigenvalues λ1,λ21,...,λt1(the first elements of the lists Λk) and diagonal entries ω1,ω2,...,ωt(the first elements of the lists Γk).

Then Λis realizable by a nonnegative matrix ACSλ1.

Perfect [13] gave conditions under which λ1,λ2,...,λtand ω1,ω2,...,ωtare the eigenvalues and the diagonal entries, respectively, of a t×tnonnegative matrix BCSλ1.For t=2it is necessary and sufficient that λ1+λ2=ω1+ω2,with 0ωiλ1.For t=3Perfect gave the following result:

Theorem 4 [13] The real numbers λ1,λ2,λ3and ω1,ω2,ω3are the eigenvalues and the diagonal entries, respectively, of a 3×3nonnegative matrix BCSλ1,if and only if:

i)0ωiλ1,i=1,2,3ii)λ1+λ2+λ3=ω1+ω2+ω3iii)λ1λ2+λ1λ3+λ2λ3ω1ω2+ω1ω3+ω2ω3iv)maxkωkλ2uid8

Then, an appropriate 3×3nonnegative matrix Bis

B=ω10λ1-ω1λ1-ω2-pω2p0λ1-ω3ω3,uid9

where

p=1λ1-ω3(ω1ω2+ω1ω3+ω2ω3-λ1λ2+λ1λ3+λ2λ3).

For t4,we only have a sufficient condition:

i)0ωkλ1,k=1,2,...t,ii)ω1+ω2+ωt=λ1+λ2+λt,iii)ωkλk,ω1λk,k=2,3,...,t,uid10

with the following matrix BCSλ1having eigenvalues and diagonal entries λ1,λ2,...,λtand ω1,ω2,...,ωt,respectively:

B=ω1ω2-λ2ωr-λtω1-λ2ω2ωr-λtω1-λtω2-λ2ωt.uid11

Example 1 Let us consider the list Λ={6,1,1,-4,-4}with the partition

Λ1={6,-4},Λ2={1,-4},Λ3={1}

and the realizable associated lists

Γ1={4,-4},Γ2={4,-4},Γ3={0}.

From () we compute the 3×3nonnegative matrix

B=40232412060

with eigenvalues 6,1,1,and diagonal entries 4,4,0.Then

A=0400040000000400040000000+10010001001000100002320001200600=04002400023200412320401200600

is nonnegative with spectrum Λ.

A map of sufficient conditions for the RNIEP it was constructed in [17], There, the sufficient conditions were compared to establish inclusion or independence relations between them. It is also shown in [17] that the criterion given by Theorem contains all realizability criteria for lists of real numbers studied therein. In [33], from a new special partition, Theorem is extended. Now, the first element λk1of the sublist Λkneed not to be nonnegative and the realizable auxiliar list Γk={ωk,λk1,...,λkpk}contains one more element. Moreover, the number of lists of the partition depend on the number of elements of the first list Λ1,and some lists Λkcan be empty.

Theorem 5 [33] Let Λ={λ1,λ2,...,λn}be a list of real numbers and let the partition Λ=Λ1Λp1+1be such that

Λk={λk1,λk2,...λkpk},λ11=λ1,λk1λk2λkpk,

k=1,...,p1+1,where p1is the number of elements of the list Λ1and some of the lists Λkcan be empty. Let ω2,...,ωp1+1be real numbers satisfying 0ωkλ1,k=2,...,p1+1.Suppose that the following conditions hold:

i)For each k=2,...,p1+1,there exists a nonnegative matrix AkCSωkwith spectrum Γk={ωk,λk1,...,λkpk},

ii)There exists a p1×p1nonnegative matrix BCSλ1,with spectrum Λ1and with diagonal entries ω2,...,ωp1+1.

Then Λis realizable by a nonnegative matrix ACSλ1.

Example 2 With this extension, the authors show for instance, that the list

{5,4,0,-3,-3,-3}

is realizable, which can not be done from the criterion given by Theorem . In fact, let the partition

Λ1={5,4,0,-3},Λ2={-3},Λ3={-3}withΓ2={3,-3},Γ3={3,-3},Γ4=Γ5={0}.

The nonnegative matrix

B=3020030230020320

has spectrum Λ1and diagonal entries 3,3,0,0.It is clear that

A2=A3=0330realizesΓ2=Γ3.

Then

A=A2A300+100010000100010000100001000020000002300002003020=030020300020000302003002300002003020

has the desired spectrum {5,4,0,-3,-3,-3}.

4. Symmetric nonnegative inverse eigenvalue problem

Several realizability criteria which were first obtained for the RNIEP have later been shown to be symmetric realizability criteria as well. For example, Kellogg criterion [14] was showed by Fiedler [18] to imply symmetric realizability. It was proved by Radwan [7] that Borobia's criterion [34] is also a symmetric realizability criterion, and it was proved in [21] that Soto's criterion for the RNIEP is 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 [22] Let Abe an n×nsymmetric matrix with spectrum Λ={λ1,λ2,...,λn}and for some rn,let {𝐱1,𝐱2,...,𝐱r}be an orthonormal set of eigenvectors of Aspanning the invariant subspace associated with λ1,λ2,...,λr.Let Xbe the n×rmatrix with i-thcolumn 𝐱i,let Ω=diag{λ1,...,λr},and let Cbe any r×rsymmetric matrix. Then the symmetric matrix A+XCXThas eigenvalues μ1,μ2,...,μr,λr+1,...,λn,where μ1,μ2,...,μrare the eigenvalues of the matrix Ω+C.

Since the columns of Xare an orthonormal set, we may complete Xto an orthogonal matrix W=[XY],that is, XTX=Ir,YTY=In-r,XTY=0,YTX=0.Then

W-1AW=[]XTYTAXY=ΩXTAY0YTAYW-1(XCXT)W=[]Ir0CIr0=C000.

Therefore,

W-1(A+XCXT)W=Ω+CXTAY0YTAY

and A+XCXTis symmetric with eigenvalues μ1,...,μr,λr+1,...,λn.

By using Theorem , the following sufficient condition was proved in [22]:

Theorem 7 [22] Let Λ={λ1,λ2,...,λn}be a list of real numbers with λ1λ2λnand, for some tn,let ω1,...,ωtbe real numbers satisfying 0ωkλ1,k=1,...,t.Suppose there exists:

i)a partition Λ=Λ1Λtwith

Λk={λk1,λk2,...λkpk},λ11=λ1,λk10,λk1λk2λkpk,

such that for each k=1,...,t,the list Γk={ωk,λk2,...,λkpk}is realizable by a symmetric nonnegative matrix Akof order pk,and

ii)a t×tsymmetric nonnegative matrix Bwith eigenvalues λ11,λ21,...,λt1}and with diagonal entries ω1,ω2,...,ωt.

Then Λis realizable by a symmetric nonnegative matrix.

Since Akis a pk×pksymmetric nonnegative matrix realizing Γk,then A=diag{A1,A2,...,At}is symmetric nonnegative with spectrum Γ1Γ2Γt.Let {𝐱1,...,𝐱t}be an orthonormal set of eigenvectors of Aassociated with ω1,...,ωt,respectively. Then the n×tmatrix Xwith i-thcolumn 𝐱isatisfies AX=XΩfor Ω=dig{ω1,...,ωt}.Moreover, Xis entrywise nonnegative, since each 𝐱icontains the Perron eigenvector of Aiand zeros. Now, if we set C=B-Ω,the matrix Cis symmetric nonnegative and Ω+Chas eigenvalues λ1,...,λt.Therefore, by Theorem the symmetric matrix A+XCXThas spectrum Λ.Besides, it is nonnegative since all the entries of A,X,and Care 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 t×tsymmetrix nonnegative matrix Bwith eigenvalues λ1,...,λtand diagonal entries ω1,...,ωt.

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]: There exists a real symmetric matrix with eigenvalues λ1λ2λtand diagonal entries ω1ω2ωtif and only if

i=1kλii=1kωi,k=1,...,t-1i=1tλi=i=1tωiuid17

For t=2,the conditions () become

λ1ω1,λ1+λ2=ω1+ω2,

and they are also sufficient for the existence of a 2×2symmetric nonnegative matrix Bwith eigenvalues λ1λ2and diagonal entries ω1ω20,namely,

B=ω1(λ1-ω1)(λ1-ω2)(λ1-ω1)(λ1-ω2)ω2.

For t=3,we have the following conditions:

Lemma 1 [18] The conditions

λ1ω1λ1+λ2ω1+ω2λ1+λ2+λ3=ω1+ω2+ω3ω1λ2uid19

are necessary and sufficient for the existence of a 3×3symmetric nonnegative matrix Bwith eigenvalues λ1λ2λ3and diagonal entries ω1ω2ω30.

In [22], the following symmetric nonnegative matrix B,satisfying conditions (), it was constructed:

B=ω1μ-ω32μ-ω2-ω3sμ-ω22μ-ω2-ω3sμ-ω32μ-ω2-ω3sω2(μ-ω2)(μ-ω3)μ-ω22μ-ω2-ω3s(μ-ω2)(μ-ω3)ω3,uid20

where μ=λ1+λ2-ω1;s=(λ1-μ)(λ1-ω1).

For t4we have only a sufficient condition:

Theorem 8 Fiedler [18] If λ1λtand ω1ωtsatisfy

i)i=1sλii=1sωi,s=1,...,t-1ii)i=1tλi=i=1tωiiii)ωk-1λk,k=2,...,t-1,uid22

then there exists a t×tsymmetric nonnegative matrix with eigenvalues λ1,...,λtand diagonal entries ω1,...,ωt.

Observe that

B=521212251212121252121225

has eigenvalues 8,6,3,3,but λ2=6>5=ω1.

Example 3 Let us consider the list Λ={7,5,1,-3,-4,-6}with the partition

Λ1={7,-6},Λ2={5,-4},Λ3={1,-3}withΓ1={6,-6},Γ2={4,-4},Γ3={3,-3}.

We look for a symmetric nonnegative matrix Bwith eigenvalues 7,5,1and diagonal entries 6,4,3.Then conditions () are satisfied and from () we compute

B=6352535462563andC=B-Ω,

where Ω=diag{6,4,3}.The symmetric matrices

A1=0660,A2=0440,A3=0330

realize Γ1,Γ2,Γ3.Then

A=A1A2A3+XCXT,whereX=220022000220022000220022,

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 [33] Let Λ={λ1,λ2,...,λn}be a list of real numbers and let the partition Λ=Λ1Λp1+1be such that

Λk={λk1,λk2,...λkpk},λ11=λ1,λk1λk2λkpk,

k=1,...,p1+1,where Λ1is symmetrically realizable, p1is the number of elements of Λ1and some lists Λkcan be empty. Let ω2,...,ωp1+1be real numbers satisfying 0ωkλ1,k=2,...,p1+1.Suppose that the following conditions hold:

i)For each k=2,...,p1+1,there exists a symmetric nonnegative matrix Akwith spectrum Γk={ωk,λk1,...,λkpk},

ii)There exists a p1×p1symmetric nonnegative matrix Bwith spectrum Λ1and with diagonal entries ω2,...,ωp1+1.

Then Λis symmetrically realizable.

Example 4 Now, from Theorem , we can see that there exists a symmetric nonnegative matrix with spectrum Λ={5,4,0,-3,-3,-3}, which can not be seen from Theorem . Moreover, we can compute a realizing matrix. In fact, let the partition

Λ1={5,4,0,-3},Λ2={-3},Λ3={-3}withΓ2={3,-3},Γ3={3,-3},Γ4=Γ5={0}.

The symmetric nonnegative matrix

B=3060030660020620

has spectrum Λ1and diagonal entries 3,3,0,0.Let Ω=diag{3,3,0,0}and

X=2200022000022000220000100001,A2=A3=0330,C=B-Ω.

Then, from Theorem we obtain

A=A2A300+XCXT,

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 [36] Let Abe an n×nirreducible symmetric nonnegative matrix with spectrum Λ={λ1,λ2,...,λn},Perron eigenvalue λ1and a diagonal element c.Let Bbe an m×msymmetric nonnegative matrix with spectrum Γ={μ1,μ2,...,μm}and Perron eigenvalue μ1.

i)If μ1c,then there exists a symmetric nonnegative matrix C,of order (n+m-1),with spectrum {λ1,...,λn,μ2,...,μm}.

ii)If μ1c,then there exists a symmetric nonnegative matrix C,of order (n+m-1),with spectrum {λ1+μ1-c,λ2,...,λn,μ2,...,μm}.

Example 5 The following example, given in [36], shows that

{7,5,0,-4,-4,-4}with the partition

Λ={7,5,0,-4},Γ={4,-4},

satisfies conditions of Theorem , where

A=40b0040db0060d60withb2+d2=23,bd=46,

is symmetric nonnegative with spectrum Λ.Then there exists a symmetric nonnegative matrix Cwith spectrum {7,5,0,-4,-4}and a diagonal element 4.By applying again Theorem to the lists {7,5,0,-4,-4}and {4,-4},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 RNIEP (see [11]): The list λ1>0>λ2λnis the spectrum of a nonnegative matrix if and only if λ1+λ2++λn0.

Theorem 11 [28] Let Λ={λ0,λ1,...,λn}be a list of complex numbers closed under complex conjugation, with

Λ'={λ1,...,λn}{z:Rez0;RezImz}.

Then Λis realizable if and only ifi=0nλi0.

Suppose that the elements of Λ'are ordered in such a way that λ2p+1,...,λnare real and λ1,...,λ2pare complex nonreal, with

xk=Reλ2k-1=Reλ2kandyk=Imλ2k-1=Imλ2k

for k=1,...,p.Consider the matrix

B=000.-x1+y1x1-y1.-x1-y1y1x1.-xp+yp00.xp-yp-xp-yp00.ypxp-λ2p+100.λ2p+1.-λn0.λn.

It is clear that B𝒞𝒮0with spectrum {0,λ1,...,λn}and all the entries on its first column are nonnegative. Define 𝐪=(q0,q1,...,qn)Twithq0=λ0+i=1nλiand

qk=-Reλkfork=1,...,2pandqk=-λkfork=2p+1,...,n.

Then, from the Brauer Theorem A=B+𝐞𝐪Tis 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].

Theorem 12 [38] Let λ2,λ3,...,λnbe nonzero complex numbers with real parts less than or equal to zero and let λ1be a positive real number. Then the list Λ={λ1,λ2,...,λn}is the nonzero spectrum of a nonnegative matrix if the following conditions are satisfied:

i)Λ¯=Λii)s1=i=1nλi0iii)s2=i=1nλi20uid30

The minimal number of zeros that need to be added to Λto make it realizable is the smallest nonnegative integer Nfor which the following inequality is satisfied:

s12(n+N)s2.

Furthermore, the list {λ1,λ2,...,λn,0,...,0}can be realized by C+αI,where Cis a nonnegative companion matrix with trace zero, αis a nonnegative scalar and Iis the n×nidentity matrix.

Corollary 1 [38] Let λ2,λ3,...,λnbe complex numbers with real parts less than or equal to zero and let λ1be a positive real number. Then the list Λ={λ1,λ2,...,λn}is the spectrum of a nonnegative matrix if and only if the following conditions are satisfied:

i)Λ¯=Λii)s1=i=1nλi0iii)s2=i=1nλi20iv)s12ns2uid32

Example 6 The list Λ={8,-1+3i,-1-3i,-2+5i,-2-5i}satisfies conditions (). Then Λis the spectrum of the nonnegative companion matrix

C=01000001000001000001232049427812.

Observe that Theorem gives no information about the realizability of Λ.

The list {19,-1+11i,-1-11i,-3+8i,-3-8i}was given in [38]. It does not satisfy conditions (): s1=11,s2=11ands12ns2.The inequality 112(5+N)11is satisfied for N6.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 [8] Let Λ={λ2,λ3,...,λn}be a list of complex numbers such that Λ¯=Λ,λ1maxiλi,i=2,...,n,andi=1nλi0.Suppose that:

i)there exists a partition Λ=Λ1Λtwith

Λk={λk1,λk2,...λkpk},λ11=λ1,

k=1,...,t,such that Γk={ωk,λk2,...,λkpk}is realizable by a nonnegative matrix Ak𝒞𝒮ωk,and

ii)there exists a t×tnonnegative matrix B𝒞𝒮λ1,with eigenvalues

λ1,λ21,...,λt1(the first elements of the lists Λk)and with diagonal entries ω1,ω2,...,ωt(the Perron eigenvalues of the lists Γk).

Then Λis realizable.

Example 7 Let Λ={7,1,-2,-2,-2+4i,-2-4i}.Consider the partition

Λ1={7,1,-2,-2},Λ2={-2+4i},Λ3={-2-4i}withΓ1={3,1,-2,-2},Γ2={0},Γ3={0}.

We look for a nonnegative matrix B𝒞𝒮7with eigenvalues 7,-2+4i,-2-4iand diagonal entries 3,0,0,and a nonnegative matrix A1realizing Γ1.They are

B=304417087070andA1=0201200101020120.

Then

A=A100+100100100100010001000004417000087000070=020104200104010204012004417000087000070

has the spectrum Λ.

6. Fiedler and Guo results

One of the most important works about the SNIEP is due to Fiedler [18]. In [18] Fiedler showed, as it was said before, that Kellogg sufficient conditions for the RNIEP are also sufficient for the SNIEP. Three important and very useful results of Fiedler are:

Lemma 2 [18] Let Abe a symmetric m×mmatrix with eigenvalues α1,...,αm,A𝐮=α1𝐮,𝐮=1.Let Bbe a symmetric n×nmatrix with eigenvalues β1,...,βn,B𝐯=β1𝐯,𝐯=1.Then for any ρ,the matrix

C=Aρ𝐮𝐯Tρ𝐯𝐮TB

has eigenvalues α2,...,αm,β2,...,βn,γ1,γ2,where γ1,γ2are eigenvalues of the matrix

C˜=α1ρρβ1.

Lemma 3 [18] If {α1,...,αm}and {β1,...,βn}are lists symmetrically realizable and α1β1, then for any t0,the list

{α1+t,β1-t,α2,...,αm,β2,...,βn}

is also symmetrically realizable.

Lemma 4 [18] If Λ={λ1,λ2,...,λn}is symmetrically realizable by a nonnegative matrix and if t>0,then

Λt={λ1+t,λ2,...,λn}

is symmetrically realizable by a positive matrix.

Remark 1 It is not hard to see that Lemma can be obtained from Theorem . In fact, it is enough to consider

C=AB+𝐮00𝐯0ρρ0𝐮T0T0T𝐯T=Aρ𝐮𝐯Tρ𝐯𝐮TB,

which is symmetric with eigenvalues γ1,γ2,α2,...,αm,β2,...,βn,where γ1,γ2are eigenvalues of

B=α1ρρβ1.

Now we consider a relevant result due to Guo [39]:

Theorem 14 [39] If the list of complex numbers Λ={λ1,λ2,...,λn}is realizable, where λ1is the Perron eigenvalue and λ2,then for any t0the list Λt={λ1+t,λ2±t,λ3,...,λn}is also realizable.

Corollary 2 [39] If the list of real numbers Λ={λ1,λ2,...,λn}is realizable andt1=i=2ntiwith ti,i=2,...,n,then the list Λt={λ1+t1,λ2+t2,...,λn+tn}is also realizable.

Example 8 Let Λ={8,6,3,3,-5,-5,-5,-5}be a given list. Since the lists Λ1=Λ2={7,3,-5,-5}are both realizable (see [31] to apply a simple criterion, which shows the realizability of Λ1=Λ2), then

Λ1Λ2={7,7,3,3,-5,-5,-5,-5}

is also realizable. Now, from Theorem , with t=1,Λ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 Λ={λ1,λ2,...,λn}is symmetrically realizable, and t>0,is the list Λt={λ1+t,λ2±t,λ3,...,λn}symmetrically realizable?.

It was shown in [40] and also in [41] that Question 1 has an affirmative answer.

Theorem 15 [40] Let Λ={λ1,a+bi,a-bi,λ4,...,λn}be a realizable list of complex numbers. Then for all t0,the perturbed list

Λt={λ1+2t,a-t+bi,a-t-bi,λ4,...,λn}

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 NIEP [27], [32]. In [32] it was given a necessary and sufficient condition for a list of 5 real numbers, which corresponds to a even-conjugate vector, to be the spectrum of 5×5symmetric nonnegative circulant matrix:

Lemma 5 [32] Let λ=(λ1,λ2,λ3,λ3,λ2)Tbe a vector of real numbers (even-conjugate) such that

λ1λj,j=2,3λ1λ2λ3λ1+2λ2+2λ30uid45

A necessary and sufficient condition for {λ1,λ2,λ3,λ3,λ2}to be the spectrum of a symmetric nonnegative circulant matrix is

λ1+(λ3-λ2)5-12-λ20.uid46

Example 9 From Lemma we may know, for instance, that the list

{6,1,1,-4,-4}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 numbers Λ={λ1,λ2,...,λn}is symmetrically realizable, and t>0,is the list Λt={λ1+t,λ2±t,λ3,...,λn}also symmetrically realizable?

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 1>λ2λn0,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 [44] gives a nonconstructive proof of the fact that if sk=λ1k+λ2k++λnk>0,for k=1,2,...,then there exists a nonnegative number Nfor which the list {λ1,...,λn,0,...,0},with Nzeros added, is realizable. In [38] Laffey and Šmigoc completely solve the NIEP for lists of complex numbers Λ={λ1,...,λn},closed under conjugation, with λ2,...,λnhaving real parts smaller than or equal to zero. They show the existence of N0for which Λwith Nzeros added is realizable and show how to compute the least such N.The situation for symmetrically realizable spectra is different and even less is known.

8. Conclusion

The nonnegative inverse 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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Ricardo L. Soto (July 11th 2012). Nonnegative Inverse Eigenvalue Problem, Linear Algebra - Theorems and Applications, Hassan Abid Yasser, IntechOpen, DOI: 10.5772/48279. Available from:

Embed this chapter on your site Copy to clipboard

<iframe src="http://www.intechopen.com/embed/linear-algebra-theorems-and-applications/nonnegative-inverse-eigenvalue-problem" />

Embed this code snippet in the HTML of your website to show this chapter

chapter statistics

2199total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Identification of Linear, Discrete-Time Filters via Realization

By Daniel N. Miller and Raymond A. de Callafon

Related Book

First chapter

Cramer’s Rules for the System of Two-Sided Matrix Equations and of Its Special Cases

By Ivan I. Kyrchei

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us