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

## 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 Abe an n × ncomplex matrix, and let

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

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

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

are called the Jordan blocksof J(A). The elementary divisorsof Aare 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,n1 + ⋯ + nk = n, are the elementary divisors of an n × nmatrix 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 Jas its JCF. In order that the problem be meaningful, the matrix Ais required to have a particular structure. When Ais required to be an entrywise nonnegative matrix, the problem is called the nonnegative inverse elementary divisors problem(NIEDP) (see [24]). The NIEDPis 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 × nentrywise nonnegative matrix. If there exists a nonnegative matrix Awith spectrum Λ, we say that Λis realizable and that Ais the realizing matrix. The NIEDPcontains the NIEP, and both problems are equivalent if the prescribed eigenvalues are all distinct. Both problems remain unsolved (the NIEPis solved only for n ≤ 4). A number of sufficient conditions or realizability criteria for the NIEPto 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 NIEDPlooks 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 sumsif 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)Tcorresponding to the eigenvalue α. A nonnegative matrix Ais called stochastic if ACS1and it is called doubly stochastic if A,ATCS1.For lack of simplicity, we shall call nonnegative generalized stochasticto a nonnegative matrix ACSαand nonnegative generalized doubly stochasticto a nonnegative matrix Awith 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 ekthe vector with one in the k-th position and zeros elsewhere. Let Sbe a nonsingular matrix such that S− 1AS = J(A) is the JCFof A. If ACSλ1,Scan be chosen so that Se1 = eand, 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 Tis an n × nmatrix of the form

T=λ100,andS=1s12s1n1s22s2n1sn2snnE400

is nonsingular, then STS− 1e = λ1e, that is, STS1CSλ1.We shall denote by Eijthe n × nmatrix with 1 in the (ij)thposition and zeros elsewhere. The following simple perturbation allows us to join two or more Jordan blocks corresponding to a same eigenvalue λpto obtain one Jordan block of a bigger size: Let Abe an n × nmatrix 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 Ais an n × ncomplex matrix with JCF J(A) = S− 1AS, then for an appropriate set K

JA+E=S1AS+E=S1A+SES1SE700

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

A+SES1CSλ1.E800

The first works on the NIEDPare 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 1Minc[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 JCFassociated 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 NIEPand 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 × nmatrix, 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 reigenvalues of an n × nmatrix Avia a rank-rperturbation, without changing any of the remaining n − reigenvalues (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 2Brauer[13] Let A be an n × n arbitrary matrix with eigenvalues λ1, …, λn. Letv = (v1,…, vn)Tan eigenvector of A associated with the eigenvalue λkand letq = (q1,…, qn)Tbe any n-dimensional vector. Then the matrix A + vqThas eigenvalues λ1, …, λk − 1λk + vTqλk + 1, …, λn.

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

U1AU=λ1λ2λnE900

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

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

and the result follows.■

Theorem 3Rado[14] Let A be an n × n arbitrary matrix with eigenvalues λ1, …, λnand let Ω = diag{λ1, …, λr} for some r ≤ n. Let X be an n × r matrix with rank r such that its columns x1x2, …, xrsatisfy Axi = λixi, 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, …, μrare 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 JCFof the Brauer perturbation A + eqT.

Lemma 1[6] LetACSλ1be with JCF

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

LetqT = (q1, …, qn) andλ1+i=1nqiλi,i = 2, …, n. Then the JCF of A + eqTisJA+i=1nqiE11.In particular, ifi=1nqi=0,then A and A + eqTare 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 matrixACSλ1with spectrum Λ, for each possible JCF associated with Λ.

Proof. Let D = diag{λ1λ2, …, λn} and let Pbe 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 + Eis the desired JCF. Then there exists ε > 0 such that A = PDP− 1 + εPEP− 1 is nonnegative, and since D + εEand D + Eare diagonally similar (with diag{1, εε2, …, εn − 1}), Ahas JCFequal to D + E. Moreover, since Pe1 = 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 NIEPhas 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 × nnonnegative 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 matrixACSλ1with spectrum Λ if and only ifi=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 matrixACSλ1with spectrum Λ if and only ifi=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] LetA=A1abTcbe an n × n matrix and let B be an m × m matrix with JCFJB=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, with0 < 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 JCFassociated 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 entryann=i=1nλiif and only ifi=1nλi0.

Proof. It is clear that the condition is necessary. Let λ1 > 0 > λ2 ≥ ⋯ ≥ λpbe real numbers and let λp+1,λp+2=λ¯p+1,,λn1,λn=λ¯n1be complex nonreal numbers, with s1Λ=i=1nλi0.Let mbe 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 Λrhaving nr + 1 elements, where nris 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 JCFassociated with Λr. Finally, by employing the Lemma 2 (Šmigoc Lemma) mtimes, we construct a nonnegative matrix Awith spectrum Λand with arbitrarily prescribed elementary divisors. ■

Example 1Let

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

be given. We want to construct a12 × 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 entrya440=20.Λ1 and Λ2 are also realizable by nonnegative matrices A1, with elementary divisors(λ − 20), (λ2 + 4λ + 13)2, and entrya551=12,and A2, with linear elementary divisors(λ − 12), (λ + 3 ± 5i), (λ + 3 ± 5i), and entrya552=0,respectively (see Corollary 3). By applying Lemma 2 to the matrices A0 and A1 we obtain an8 × 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 Awith spectrum Λ = {λ1, …, λn}, where λiG,i = 2, …, n, for each JCFassociated 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 2Let Λ = {λ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 thatBCSλ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 + eqT, where λ1 ≥ 10 + 3 = 13. Moreover, from Lemma 1, A has the prescribed elementary divisors. Observe that the values3 and10 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 + eqT, 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 blocksJniλi, of size ni ≥ 2, are associated to a real eigenvalue λi < 0; or when there is at least one Jordan blockJniλi, of size ni ≥ 2, associated to a real eigenvalue λi ≥ 0 withM=Reλi0+Imλi0,for some i0 ≤ n − 1.

or if

ii)λ1>M+m,E6

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

then there exists an n × n nonnegative matrixACSλ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 = Ω + CXis an r × rmatrix 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 = Ω + CXand VAYhave no common eigenvalues, A + XCis similar to B ⊕ VAY. Then we have:

Lemma 4Let 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 satisfying0 ≤ ωk ≤ λ1, k = 1, …, p0. Suppose that

i) For each k = 1, …, p0, there exists a listΓk=ωkλk1λkpkwith ωk ≥ Mk + mkor ω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 matrixMCSλ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 Γkand let Ek = ∑Ei,i + 1 such that Dk + εEkis 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 + XCis nonnegative with spectrum Λand from Lemma 4, Mhas the prescribed elementary divisors.■

Example 3Let Λ = {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 entries4, 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, …, λpare real and λp + 1, …, λnare 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 λkbeing 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 λibe real, i = 2, …, p, and let xj = Reλjand 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 Ainto 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 + erTis 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 kthcolumn of Ahas εabove Imλkor above a real λk, and

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

otherwise. Let B = A' + eqT. Again by Lemma 1, Bhas 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 ttimes 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 Bare 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 qkwere defined, each the columns 2, …, nhave column sum λ1. The first column sum is also λ1.■

Example 4Let Λ = {λ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 the7 × 7 initial matrixACSλ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 matrixA'=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' + eqTis 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, withAk,AkTCSωk,and with prescribed elementary divisors

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

ii) There exists a p0 × p0 nonnegative (positive) matrixB=biji,j=1nsuch thatB,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 thatA,ATCSλ1,with spectrum Λ and with the prescribed elementary divisors associated to the lists Λk.

Example 5Let Λ = {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 NIEDPfor 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 AT, denotes the transpose of A, the superscript F, in AF, denotes the flip-transpose of A, which flips Aacross its skew-diagonal. If A = (aij) mn, then AF = (an − j + 1,m − i + 1) nm. A matrix Ais said to be persymmetricif AF = A, that is, if it is symmetric across its lower-left to upper-right diagonal. Let Jbe the n × nmatrix with ones along its skew-diagonal and zeroes elsewhere, that is, J = [en|en − 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 10If A and B are persymmetric matrices, then i) aA + bB, with ab ∈ ℝ, ii) A− 1, if A− 1 exists, and iii) AT, are also persymmetric.

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

ii) I = A− 1 Aimplies AF(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, …, xr} be a set of eigenvectors of A corresponding to λ1, …, λr, respectively. Let X be the n × r matrix with i − th columnxiand rank(X) = r. Let Ω = diag{λ1, …, λr}, and let C be an r × r persymmetric matrix. Then, the matrix A + XCXFis persymmetric with eigenvalues μ1μ2, …, μrλr + 1, …, λn, where μ1μ2, …, μrare eigenvalues of B = Ω + CXFX.

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 Λkcan 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, Akcan be chosen as AkCSωk.

Let the n × p0 matrix

X=x1xp02yp02y1,forevenp0.E11

where, xk = e = [1, 1, …, 1] Tand yk=yk1ykpk+1T0are, respectively, the Perron eigenvectors of Akand AkF,k=1,2,,p02.It was shown in [23] that in the case of even p0, XFXis 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 = Ω + CXFXis 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 XFXis nonsingular, we may compute C = (B − Ω)(XFX)− 1. However, although both matrices, (B − Ω) and (XFX)− 1 are persymmetric, their product need not to be persymmetric. It was shown in [23, Lemma 3.1] that we may transform the matrix Xinto 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, andi=1nλi0.Suppose there exists a partition of Λ as in (9), such that the following conditions are satisfied:

i) For eachk=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 Akbe a nonnegative matrix with spectrum Γk, and certain prescribed elementary divisors, k=1,2,,p02.We may assume that AkCSωk.Then Ake = ωke, 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 + XCXFis persymmetric with spectrum Λ, and with the prescribed elementary divisors. Since AX, and Care nonnegative, then Mis also nonnegative. ■

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

Theorem 13[10] Let

C=0100001001cn1c2c1c0E101

be the companion matrix of the polynomialpx=xn+k=1nck1xnk. ThenCis similar to a persymmetric matrixP. In particular, ifCis 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}, withRi ≤ 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 thati=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, …, knare all nonpositive, then there exists an n × n nonnegative matrix, with spectrum Λ and with diagonal entries a1a2, …, an.

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

A=a11000a21001knk3k2an.E104

Expanding the determinant of xI − Awith respect to the last row it, follows that Ahas characteristic polynomial p(x) and therefore Ahas spectrum Λ. Besides, if k1, …, knare all nonpositive, Ais nonnegative.

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

C=010000100001243216540P=010027010108001972108270.E105

Next, we compute a persymmetric matrixPwith 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 + XCXFwith the required properties. Finally, we compute a persymmetric nonnegative matrixPwith 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 entries0, 3, 0 (in that order), from Theorem15, 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 JCFassociated 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 JCFassociated 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 NIEPand the NIEDP. Necessary and sufficient conditions are only known for n ≤ 3.

chapter PDF
Citations in RIS format
Citations in bibtex format

## More

© 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

### 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:

### Related Content

#### Applied Linear Algebra in Action

Edited by Vasilios Katsikis

Next chapter

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

By Valery Serov, Markus Harju and Georgios Fotopoulos

First chapter

#### PID Control Design

By A.B. Campo

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.