The diagonalizable nonnegative inverse eigenvalue problem 7 Anthony G. Cronin and Thomas J. Laffey 1 ∗ † 0 2 n a Abstract J 5 In this paper we prove that the SNIEP = DNIEP, i.e. the symmetric and diagonal- 2 6 izable nonnegative inverse eigenvalue problems are different. We also show that the ] O minimum t > 0 for which (3+t,3 t, 2, 2, 2) is realizable by a diagonalizable − − − − C matrix is t = 1, and we distinguish diagonalizably realziable lists from general real- . izable lists using the Jordan Normal Form. h t a m AMS Subject Classification: 15A18; 15A29; 47A75; 58C40 [ Keywords: Nonnegative matrices; Inverse eigenvalue problem; Spectral theory 1 v 1 1 Introduction 5 6 8 Classifying spectra of nonnegative matrices is know as the nonnegative inverse eigenvalue 0 . problem or NIEP. The real nonnegative inverse eigenvalue problem or RNIEP is to de- 1 0 termine necessary and sufficient conditions on the list of n real numbers (λ ,λ ,...,λ ) 1 2 n 7 so that σ be the spectrum of an entry-wise nonnegative matrix. Such a matrix is then 1 : said to realize σ. If we further require that the realizing matrix be symmetric we call the v i problem the symmetric nonnegaitive inverse eigenvalue problem or SNIEP. Both prob- X r lems are unsolved for n 5 though the trace zero case for 5 5 matrices was solved by a ≥ × Spector [17]. The two problems are the same for n 4 but are different for n 5 as was ≤ ≥ first shown by Johnson, Laffey and Loewy in [6]. The first significant breakthrough in this problem was Suleimanova’s result [19] on lists of real numbers with just one positive number, which says that the real list λ > 0 λ λ is realizable if and only 1 2 n ≥ ≥ ··· ≥ if λ + λ + + λ 0. The question of realizing real lists of five or more numbers 1 2 n ··· ≥ containing just two positive numbers is still unsolved in general. 1.1 Necessary conditions The Perron-Frobenius theory ([14],[3]) says (among other things) that the spectral radius of an irreducible nonnegative matrix must be contained in the spectrum of that matrix i.e. max λ : λ σ σ. j j {| | ∈ } ∈ ∗School of Mathematics and Statistics, University College Dublin, Ireland, [email protected] †School of Mathematics and Statistics, University College Dublin, Ireland, thomas.laff[email protected] In this context the spectral radius ρ is known as the Perron root and for irreducible nonnegative matrices ρ > 0 and it occurs just once as an eigenvalue. We define the power sums s as follows k s := λk +λk + +λk, for k = 1,2,.... k 1 2 ··· n Notice that if σ = (λ ,λ ,...,λ ) is the spectrum of a nonnegative matrix A then the 1 2 n power sums isalsothetraceofthekth power ofarealizing matrixAforσ. Independently k Loewy and London [11] and Johnson [6] derived an infinite set of inequalities which the spectrum of a nonnegative matrix must satisfy, namely that nm−1s sm for k,m = 1,2,... km ≥ k known as the JLL conditions. Necessary conditions for both the RNIEP and the SNIEP thus include: max λ : λ σ σ (1) j j {| | ∈ } ∈ s 0 for k = 1,2,... (2) k ≥ nm−1s sm for k,m,n = 1,2,.... (3) km ≥ k Anewnecessary conditionfortheSNIEPwhen thetraceisatleast halfthespectral radius is given by Loewy and Spector in [18]. A necessary condition for general n involving only the first three power sums s is given by Cronin and Laffey in [1]. k 2 A classic example σ = 3,3, 2, 2, 2 { − − − } The list σ = 3,3, 2, 2, 2 , in the guise τ = (1,1, 2, 2, 2) was first studied by { − − − } −3 −3 −3 Salzmann in 1971 [15] and Friedland in 1977 [2]. As can be checked the list τ satisfies the necessary conditions (1), (2) and (3) for all positive integers k,m and n. However the list τ is not realizable. For if it were, a realizing matrix would have to be reducible as the Perron root occurs twice. As can be easily seen, any such reducible ma- trix having this spectrum would require the list to be partionable into two lists which are separately realizable, and this leads to a negative trace realization which is forbidden by (2). Laffey and Meehan in [8] showed that in order for a list of five numbers which sum to zero to berealizable, we must have a refined JLL inequality satisfied, in particular 4s s2 0. 4− 2 ≥ For σ (which is 3τ) we have 4s s2 = 840 900 < 0 and so again we see that σ cannot t 4− 2 − be realizable. 2.1 σ = 3 + t,3, 2, 2, 2 t { − − − } The related problem of trying to realize σ = 3+t,3, 2, 2, 2 for the minimum value t { − − − } of t > 0 is unsolved. In her thesis, Meehan [13] showed that σ is realizable for t 0.519310982048 and a t ≥ ··· realizing matrix of the form t 1 0 0 0 p 0 1 0 0 A = 0 q 0 1 0     0 0 0 0 1   0 0 w h 0   is presented. She also shows that for a 5 5 extreme (or Perron extreme) matrix [7], 4s s2 +s2s s41 0 which for σ , me×ans t 0.39671 . 4 − 2 1 2 − 2 ≥ t ≥ ··· Hence the range for the minimum value of t for which σ is realizable is t 0.39671 t 0.51931 ···≤ ≤ ··· This classic example highlights the difficulty in moving from the NIEP for n = 5 and trace zero to the positive trace case in the NIEP, even when the numbers of the list are all real. 2.1.1 σ = 3+t,3, 2, 2, 2 in the symmetric case t { − − − } We note that for t = 1, σ = (3 + t,3, 2, 2, 2), is symmetrically realizable by the t − − − matrix 0 2 2 0 0 2 0 2 0 0  A = 2 2 0 0 0     0 0 0 1 √6   0 0 0 √6 0    and this is the best possible t in the symmetric case. Thus the RNIEP and the SNIEP are different for n = 5, and this is the first case in which they differ [6]. The interested reader should consult Loewy and London [11], for the proofs that the RNIEP=SNIEP for n 4. ≤ 2.2 σ = 3 + t,3 t, 2, 2, 2 { − − − − } A further related problem of finding the minimum value of t > 0 for which the list b σ = (3+t,3 t, 2, 2, 2) is realizable, is solved. Note that the sum of the elements t − − − − in σ is zero and so any realizing matrix for σ must have trace zero. Also note, as is the t t b case for σ = (3+t,3 t, 2, 2, 2), that any realizing matrix for σ must be irreducible. b − − − − b The minimum value of t for which σ = (3 + t,3 t, 2, 2, 2) is realziable in the t − − − − symmetric case must be at least one. This can be seen by considering the sign pattern b of the eigenvector z associated with the second largest eigenvalue 3 t of a realizing − matrix A = At. Now z cannot have all its entries positive (or negative) as only the Perron eigenvector (and its scalar multiples) has this property. Thus z (or z) has either one or − two positive entries (and hence either four or three non-positive entries). Without loss of generality we can permute the entries of z so that its positive entries, denoted with a + below, occur in the first position(s) of the vector i.e. + +   + − z = or     − −     − −     − − where the minus sign means the corresponding entry is less than or equal to zero. Now if z has just one positive entry then Az = (3 t)z implies − 0 A z z 12 1 = (3 t) 1 (cid:20)A A (cid:21)(cid:20) z (cid:21) − (cid:20) z (cid:21) 21 22 2 2 where A is (1 4), A is (4 1), and A is (4 4), and z = [z z ]t where z > 0 and 12 21 22 1 2 1 × × × z 0, for z R,z R4. But this implies A zt = (3 t)z which is false as the left 2 ≤ 1 ∈ 2 ∈ 12 2 − 1 hand side of this equation is non-positive and the right hand side is positive. Hence this sign pattern(onepositive component followed by fournon-positive) for z isnot permitted. So z must have 2 positive entries and 3 non-positive entries. For simplicity we write z = [u v]t where u = [u u ]t and v = [v v v ]t where u ,v 0 1 2 1 2 3 i j − ≥ for each i and j. From the eigenvalue/eigenvector equation Az = (3 t)z we have that − A A u u 11 12 = (3 t) (cid:20)A A (cid:21)(cid:20) v (cid:21) − (cid:20) v (cid:21) 21 22 − − where A is (2 2), A is (3 3), and z = [u v]t where u > 0 and v 0 are vectors 11 22 × × − ≥ in R2 and R3 respectively. Thus A u A v = (3 t)u implies (A (3 t)I )u 0 since the vector A v is non- 11 12 11 2 12 − − − − ≥ positive. But this implies, by a corollary of the Courant-Fischer theorem, (see Theorem 8.3.2 of [5]), that ρ(A ) (3 t), where ρ denotes the Perron root of A . Thus A has 11 11 11 ≥ − an eigenvalue ν with ν (3 t). (4) ≥ − Now A is a (2 2) nonnegative matrix with trace zero since tr(A) = 0 and so its 11 × eigenvalues are say, ν and ν. But A is symmetric which means the interlacing property − holds i.e. any principal submatrix of A cannot have an eigenvalue larger than the largest eigenvalue of A or an eigenvalue smaller than the smallest eigenvalue of A. Hence the eigenvalues of A must satisfy 2 ν, ν 3+t. 11 − ≤ − ≤ By (4), this means 2 ν t 3 which gives t 1. − ≤ − ≤ − ≥ This argument is due to McDonald and Neumann [12] and we will make use of it again later when the condition symmetric is replaced by diagonalizable. More generally, for a list of five real numbers λ ,λ ,λ ,λ ,λ satisfying 1 2 3 4 5 λ λ λ λ λ , McDonald and Neumann [12] showed that λ +λ trace(A) 1 2 3 4 5 2 5 ≥ ≥ ≥ ≥ ≤ where A is a symmetric realizing matrix. Hence for σ we must have that (3 t)+( 2) 0 which again implies t 1. t − − ≤ ≥ For t = 1, σ = (3+t,3 t, 2, 2, 2) is symmetrically realizable by t b − − − − b 0 2 0 0 0 2 0 0 0 0 A = 0 0 0 2 2     0 0 2 0 2   0 0 2 2 0   and so t = 1 is the best possible result in the symmetric case - this was first proven by Loewy and Hartwig (unpublished). 2.2.1 σ = 3+t,3 t, 2, 2, 2 in the general case t { − − − − } Howeverbinthegeneral (non-symmetric) caseLaffeyandMeehanshowthatσt must satisfy the necessary condition b 4s s2. 4 ≥ 2 This requires that t t := 16√6 39 = 0.43799 0 ≥ q − ··· and they show that the matrix 0 1 0 0 0  15+t2 0 1 0 0 2 A = 0 0 0 1 0      0 0 0 0 1 3t4 +58t2 +3 t4+78t2−15 10+6t2 15+t2 0  4 2  is nonnegative for t t and has spectrum (3+t,3 t, 2, 2, 2). 0 ≥ − − − − This result shows thatthebelief thatt = 1was theminimum t > 0 required for realization of σ in the general NIEP is false. t Also note, that by the result of Guo [4], the list (3+t,3, 2, 2, 2) is realizable b − − − for all t 2t = 0.87598 . ≥ 0 ··· b b 3 D-RNIEP = SNIEP 6 Next we examine the subtle difference between the SNIEP and the Diagonalizable RNIEP or D-RNIEP, where the D-RNIEP is the problem of finding a nonnegative diagonalizable matrix realizing a given real spectrum σ. Again we consider the list σ = (3+t,3 t, 2, 2, 2). We note that for t − − − − b1 t t = 120√1066 3899 = 0.4354153419 0 ≥ 10q − ··· the perturbed list (3+t,3 t, 1.9, 2, 2.1) is the spectrum of the matrix − − − − 0 1 0 0 0  1501+100t2 0 1 0 0 200 A = 0 0 0 1 0 .      0 0 0 0 1 15000t4+289950t2+14649 10000t4+779800t2−148199 150t2+249 1501+100t2 0  5000 40000 25 200  The (5,2) entry of the matrix A is nonnegative if 10000t4 + 779800t2 148199 and ≥ this holds for t t . Also note that this matrix is diagonalizable as it has five distinct 0 ≥ eigenvalues. However if the list (3 + t,3 t, 1.9, 2, 2.1) is to be symmetrically realizable by a − − − − matrix A we can use the Courant-Fischer argument again to say that the Perron root ν 1 of some principal 2 2 submatrix A say, must be at least 3 t. 11 × − Let ν = 3 t+ǫ where ǫ 0. 1 − ≥ The eigenvalues ν ,ν of A must satisfy ν +ν = 0 (since tr(A = 0). 1 2 11 1 2 11 Now consider the matrix A+(2.1)I . 5 This matrix has eigenvalues 5.1+t,5.1 t,0.2,0.1 and 0 and so is positive-semidefinite. − Now tr(A +(2.1)I ) = 4.2 since tr(A ) = 0, and from this we get that, 11 2 11 4.2 = 5.1 t+ǫ+µ 2 − where µ = ν + 2.1. Since every principal submatrix of a positive-semidefinite matrix 2 2 inherits positive-semidefiniteness we must have that µ 0 and so we get 2 ≥ µ = 0.9+t ǫ 0 = t 0.9. 2 − − ≥ ⇒ ≥ Hence the two problems of D-RNIEP and SNIEP are different at least in this case. We also note that for small ǫ > 0 the spectrum (3+t,3 t, 2+ǫ, 2, 2 ǫ) is diago- − − − − − nalizably realizable (five distinct eigenvalues) for t close to 16√6 39 = 0.43799 . − ··· Spector showed that for this t the same list is symmetricallyprealizable also. However this is not a continuous property in ǫ since we have the following Proposition 1. Suppose σ = (3 + t,3 t, 2, 2, 2) is realizable by a diagonalizable t − − − − matrix A, then t 1. ≥ b To prove this result we will make use of the following fact. Lemma 2. Let B B B = 11 12 (cid:20)B B (cid:21) 21 22 be an n n matrix. × If rank(B) =rank(B ) = k and B−1 exists, then B = B B−1B . 11 11 22 21 11 12 Proof. Note that I 0 B B B B 11 12 = 11 12 , (cid:20) B B−1 I(cid:21)(cid:20)B B (cid:21) (cid:20) 0 B B B−1B (cid:21) − 21 11 21 22 22 − 21 11 12 where I and 0 are the identity and zero matrices of appropriate dimensions respectively. Since rank(B)=rank(B ) = k the rowspace of B is spanned by the rows of B extended 11 11 in to B . Hence for any row r , j = k +1,k +2,...,n, 12 j in B B B−1B to be written as a linear combination of rows in B extended we 22 − 21 11 12 11 must have that r = α r +α r + +α r +α r + +α r . But r ,r ,...,r are already linearly j 1 1 2 2 k k k+1 k+1 n n 1 2 k ··· ··· independent, so α = α = = α = 0. Hence r = 0 for j = k +1,k+2,...,n. 1 2 n j ··· Proof of Proposition 1 Proof. Suppose t < 1. Note for σ = (3+t,3 t, 2, 2, 2) to be realizable by a diagonalizable matrix A, then t − − − − A must be irreducible. b Let wT > 0 be the left eigenvector associated with the Perron eigenvalue 3+t, so wTA = (3+t)wT, where T denotes the transpose. Let v be the right eigenvector associated with the eigenvalue 3 t, so Av = (3 t)v. − − Then (3+t)wTv = wTAv = wT(3 t)v wTv = 0 v has some negative components. − ⇒ ⇒ By the earlier argument we know that v cannot have just one negative (or positive) component. Hence we can write Az = (3 t)z as − A A z z 11 12 1 = (3 t) 1 (cid:20)A A (cid:21)(cid:20) z (cid:21) − (cid:20) z (cid:21) 21 22 2 2 − − where A is (2 2), A is (3 3), and z ,z 0 are column vectors in R2 and R3 11 22 1 2 × × ≥ respectively. Then (againusing theMcDonald-Neumann argument) thePerroneigenvalue of A is at least 3 t and hence A has spectrum (3 t + ǫ) where ǫ 0, since 11 11 − ± − ≥ tr(A ) = 0. Since A is diagonalizable the minimum polynomial of A is 11 m (x) = (x (3+t))(x (3 t))(x+2) A − − − so that (A (3+t)I)(A (3 t)I)(A+2I) = 0 − − − (A2 6A+(9 t2)I)(A+2I) = 0 ⇒ − − A3 4A2 (3+t2)A+(18 2t2)I = 0 ⇒ − − − A3 +(18 2t2)I = 4A2 +(3+t2)A. (5) ⇒ − Now A diagonalizable also implies there exists a nonsingular matrix T with T−1(A+2I )T = (5+t) (5 t) (0 ). 5 3 ⊕ − ⊕ Now rank(A+2I) = 2 since rank(A +2I ) = 2. 11 2 Note that A has trace zero and so A +2I has the form 11 11 2 a 12 . (cid:20)a 2 (cid:21) 21 So det(A +2I) = 4 a a 11 12 21 − Since rank(A + 2I) = 2 we have that rank(A + 2I ) 2 since the rank of a leading 22 3 ≤ principal submatrix cannot exceed the rank of the original matrix. Thus A + 2I has 22 3 zero as an eigenvalue (as it does not have full rank) and hence 2 is an eigenvalue of A . 22 − ApplyingtheMcDonald-NeumannargumentagainwehavethatA z A z = (3 t)z 21 1 22 2 2 − − − so that (A (3 t))z = A z 0 and so A has an eigenvalue 3 t+ǫ′ where ǫ′ 0. 22 2 21 1 22 − − ≥ − ≥ Since tr(A ) = 0, A has eigenvalues 3 t+ǫ′, 1+t ǫ′, 2. 22 22 − − − − Now consider the tr(A2) where A2 +A A A A +A A A2 = 11 12 21 11 12 12 22 (cid:18) A A +A A A A +A2 (cid:19) 21 11 22 21 21 12 22 and the the tr(A3) where A3 = A A A2 +A A A A +A A = 11 12 11 12 21 11 12 12 22 (cid:18) A A (cid:19)(cid:18) A A +A A A A +A2 (cid:19) 21 22 21 11 22 21 21 12 22 A3 +A A A +A (A A +A A ) = 11 11 12 21 12 21 11 22 21 ∗ (cid:18) A (A A +A A )+A3 +A A A (cid:19) ∗∗ 21 11 12 12 22 22 22 21 12 where * and ** do not contribute to the trace of A3. Let α = tr(A A ) = tr(A A ) 12 21 21 12 β = tr(A A A ) and 11 12 21 γ = tr(A A A ). 12 22 21 Using (5) we see that the contribution to trI, tr(A), tr(A2) and tr(A3) from positions (1,1) and (2,2) yields that 4 2(3 t+ǫ)2 +α = 2β +γ +2(18 2t2). − − (cid:0) (cid:1) Applying Lemma 2 to A+2I= A +2I A 11 2 12 (cid:20) A A +2I (cid:21) 21 22 3 we get that A +2I = A (A +2I )−1A . 22 3 21 11 2 12 Now (A +2I )−1 11 2 1 2 a = − 12 det(A +2I ) (cid:20) a 2 (cid:21) 11 2 21 − 1 2 a 12 = − − (5 t+ǫ)(1 t+ǫ) (cid:20) a 2 (cid:21) 21 − − − 1 2 a = − 12 (5 t+ǫ)(1 t+ǫ)) (cid:20)a 2(cid:21) 21 − − − (A 2I ) = 11 − 2 . (5 t+ǫ)(1 t+ǫ)) − − So A + 2I = A21(A11−2I2)A12. Note that trA = 0 so upon comparing traces in this 22 3 (5−t+ǫ)(1−t+ǫ)) 22 equation we get that tr(A A A ) 2tr(A A ) 21 11 12 21 12 6 = − (5 t+ǫ)(1 t+ǫ)) − − β 2α = − . (5 t+ǫ)(1 t+ǫ)) − − Now consider the contribution from the top two positions on the main diagonal to the traces of both sides of equation (5). We have that 2β +γ +36 4t2 = 8(3 t+ǫ)2 +4α − − This implies 12(5 t+ǫ)(1 t+ǫ)+4α+γ +36 4t2 = 72 48t+8t2 +16ǫ(3 t)+8ǫ2 − − − − − ⇒ 24+24ǫ+4ǫ2 +4ǫ+γ (24t+8ǫt) = 0. − But note that 24 24t > 0 since t < 1, and 24ǫ 8ǫt = 16ǫ+8ǫ 8ǫt > 0, implies that the − − − left hand side of this equation is positive and the right hand side is zero which contradicts our hypothesis that t < 1. Hence t 1. ≥ Laffey and Smigoc [9] proved that (3+t,3 t, 2, 2, 2,0) is symmetrically realizable − − − − by a 6 6 matrix for t 1. The fact that the value t = 1 is necessary in this case and in × ≥ 3 3 the case σ (0,0) has been checked by computer search by Lixing Han (unpublished) at t the UniversSity of Michigan-Flint and the same realizing matrix was found. We conjecture b that t = 1 is the best bound for any number of zeros added to the spectrum σ . Also 3 t b Lixing Han’s extensive computer searches in the cases n = 6 and n = 7 failed to find a counterexample to this bound. 4 A note on the dependence of realizable spectra on the Jordan Form structure The matrix 0 8 1 0 0  8 0 1 0 0 1 A = 75 75 0 1 0 4  2 2     0 0 0 0 1   829 829 256 110 0   has spectrum σ3 = (3+ 3,3 3, 2, 2, 2) and minimal polynomial 4 4 − 4 − − − 3 3 x (3+ ))(x (3 ))(x+2)2 (cid:18) − 4 − − 4 (cid:19) andsoitdistinguishes thediagonalizablyrealizablelistsfromthosewithCanonicalJordan 2 1 Form structure (3+t) (3 t) ( 2) − with t = 3. ⊕ − ⊕ − ⊕(cid:20) 0 2(cid:21) 4 − Hence the D-RNIEP is different to the general NIEP. Note that this matrix was built up from a 4 4 nonnegative matrix with spectrum (3 + 3,3 3, 2, 2) having the entry × 4 − 4 − − 2 on the diagonal using the Sˇmigoc methods deployed in [16]. The question of whether every realizing matrix can be chosen to be nonderogatory remains open and will require further ideas related to this paper. 5 Conclusion In this paper we proved that the SNIEP = D-RNIEP and that the D-RNIEP can be 6 distinguished from the general NIEP by examining the Jordan Normal Form. We also showed that the minimum t > 0 for which (3 + t,3 t, 2, 2, 2) is realizable by a − − − − diagonalizable matrix is t = 1. References [1] A. Cronin, T.J. Laffey, An inequality for the spectra of nonnegative matrices, Linear Algebra Appl, 436(9), (2012), 3225-3238. [2] S. Friedland, On an inverse problem for nonnegative and eventually nonnegative matrices, Israel J. Math., 29(1), (1978), 43-60. [3] G. Frobenius, Ueber Matrizen aus nicht negativen Elementen, Sitzungsber. Knigl. Preuss. Akad. Wiss., (1912), 456-477.