Open access peer-reviewed chapter

Nonnegative Inverse Elementary Divisors Problem

By Ricardo L. Soto

Submitted: September 22nd 2015Reviewed: January 12th 2016Published: July 6th 2016

DOI: 10.5772/62234

Downloaded: 769

Abstract

Inverse eigenvalue problems appear in a wide variety of areas in the pure and applied mathematics. They have to do with the construction of a certain matrix from some spectral information. Associated with any inverse eigenvalue problem, there are two important issues: the existence of a solution and the construction of a solution matrix. The purpose of this chapter is to study the nonnegative inverse elementary divisors problem (hereafter, NIEDP) and its state of the art. The elementary divisors of a given matrix A are the characteristic polynomials of the Jordan blocks of the Jordan canonical form of A. The NIEDP looks for necessary and sufficient conditions for the existence of a nonnegative matrix with prescribed elementary divisors. Most of the content of this chapter is based on recent results published by the author and collaborators from the Mathematics Department at Universidad Católica del Norte, Chile.

Keywords

  • nonnegative matrices
  • elementary divisors
  • Jordan canonical form
  • nonnegative inverse eigenvalue problems
  • nonnegative inverse elementary divisors problems

1. Introduction

Inverse problems appear in a wide variety of disciplines and they may be of many different kinds. Inverse eigenvalue problems, for instance, 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. Inverse eigenvalue problems have to do with constructing a certain matrix from some spectral information. Associated with any inverse eigenvalue problem, there are two important issues: the existence of a solution and the construction of a solution matrix. The structure of the solution matrix (usually it is not unique) plays a fundamental role in the study of the inverse eigenvalue problems. It is necessary to properly formulate the problem, otherwise it could become a trivial one. Chu and Golub [1] say that “an inverse eigenvalue problem should always be a structured problem.” In this chapter, we study the Nonnegative Inverse Elementary Divisors Problem (hereafter, the NIEDP), which is the problem of finding necessary and sufficient conditions for the existence of a nonnegative matrix with prescribed elementary divisors.

Let A be an n × n complex matrix, and let

JA=S1AS=Jn1λ1000Jn2λ2000JnkλkE100

be its Jordan canonical form (hereafter, JCF). The ni × ni submatrices

Jniλi=λi1λi1λi,i=1,2,,kE200

are called the Jordan blocks of J(A). The elementary divisors of A are the polynomials λλini,that is, the characteristic polynomials of Jniλi,i = 1, …, k. The inverse elementary divisors problem (IEDP) is the problem of determining necessary and sufficient conditions under which the polynomials λλ1n1,λλ2n2,,λλknk,n 1 + ⋯ + nk = n, are the elementary divisors of an n × n matrix A. It is clear that for any arbitrarily prescribed Jordan canonical form J, and for any nonsingular matrix S, there exists a matrix A = SJS− 1 with J as its JCF. In order that the problem be meaningful, the matrix A is required to have a particular structure. When A is required to be an entrywise nonnegative matrix, the problem is called the nonnegative inverse elementary divisors problem (NIEDP) (see [24]). The NIEDP is strongly related to another inverse problem, the nonnegative inverse eigenvalue problem (hereafter, the NIEP), which is the problem of determining necessary and sufficient conditions for a list of complex numbers Λ = {λ1λ2, …, λn} to be the spectrum of an n × n entrywise nonnegative matrix. If there exists a nonnegative matrix A with spectrum Λ, we say that Λ is realizable and that A is the realizing matrix. The NIEDP contains the NIEP, and both problems are equivalent if the prescribed eigenvalues are all distinct. Both problems remain unsolved (the NIEP is solved only for n ≤ 4). A number of sufficient conditions or realizability criteria for the NIEP to have a solution are known in the literature regarding the problem (see [5] and the references therein). In contrast, only a few works are known about the NIEDP (see [3, 4, 612]) According to Minc [2], the NIEDP looks for to give an answer to the question: which matrices are similar to a nonnegative matrix?

A matrix A=aiji,j=1nis said to have constant row sums if all its rows sum up to the same constant, say α, i.e.

j=1naij=α,i=1,,n.E300

The set of all matrices with constant row sums equal to α is denoted by CSα. It is clear that any matrix in CSαhas the eigenvector e = (1, 1, …1)T corresponding to the eigenvalue α. A nonnegative matrix A is called stochastic if ACS1and it is called doubly stochastic if A,ATCS1.For lack of simplicity, we shall call nonnegative generalized stochastic to a nonnegative matrix ACSαand nonnegative generalized doubly stochastic to a nonnegative matrix A with A,ATCSα.The relevance of matrices with constant row sums is due to the well-known fact that if Λ = {λ1λ2,…, λn} is the spectrum of a nonnegative matrix, then Λ is also the spectrum of a nonnegative matrix with constant row sums equal to its Perron eigenvalue (spectral radius).

Denote by ek the vector with one in the k-th position and zeros elsewhere. Let S be a nonsingular matrix such that S− 1AS = J(A) is the JCF of A. If ACSλ1,S can be chosen so that Se1 = e and, in this case, it is easy to see that the rows of S− 1 = (ŝij) satisfy:

j=1ns^1j=1andj=1ns^ij=0,i=2,,n.E1

If T is an n × n matrix of the form

T=λ100,andS=1s12s1n1s22s2n1sn2snnE400

is nonsingular, then STS− 1e = λ1e, that is, STS1CSλ1.We shall denote by Eij the n × n matrix with 1 in the (ij)th position and zeros elsewhere. The following simple perturbation allows us to join two or more Jordan blocks corresponding to a same eigenvalue λp to obtain one Jordan block of a bigger size: Let A be an n × n matrix with JCF J(A). Let the Jordan blocks Jm1λp,Jm2λp,,Jmqλpbe corresponding to the eigenvalue λp. Let ξ=j=1p1mj,1 ≤ p ≤ k, with ξ = 0 if p = 1, and let E=iKEi,i+1.Then by using the perturbation J(A) + E, with

K=ξ+m1,ξ+m1+m2,,ξ+i=1q1mi,E600

we obtain a Jordan block of bigger size Jγ(λp), corresponding to the elementary divisor (λ − λp)γ, γ = m1 + m2 + … + mq.

Observe that if E=iKEi,i+1with K ⊂ {1, 2, …, n − 1}, and A is an n × n complex matrix with JCF J(A) = S− 1AS, then for an appropriate set K

JA+E=S1AS+E=S1A+SES1SE700

is the JCF of A + SES− 1. If ACSλ1and S = [e| ∗ | ⋯ |∗], then

A+SES1CSλ1.E800

The first works on the NIEDP are due to H. Minc [3, 4]. Minc studied the problem for nonnegative and doubly stochastic matrices, modulo the NIEP. In particular, he proved the following two results, which we collect as:

Theorem 1 Minc [3] Let Λ = {λ1λ2, …, λn} be a list of complex numbers, which is realizable by a diagonalizable positive (diagonalizable positive doubly stochastic) matrix A. Then, for each JCF JΛ associated with Λ, there exists a positive (positive doubly stochastic) matrix B with the same spectrum as A, and with JCF J(B) = JΛ.

According to Minc, the positivity condition is essential in his proof, and it is not known if the result holds without this condition (see [2]). Specifically, it is not known: i) whether for every positive matrix, there exists a diagonalizable positive matrix with the same spectrum, ii) whether for every nonnegative diagonalizable matrix with spectrum Λ = {λ1, …, λn}, there exists a nonnegative matrix for each JCF associated with Λ.

Usually, to work with the NIEDP, we are given a list of complex numbers Λ = {λ1λ2, …, ;n}, from which we want to construct a nonnegative or positive matrix with spectrum Λ and with prescribed elementary divisors. In this sense, we mention two matrix perturbation results, which have been employed in connection with the NIEP and the NIEDP, to derive sufficient conditions for the existence and construction of nonnegative matrices with prescribed spectrum and prescribed elementary divisors. The first result, due to Brauer [13, Theorem 27], shows how to change a single eigenvalue of an n × n matrix, via a rank-1 perturbation, without changing any of the remaining n − 1 eigenvalues. The second result, due to R. Rado and introduced by Perfect in [14], is an extension of the Brauer result. It shows how to change r eigenvalues of an n × n matrix A via a rank-r perturbation, without changing any of the remaining n − r eigenvalues (see [15] to understand how Rado's result is applied to the NIEP). The proof of the Brauer result, which we give here, is due to R. Reams [16].

Theorem 2 Brauer [13] Let A be an n × n arbitrary matrix with eigenvalues λ1, …, λn. Let v = (v1,…, vn)T an eigenvector of A associated with the eigenvalue λk and letq = (q1,…, qn)T be any n-dimensional vector. Then the matrix A + vq T has eigenvalues λ1, …, λk − 1λk + v T qλk + 1, …, λn.

Proof. [16] From the Schur's triangularization theorem, let U be an n × n nonsingular matrix such that

U1AU=λ1λ2λnE900

is an upper triangular matrix, with v being the first column of U. Then,

U1A+vqTU=U1AU+q1q2qnU=λ1+qTvλ2λn.E501

and the result follows.■

Theorem 3 Rado [14] Let A be an n × n arbitrary matrix with eigenvalues λ1, …, λn and let Ω = diag{λ1, …, λr} for some r ≤ n. Let X be an n × r matrix with rank r such that its columns x1x2, …, xr satisfy Axi = λi xi, i = 1, …, r. Let C be an r × n arbitrary matrix. Then the matrix A + XC has eigenvalues μ1, …, μrλr + 1, …, λn,where μ1, …, μr are eigenvalues of the matrix Ω + CX.

Proof. Let S = [X|Y] a nonsingular matrix with S1=VU.Then UX = Ir, VY = In − r, and VX = 0, UY = 0. Let C = [C1|C2], X=X2X1,Y=Y2Y1.Then, since AX = ,

S1AS=UVXΩ|AY=ΩUAY0VAYE502

and

S1XCS=Ir0C1|C2S=C1C200X1Y1X2Y2=CXCY00.E503

Thus,

S1A+XCS=S1AS+S1XCS=Ω+CXUAY+CY0VAY,E13

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

The following result in [6], which will be frequently used later, shows how is the JCF of the Brauer perturbation A + eq T .

Lemma 1 [6] Let ACSλ1be with JCF

JA=S1AS=diagJ1λ1,Jn2λ2,,JnkλkE14

Let q T  = (q1, …, qn) and λ1+i=1nqiλi,i = 2, …, n. Then the JCF of A + eq T is JA+i=1nqiE11.In particular, if i=1nqi=0,then A and A + eq T are similar.

2. Cases completely solved

In this section, we shall discuss about certain subproblems of the NIEDP, for which a complete solution has been obtained. We start with a list of real nonnegative numbers Λ = {λ1λ2, …, λn} with λ1 > λ2 ≥ ⋯ ≥ λn ≥ 0. Let D = diag{λ1λ2, …, λn}. In [17], Perfect shows that the matrix

P=1111111110111100E2

has the property that PDP1CSλ1is positive diagonalizable with spectrum Λ. Then we have:

Theorem 4 [6] Let Λ = {λ1, …, λn} be a list of real numbers with λ1 > λ2 ≥ ⋯ ≥ λn ≥ 0. Then, there exists a nonnegative matrix ACSλ1with spectrum Λ, for each possible JCF associated with Λ.

Proof. Let D = diag{λ1λ2, …, λn} and let P be the matrix in (2). Then PDP1CSλ1is positive (generalized stochastic) with spectrum Λ and linear elementary divisors. Let

K2,3,,n1andE=iKEi,i+1,E16

such that D + E is the desired JCF. Then there exists ε > 0 such that A = PDP− 1 + εPEP− 1 is nonnegative, and since D + εE and D + E are diagonally similar (with diag{1, εε2, …, ε n − 1}), A has JCF equal to D + E. Moreover, since P e1 = e, the rows of P− 1 satisfy (1) and PEP− 1 e = 0. Thus ACSλ1has the desired elementary divisors. ■

The following two cases correspond, respectively, to lists Λ = {λ1, …, λn} of real numbers satisfying λ1 > 0 > λ2 ≥ ⋯ ≥ λn, which are called lists of Suleimanova type; and to lists Λ = {λ1, …, λn} of complex numbers satisfying λi ∈ ℱ, i = 2, …, n, where

=z:Rez<0,RezImz,E17

which are called lists of complex Suleimanova type. In both cases, the NIEP has a solution if and only if i=1nλi0(see [18, 19]).

Let Λ = {λ1, …, λn} be a list of complex numbers with Λ¯=Λ,i=1nλi0,and λ1 ≥ |λi|, i = 2, …, n. In [9, Theorem 2.1], the authors define

M=max2kn0,Reλk+Imλkm=k=2nmin0,Reλk,ImλkE18

and show that if λ1 ≥ M + m, when all possible Jordan blocks Jniλi,of size ni ≥ 2, are associated to a real eigenvalue λi < 0; or when there is at least one Jordan block Jniλi,of size ni ≥ 2, associated to a real eigenvalue λi ≥ 0 with M=Reλi0+Imλi0,for some i0, then there exists an n × n nonnegative matrix ACSλ1with spectrum Λ and with prescribed elementary divisors. The result in [9, Theorem 2.1] was used by the authors to prove the following

Corollary 1 [9] Let Λ = {λ1, …, λn} be a list of complex numbers with λi ∈ ℱ, i = 2, …, n. Then, for each possible JCF associated with Λ, there exists a nonnegative matrix ACSλ1with spectrum Λ if and only if i=1nλi0.

Proof. The condition is necessary for the existence of a nonnegative matrix with spectrum Λ. The condition is also sufficient. In fact, since

M=max2kn0,Reλk+Imλk=0,E19
m=k=2nmin0,Reλk,Imλk=k=2nReλk=k=2nλi,E20

then if λ1 + λ2 + ⋯ + λn ≥ 0, λ1k=2nλi=M+m.

In [19, Theorem 3.3], the authors show that if Λ = {λ1, …, λn} is a list of complex numbers with λi ∈ ℱ, i = 2, …, n, then there exists a nonnegative matrix with spectrum Λ if and only if i=1nλi0.Thus we have:

Corollary 2 [6] Let Λ = {λ1, …, λn} be a list of real numbers with λ1 > 0 > λ2 ≥ ⋯ ≥ λn. Then, for each possible JCF associated with Λ, there exists a nonnegative matrix ACSλ1with spectrum Λ if and only if i=1nλi0.

In [20], Šmigoc extends the result in [19, Theorem 3.3], to the region

G=z:Rez<0,3RezImz,E21

that is, she shows that if Λ = {λ1, …, λn} is a list of complex numbers with λiG,i = 2, …, n, then there exists a nonnegative matrix with spectrum Λ if and only if i=1nλi0.The following result extends Corollary 1 to lists of complex numbers Λ = {λ1, …, λn}, with λiG,i = 2, …, n. Before, to state this result and its proof, we need the following lemmas, which we set here without proof:

Lemma 2 [20] Let A=A1abTcbe an n × n matrix and let B be an m × m matrix with JCF JB=c00IB.Then the matrix

C=A1atTsbTB,Bs=cs,tTB=ctT,withtTs=1,E22

has JCF

JC=JA00IB.E23

Lemma 3 [12] Let Λ = {λ1a ± bi, …, a ± bi} be a list of n complex numbers, with n ≥ 3, a < 0, b > 0. If

λ1maxn1a,2n5a2+b22a,E3

then for each JCF associated with Λ, there exists an n × n nonnegative matrix A = (aij), with spectrum Λ and entry ann = s1(Λ).

Corollary 3 [12] Let Λ = {λ1a ± bi, …, a ± bi} be a list of n complex numbers, with 0 < b3a.Then, for each JCF associated with Λ, there exists a nonnegative matrix A = (aij) with spectrum Λ and entry ann = s1(Λ), if and only if λ1 + (n − 1)a ≥ 0.

Proof. It is clear that the condition is necessary. Assume that λ1 + (n − 1)a ≥ 0. Since 0 < b3a,it follows that

maxn1a,2n5a2+b22aE25
=maxn1a,n1a+3a2b22aE26
=n1aE27
λ1.E28

Hence, from Lemma 3, Λ is the spectrum of a nonnegative matrix A = (aij) with entry ann = s1(Λ), for each JCF associated with Λ.

Now we state the main result of this section:

Theorem 5 [12] Let Λ = {λ1, …, λn} be a list of complex numbers with λiG,i = 2, …, n. Then, for each JCF associated with Λ, there exists a nonnegative matrix A with spectrum Λ and entry ann=i=1nλiif and only if i=1nλi0.

Proof. It is clear that the condition is necessary. Let λ1 > 0 > λ2 ≥ ⋯ ≥ λp be real numbers and let λp+1,λp+2=λ¯p+1,,λn1,λn=λ¯n1be complex nonreal numbers, with s1Λ=i=1nλi0.Let m be the number of distinct pairs of complex conjugate. Consider the partition

Λ0=λ1λ2λpE29
Λr=s1Λr1,λp+r,λ¯p+r,,λp+r,λ¯p+r,r=1,,mE30

with Λr having nr + 1 elements, where nr is the number of elements of Λr − {s1(Λr − 1)}, in such a way that r=1mnr=np.The list Λ0 satisfies Corollary 2, and then, we can compute a matrix A0=aij0with spectrum Λ0, the entry app0=s1Λ0and with arbitrarily prescribed elementary divisors. Moreover, since 0<Imλp+r3Reλp+r,r = 1, …, m, there exists, from Corollary 3, a nonnegative matrix Ar=aijrof size nr + 1, with spectrum Λr, entry anr+1,nr+1r=s1Λr,for each JCF associated with Λr. Finally, by employing the Lemma 2 (Šmigoc Lemma) m times, we construct a nonnegative matrix A with spectrum Λ and with arbitrarily prescribed elementary divisors. ■

Example 1 Let

Λ=23,1,1,1,2±3i,2±3i,3±5i,3±5iE31

be given. We want to construct a 12 × 12 nonnegative matrix with elementary divisors

λ23,λ+12,λ+1,λ2+4λ+132E32
λ+35i,λ+35i,λ+3+5i,λ+3+5i.E33

Consider the lists

Λ0=23,1,1,1E34
Λ1=20,2±3i,2±3iE35
Λ2=12,3±5i,3±5i.E36

Clearly Λ0 is realizable by a nonnegative matrix A0, with elementary divisors (λ − 23), (λ + 1)2, (λ + 1), and entry a440=20.Λ1 and Λ2 are also realizable by nonnegative matrices A1, with elementary divisors (λ − 20), (λ2 + 4λ + 13)2, and entry a551=12,and A2, with linear elementary divisors (λ − 12), (λ + 3 ± 5i), (λ + 3 ± 5i), and entry a552=0,respectively (see Corollary 3). By applying Lemma 2 to the matrices A0 and A1 we obtain an 8 × 8 nonnegative matrix B1 = (bij) with spectrum Λ0 ∪ Λ1 − {20}, elementary divisors

λ23,λ+12,λ+1,λ2+4λ+132E37

and entry b88 = 12. Next, we employ Lemma 2 again with the matrices B1 and A2, to obtain a nonnegative matrix A with spectrum Λ and the prescribed elementary divisors.

The method that we employ to prove Theorem 5, allow us to compute, under certain conditions, a nonnegative matrix A with spectrum Λ = {λ1, …, λn}, where λiG,i = 2, …, n, for each JCF associated with Λ. However, this procedure does not work for any list of complex numbers in the left half plane. In particular, the list

Λ=6,1+3i,13i,1+3i,13iE38

satisfies the Laffey and Šmigoc conditions [21], and therefore, it is realizable. However, Λ does not satisfy the condition of Lemma 3. As a consequence, we cannot obtain, from Lemma 3, a nonnegative matrix with spectrum Λ and linear elementary divisors.

3. General sufficient conditions

In this section, we start with a general result, which gives a simple sufficient condition for the existence and construction of a nonnegative matrix with prescribed spectrum and elementary divisors. In particular, the result stated that if the Perron eigenvalue λ1 is large enough, then the list Λ = {λ1, …, λn} is the spectrum of a nonnegative matrix with prescribed elementary divisors. Since the result and its proof are somewhat involved, we start with the following example in order to illustrate the ideas and the constructive procedure followed in the proof:

Example 2 Let Λ = {λ1, 3, 3, − 1, − 1, − 1 ± 3i, − 1 ± 3i}.

Case i): We want to construct a nonnegative matrix A with elementary divisors

J1λ1,J13,J13,J21,J21+3i,J213i.E39

We consider the initial matrix

D=λ1331113311331.E40

Let S = [e|e2| ⋯ |e9] and E = E4,5 + E7,8. Then

B=SD+εES1E41
=λ1λ133λ133λ1+1ε1ελ1+11λ1213λ1+4ε31ελ1213λ1+431.E42

It is clear that BCSλ1has the desired JCF. Now, in order that B becomes nonnegative, we take

qT=10,0,0,1,1,3,1,3,1,ε1,E43

and apply Theorem 2 (Brauer result) to obtain the nonnegative matrix A = B + eq T , where λ1 ≥ 10 + 3 = 13. Moreover, from Lemma 1, A has the prescribed elementary divisors. Observe that the values 3 and 10 represent the cost we must pay to obtain A. These values are defined as

M=max2kn0,Reλk+ImλkandE44
m=k=2nmin0,Reλk,Imλk.E45

In this case, M = 3 and m = 10.

Case ii): Now, suppose we want to construct a nonnegative matrix A with elementary divisors

J1λ1,J23,J21,J21+3i,J213i.E46

In this case, we take E = E2,3 + E4,5 + E7,8, and

B=SD+εES1E47
=λ1λ13ε3ελ133λ1+1ε1ελ1+11λ1213λ1+4ε31ελ1213λ1+431.E48

By choosing

qT=10,0,0,1,1,3,1,3,1,ε>0,E49

we obtain A = B + eq T , which for λ1 > M + N = 13, is nonnegative with spectrum Λ, and with the prescribed elementary divisors.

Now we state the mentioned result. A proof of it can be found in [9, Theorem 2.1].

Theorem 6 [9] Let Λ = {λ1λ2, …, λn} be a list of complex numbers with Λ¯=Λ,i=1nλi0,and λ1 ≥ |λi|, i = 2, …, n. Let

M=max2in0,Reλi+Imλi;m=i=2nmin0,Reλi,Imλi,E4

if

i)λ1M+m,E5

when all possible Jordan blocks Jniλi, of size ni ≥ 2, are associated to a real eigenvalue λi < 0; or when there is at least one Jordan block Jniλi, of size ni ≥ 2, associated to a real eigenvalue λi ≥ 0 with M=Reλi0+Imλi0,for some i0 ≤ n − 1.

or if

ii)λ1>M+m,E6

when at least one Jordan block Jniλi, of size ni ≥ 2, is associated to a real eigenvalue λi ≥ 0 with M = λk ≥ 0,

then there exists an n × n nonnegative matrix ACSλ1with spectrum Λ and with prescribed elementary divisors

λλ1,λλ2n2,,λλknk,n2++nk=n1.E53

Let AXC, and Ω be as in Theorem 3, with

S1A+XCS=Ω+CXUAY+CY0VAY,E54

where B = Ω + CX is an r × r matrix with eigenvalues μ1, …, μr (the new eigenvalues) and diagonal entries λ1, …, λr (the former eigenvalues). Then from a result in [2, Chapter VI, Lemma 1.2], if B = Ω + CX and VAY have no common eigenvalues, A + XC is similar to B ⊕ VAY. Then we have:

Lemma 4 Let AXYVC, and Ω be as above. If the matrices B = Ω + CX and VAY have no common eigenvalues, then

JA+XC=JBJVAY.E55

In particular, if CX = 0, A and A + XC are similar.

The following result extends Theorem 6:

Theorem 7 [9] Let Λ = {λ1λ2, …, λn} be a list of complex numbers with Λ=Λ¯,λ1 ≥ max i|λi|, i = 2, …, n; i=1nλi0.Let Λ=Λ0Λ1Λp0be a pairwise disjoint partition, with Λk=λk1λk2λkpk;λ11 = λ1, k = 1, …, p0, where Λ0 is realizable, p0 is the number of elements of the list Λ0 and some lists Λk, k = 1, …, p0, can be empty. Let ω1,,ωp0be real numbers satisfying 0 ≤ ωk ≤ λ1, k = 1, …, p0. Suppose that

i) For each k = 1, …, p0, there exists a list Γk=ωkλk1λkpkwith ωk ≥ Mk + mk or ωk > Mk + mk, as in Theorem 6, where

Mk=max1ipk0,Reλki+Imλki;mk=i=1pkmin0,Reλki,Imλki,E56

and

ii) there exists a p0 × p0 nonnegative matrix B with spectrum Λ0 and diagonal entries ω1,,ωp0.

Then there exists an n × n nonnegative matrix MCSλ1with spectrum Λ and with prescribed elementary divisors.

Proof. Let

Dk=ωkλksReλks+1Imλks+1Imλks+1Reλks+1Reλkpk1Imλkpk1Imλkpk1Reλkpk1E57

with spectrum Γk and let Ek = ∑Ei,i + 1 such that Dk + εEk is the prescribed JCF. Let Sk=e|e2||epk.Then Ak=SkDk+εEkSk1CSωk,k = 1, …, p0, and

A=A1A2Ap0.E58

From i), there exists an appropriate vector qkT=qk0qkp1qkpk,with j=0pkqkj=0,such that Ak+eqkTis nonnegative for each k = 1, …, p0. From Lemma 1, Ak+eqkThas the prescribed elementary divisors. Thus, from Theorem 3, M = A + XC is nonnegative with spectrum Λ and from Lemma 4, M has the prescribed elementary divisors.■

Example 3 Let Λ = {7, 1, − 2, − 2, − 1 + 3i, − 1 − 3i}. We construct a nonnegative matrix A with spectrum Λ and with elementary divisors

λ7,λ1,λ+22,λ+13i,λ+1+3i.E59

Consider the partition Λ = Λ0 ∪ Λ1 ∪ Λ2 ∪ Λ3 with

Λ0=7,1+3i,13i;Λ1=2,2;Λ2=1;Λ3=0andΓ1=4,2,2;Γ2=11;Γ3=0.E60

The matrix

B=403347187070E61

has the spectrum Λ0 with diagonal entries 4, 1, 0. Then, from Theorem 7, we have

A=022000301000220000000100000010000000+100100100010010001000003347000087000700=022003301003220003347001087347000187000700E62

with the prescribed spectrum and elementary divisors.

4. NIEDP for generalized doubly stochastic matrices

In this section, we provide sufficient conditions for the existence of nonnegative generalized doubly stochastic matrices with prescribed elementary divisors. In particular, we show how to transform a generalized stochastic matrix, not necessarily nonnegative, with given elementary divisors, into a nonnegative (positive) generalized doubly stochastic matrix, at the expense of increasing the Perron eigenvalue, but keeping other elementary divisors unchanged. This is what the following result does:

Theorem 8 [11] Let Λ = {λ1, …, λn} be a list of complex numbers, with Λ¯=Λ,i=1nλi>0,λ1 > |λi|, i = 2, …, n. where λ1, …, λp are real and λp + 1, …, λn are complex nonreal numbers. Let

λλ1,λλ2n2,,λλknk,n2++nk=n1,E63

the prescribed elementary divisors (prescribed JCF). Let M be as defined in ( 4) and let mk = − min{0, Rk, Ik}, k = 2, …, n. If each of the following statements hold:

i)

ii) λ1 > Reλk + Imλk + n(mk), k = 2, …, n,

iii)

where ε < 0, with

εminmin2kpλk,minp+1knImλk,1ti=1nλi,E7

for real λk ≠ 0, k = 2, …, p, or

εminminp+1knImλk,1ti=1nλi,E8

if λk = 0, with λk being the zero of an elementary divisor λλknk,nk ≥ 2, and t being the total number of times that ε appears in the prescribed JCF, in certain positions (ii + 1), i = 2, …, n − 1, then there exists a nonnegative generalized doubly stochastic matrix with the prescribed elementary divisors.

Proof. Let λi be real, i = 2, …, p, and let xj = Reλj and yj = Imλj, j = p + 1, …, n − 1. Consider the initial matrix ACSλ1,

A=λ1λ1λlελlελ1λlλlλ1xhyhxhyhλ1xh+yhεyhxhελ1xhyhxhyhλ1xh+yhyhxhλ1xn1+yn1yn1xn1,E68

which has the desired JCF. First, from Theorem 2, we can transform A into a nonnegative matrix A'CSλ1.Let

rk=mk,k=2,,nandE69
rT=k=2nrk,r2,r3,,rn.E70

Then from condition i), the matrix A' = A + er T is nonnegative, A'CSλ1,and from Lemma 1, it has same elementary divisors as A. We now describe how to perturb A' to make it nonnegative generalized doubly stochastic. Define

qT=k=2nqk,q2,q3,,qn,E71

with

qk=1nλ1ReλkImλknrkεE72

if the kth column of A has ε above Imλk or above a real λk, and

qk=1nλ1ReλkImλknrk,k=2,,n,E73

otherwise. Let B = A' + eq T . Again by Lemma 1, B has the same elementary divisors as A' (which are the same of A). From ii) it is clear that all entries of B, on columns 2 to n, are nonnegative. For the (1, 1) entry of B, we have, from (7) or (8), and assuming that ε appears a total of t times in positions (ii + 1), that

λ1k=2nrkk=2nqk=λ1k=2nrk1nk=2nλ1ReλkImλknrk+1ntεE74
=1nk=1nλk+tε0.E75

In position (k, 1), k = 2, …, n, we have from condition iii) that

λ1ReλkImλkk=2nrkk=2nqk=1nk=1nλk+tεReλkImλk0.E76

Thus, all entries in B are nonnegative. Now we show that B,BTCSλ1:It is clear that BCSλ1:Be=A'+eqTe=λ1e.Then, since the row sums are each λ1, and from the way in which the qk were defined, each the columns 2, …, n have column sum λ1. The first column sum is also λ1.■

Example 4 Let Λ = {λ1, 2, 2, − 1 + i, − 1 − i, − 1 + i, − 1 − i}. We want to construct a nonnegative generalized doubly stochastic matrix with elementary divisors (λ − λ1), (λ + 2)2, ((λ + 1)2 + 1)2. We start with the 7 × 7 initial matrix ACSλ1,and the desired JCF:

A=λ1000000λ12ε2ε0000λ12020000λ1001100λ1+2ε0011ε0λ1000011λ1+2000011.E77

We apply Theorem 2 to transform A into a nonnegative matrix A'=A+erTCSλ1,where for ε = − 1,

rT=k=27rk,r2,,r7=5,0,1,1,1,1,1E78

Then we obtain

A'=A+erT=λ15011111λ16201111λ17031111λ15010211λ12010001λ15011102λ13011100,E79

which, by Lemma 1 is a nonnegative generalized stochastic matrix for all λ1 ≥ 7, with the same elementary divisors as A. We now perturb A' to make it nonnegative generalized doubly stochastic. Define

qT=k=27qk,q2,,q7,withq1=176λ133E80
q2=17λ12,q3=17λ18,q4=17λ17E81
q5=17λ15,q6=17λ17,q7=17λ14E82

Then B = A' + eq T is nonnegative generalized doubly stochastic, with same elementary divisors as A, provided that

λ17176λ1330,thatisλ116.E83

The following result extends Theorem 8. A proof, which is built on the basis of Theorem 3, can be found in [11, Theorem 3.1]. The constructive nature of the proof allows us to compute a solution matrix.

Theorem 9 [11] Let Λ = {λ1λ2, …, λn} be a list of complex numbers with Λ¯=Λ,i=1nλi>0,λ1 > |λi|, i = 2, …, n. Suppose there exists a partition Λ=Λ0Λ1Λp0with

Λ0=λ01λ02λ0p0,λ01=λ1E84
Λk=λk1λk2λkpk,pk=p,k=1,,p0,E85

where the lists Λk, k = 1, …, p0, have cardinality p, in such a way that:

i) For each k = 1, …, p0, there exists a list

Γk=ωkλk1λkpk,0<ωk<λ1E86

which is realizable by a nonnegative (positive) matrix Ak, with Ak,AkTCSωk,and with prescribed elementary divisors

λωk,λλk1nk1,,λλkjnkj,nk1++nkj=pk,E87

ii) There exists a p0 × p0 nonnegative (positive) matrix B=biji,j=1nsuch that B,BTCSλ1,with spectrum Λ0 and diagonal entries ω1,ω2,,ωp0,and with certain of the prescribed elementary divisors.

Then there exists a nonnegative (positive) matrix A, such that A,ATCSλ1,with spectrum Λ and with the prescribed elementary divisors associated to the lists Λk.

Example 5 Let Λ = {12, 5, 2, 2, 0, − 1, − 1, − 2 + i, − 2 − i}. To construct a positive generalized doubly stochastic matrix A with elementary divisors

λ12,λ5,λ22,λ,λ+12,λ2+4λ+5E88

we take the partition

Λ0=1250,Γ1=722,Γ2=6,2+i,2i,Γ3=4,1,1E89

and we compute the positive generalized doubly stochastic matrices

A1=13105671134512,A2=1329753101161,A3=13156723453E90

with spectra Γ1Γ2Γ3, and elementary divisors (λ − 7), (λ − 2)2; (λ − 6), λ2 + 4λ + 5; and (λ − 4), (λ + 1)2, respectively. Moreover, we compute

B=714264354withspectrumΛ0,andC=014204350.E91

Finally

XCXT=13000111444000111444000111444222000444222000444222000444333555000333555000333555000,andA=A1A2A3+XCXTE92

is positive generalized doubly stochastic matrix with the prescribed elementary divisors.

5. NIEDP for persymmetric matrices

In this section, we consider the NIEDP for persymmetric matrices. Persymmetric matrices are common in physical sciences and engineering. They arise, for instance, in the control of mechanical and electric vibrations, where the eigenvalues of the Gram matrix, which is symmetric and persymmetric, play an important role [22]. As the superscript T, in A T , denotes the transpose of A, the superscript F, in A F , denotes the flip-transpose of A, which flips A across its skew-diagonal. If A = (aij) mn, then A F  = (an − j + 1,m − i + 1) nm. A matrix A is said to be persymmetric if A F  = A, that is, if it is symmetric across its lower-left to upper-right diagonal. Let J be the n × n matrix with ones along its skew-diagonal and zeroes elsewhere, that is, J = [e n|e n − 1| ⋯ |e1]. Then

JT=JF=J,J2=I,AF=JATJ,E93

and the following properties are straightforward:

AFF=A,ATF=AFT,A+BF=AF+BF,ABF=BFAF.E94

Proposition 10 If A and B are persymmetric matrices, then i) aA + bB, with ab ∈ ℝ, ii) A− 1, if A− 1 exists, and iii) A T , are also persymmetric.

Proof. i) (aA + bB) F  = aA F  + bB F  = aA + bB.

ii) I = A− 1 A implies A F (A− 1) F  = A(A− 1) F  = I. Hence, (A− 1) F  = A− 1.

iii)(AT)F=(AF)T=AT.

In this section, we give sufficient conditions for the existence of nonnegative persymmetric matrices with prescribed elementary divisors. Our result generates an algorithmic procedure to compute a solution matrix. We also show that companion matrices are similar to persymmetric ones. As a consequence, we show that any realizable list of complex numbers Λ = {λ1, …, λn}, with Reλi ≤ 0, i = 2, …, n, is in particular realizable by a nonnegative persymmetric matrix.

In [23], the authors develop the following persymmetric version of Rado's Theorem 3, which allow us to obtain sufficient conditions for the existence of a persymmetric nonnegative matrix with prescribed spectrum.

Theorem 11 [23] Let A be an n × n persymmetric matrix with spectrum

Λ = {λ1λ2, …, λn}, and for some r ≤ n, let {x1x2, …, x r} be a set of eigenvectors of A corresponding to λ1, …, λr, respectively. Let X be the n × r matrix with i − th column x i and rank(X) = r. Let Ω = diag{λ1, …, λr}, and let C be an r × r persymmetric matrix. Then, the matrix A + XCX F is persymmetric with eigenvalues μ1μ2, …, μrλr + 1, …, λn, where μ1μ2, …, μr are eigenvalues of B = Ω + CX F X.

Let Λ = {λ1λ2, …, λn} be a list of complex numbers, which can be partitioned as

Λ=Λ0Λ1Λp02Λp02Λ1,forevenp0,withΛ0=λ01λ02λ0p0,λ01=λ1,Λk=λk1λk2λkpk,k=1,2,,p02,E9

where some of the lists Λk can be empty. For each list Λk, we associate the list

Γk=ωkλk1λk2λkpk,0ωkλ1,E10

which is realizable by a (pk + 1) × (pk + 1) nonnegative matrix Ak. In particular, Ak can be chosen as AkCSωk.

Let the n × p0 matrix

X=x1xp02yp02y1,forevenp0.E11

where, x k = e = [1, 1, …, 1] T and yk=yk1ykpk+1T0are, respectively, the Perron eigenvectors of Ak and AkF,k=1,2,,p02.It was shown in [23] that in the case of even p0, X F X is diagonal persymmetric nonnegative matrix with positive main diagonal. To apply Theorem 11, we need to find a p0 × p0 persymmetric nonnegative matrix C, where B = Ω + CX F X is persymmetric nonnegative with eigenvalues μ1,μ2,,μp0(the new eigenvalues) and diagonal entries ω1,,ωp02,ωp02,,ω1(the former eigenvalues), and Ω=diagω1,,ωp02,ωp02,,ω1. Thus, since X F X is nonsingular, we may compute C = (B − Ω)(X F X)− 1. However, although both matrices, (B − Ω) and (X F X)− 1 are persymmetric, their product need not to be persymmetric. It was shown in [23, Lemma 3.1] that we may transform the matrix X into a matrix X˜in such a way that X˜FX˜=sI,s > 0, with the columns of X˜still being eigenvectors of A. Now we state the main result of this section, which was proven in [10]. We only consider the case of even p0. The odd case is similar.

Theorem 12 [10]Let Λ = {λ1λ2, …, λn} be a list of complex numbers with Λ=Λ¯,λ1 ≥ |λi|, i = 2, 3, …, n, and i=1nλi0.Suppose there exists a partition of Λ as in (9), such that the following conditions are satisfied:

i) For each k=1,2,,p02,there exists a nonnegative matrix with spectrum

Γk=ωkλk1λk2λkpk,0ωkλ1,E99

and with certain prescribed elementary divisors.

ii) There exists a persymmetric nonnegative matrix of order p0, with spectrum Λ0, diagonal entries ω1,ω2,,ωp02,ωp02,,ω2,ω1,and certain prescribed elementary divisors.

Then Λ is realizable by an n × n persymmetric nonnegative matrix with the prescribed elementary divisors.

Proof. From i), let Ak be a nonnegative matrix with spectrum Γk, and certain prescribed elementary divisors, k=1,2,,p02.We may assume that AkCSωk.Then Ak e = ωk e, with e = (1, 1, …, 1) T . The matrix

A=A1A2Ap02Ap02FA2FA1FE601

is persymmetric nonnegative with spectrum Γ=Γ1Γp02Γp02Γ1,and the prescribed elementary divisors associated to the lists Λk. Let X (or X˜) be the matrix in (11) such that XFX=sIp0,s > 0 (or X˜FX˜=sIp0,s > 0). Now, from ii) let B=Ω+CXFX=Ω+sCIp0be the p0 × p0 persymmetric nonnegative matrix with spectrum Λ0 and diagonal entries ω1,,ωp02,ωp02,,ω1.Then C=1sBΩis persymmetric nonnegative, where Ω=diagω1ωp02ωp02ω1.Thus, from Theorem 11, M = A + XCX F is persymmetric with spectrum Λ, and with the prescribed elementary divisors. Since AX, and C are nonnegative, then M is also nonnegative. ■

In [10], the authors show the following result:

Theorem 13 [10] Let

C=0100001001cn1c2c1c0E101

be the companion matrix of the polynomial px=xn+k=1nck1xnk. Then Cis similar to a persymmetric matrix P. In particular, if Cis nonnegative, Pis also nonnegative.

In [21], Laffey and Šmigoc solve the NIEP in the left half plane. That is, they give necessary and sufficient conditions for the existence of a nonnegative matrix with prescribed complex spectrum Λ = {λ1λ2, …, λn} satisfying Ri ≤ 0, i = 2, …, n. Here we show that a realizable list of complex numbers, with Ri ≤ 0, i = 2, …, n, is in particular realizable by a nonnegative persymmetric matrix.

Theorem 14 [10] Let Λ = {λ1λ2, …, λn}, with Ri ≤ 0, i = 2, …, n, be a realizable list of complex numbers. Then Λ is also realizable by a nonnegative persymmetric matrix.

Proof. If Λ is realizable, then from the result in [21], Λ is the spectrum of a matrix of the form C+αI,where Cis a nonnegative companion matrix with trC=0.Then from Theorem 13, Cis similar to a nonnegative persymmetric matrix Pwith eigenvalues λ1 − αλ2 − α, …, λn − α. Hence P+αIis nonnegative persymmetric with spectrum Λ.

To apply Theorem 12, we need to know conditions under which there exists a p0 × p0 persymmetric nonnegative matrix with spectrum Λ0 and diagonal entries ω1,ω2,,ωp02,ωp02,,ω2,ω1.Following a result due to Farahat and Ledermann [24, Theorem 2.1], we have

Theorem 15 [24] Let Λ = {λ1λ2, …, λn} be a list of complex numbers and let {a1a2, …, an} be a list of nonnegative real numbers such that i=1nai=i=1nλi.Let p(x) = (x − λ1)(x − λ2) ⋯ (x − λn) and

μ0=1,μ1=xa1,,μn=xa1xa2xan,E102

with

px=μn+k1μn1++kn1μ1+kn.E12

If k1k2, …, kn are all nonpositive, then there exists an n × n nonnegative matrix, with spectrum Λ and with diagonal entries a1a2, …, an.

Proof. The polynomials μ0μ1, …, μn constitute a basis in the space of polynomials of degree less than or equal to n. Equating the coefficients of x n − 1 in both sides in (12), we obtain k1 = 0. Let the matrix

A=a11000a21001knk3k2an.E104

Expanding the determinant of xI − A with respect to the last row it, follows that A has characteristic polynomial p(x) and therefore A has spectrum Λ. Besides, if k1, …, kn are all nonpositive, A is nonnegative.

Example 6 Let Λ = {9, − 3, − 3, − 3}. First we compute a persymmetric nonnegative matrix Pwith spectrum Λ and with elementary divisors (λ − 9), (λ + 3)3. Then p(x) = (λ − 9)(λ + 3)3 = λ4 − 54λ2 − 216λ − 243, and the corresponding matrices C(the companion of p(x)) and P(obtained from Theorem 13) are, respectively,

C=010000100001243216540P=010027010108001972108270.E105

Next, we compute a persymmetric matrix Pwith spectrum Λ and linear elementary divisors: Then we take the partition

Λ0=9,3,Λ1=Λ2=3withΓ1=Γ2=3,3.E106

We apply Theorem 12 with

A=0300300000030030,X=120120012012,B=31363,E107

to obtain the persymmetric nonnegative matrix A + XCX F with the required properties. Finally, we compute a persymmetric nonnegative matrix Pwith spectrum Λ and with elementary divisors (λ − 9), (λ + 3)2, (λ + 3). In this case, we take the partition

Λ0=9,3,3,Λ1=Λ3=,Λ2=3E108
Γ1=Γ3=0,Γ2=3,3E109
A1=A3=0,A2=0330.E110

We compute the matrix B, with spectrum Λ0 and diagonal entries 0, 3, 0 (in that order), from Theorem 15, case n = 3:

B=01045231814520withJB=900031003E111

Then,

A=0000003003000000+100012001200010104520181452010000121200001=0122122045420312245423012281454245420,JA=9000031000300003.E112

6. Some open questions

In [3, Theorem 1], Minc proved the following result:

Theorem 16 [3]Let Λ = {λ1λ2, …, λn} be a list of complex numbers, which is realizable by a diagonalizable positive matrix A. Then, for each JCF JΛ associated with Λ, there exists a positive matrix B with the same spectrum as A, and with JCF J(B) = JΛ.

According to Minc, the positivity condition is essential in his proof, and it is not known if the result holds without this condition (see [2]). Specifically, it is not known i) whether for every positive matrix, there exists a diagonalizable positive matrix with the same spectrum, ii) whether for every nonnegative diagonalizable matrix with spectrum Λ = {λ1, …, λn}, there exists a nonnegative matrix for each JCF associated with Λ. There are many examples which show that the Minc result holds for diagonalizable nonnegative matrices. For instance, all diagonalizable nonnegative matrices with spectrum Λ given in Section 2, Theorems 4 and 5, and Corollaries 1 and 2, give rise to nonnegative matrices for each one of the possible JCF associated with Λ. However, we do not know if the Minc result holds for a general diagonalizable nonnegative matrix.

The problem of finding a nonnegative matrix with prescribed spectrum and diagonal entries is a hard open problem, which, besides of being important in itself, is necessary to apply different versions of Rado's Theorem on both problems, the NIEP and the NIEDP. Necessary and sufficient conditions are only known for n ≤ 3.

© 2016 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Ricardo L. Soto (July 6th 2016). Nonnegative Inverse Elementary Divisors Problem, Applied Linear Algebra in Action, Vasilios N. Katsikis, IntechOpen, DOI: 10.5772/62234. Available from:

chapter statistics

769total 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

Some Recent Advances in Nonlinear Inverse Scattering in 2D: Theory and Numerics

By Valery Serov, Markus Harju and Georgios Fotopoulos

Related Book

First chapter

Simulation of Piecewise Hybrid Dynamical Systems in Matlab

By Fatima El Guezar and Hassane Bouzahir

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