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
be its Jordan canonical form (hereafter, JCF). The ni × ni submatrices
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 [2–4]). 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, 6–12]) 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=1n is said to have constant row sums if all its rows sum up to the same constant, say α, i.e.
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 A∈CS1 and it is called doubly stochastic if A,AT∈CS1. For lack of simplicity, we shall call nonnegative generalized stochastic to a nonnegative matrix A∈CSα and nonnegative generalized doubly stochastic to a nonnegative matrix A with A,AT∈CSα. 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 A∈CSλ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:
If T is an n × n matrix of the form
is nonsingular, then STS− 1e = λ1e, that is, STS−1∈CSλ1. We shall denote by Eij the n × n matrix with 1 in the (i, j)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λp be corresponding to the eigenvalue λp. Let ξ=∑j=1p−1mj, 1 ≤ p ≤ k, with ξ = 0 if p = 1, and let E=∑i∈KEi,i+1. Then by using the perturbation J(A) + E, with
we obtain a Jordan block of bigger size Jγ(λp), corresponding to the elementary divisor (λ − λp)γ, γ = m1 + m2 + … + mq.
Observe that if E=∑i∈KEi,i+1 with 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
is the JCF of A + SES− 1. If A∈CSλ1 and S = [e| ∗ | ⋯ |∗], then
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
is an upper triangular matrix, with v being the first column of U. Then,
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 x1, x2, …, 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 S−1=VU. Then UX = Ir, VY = In − r, and VX = 0, UY = 0. Let C = [C1|C2], X=X2X1, Y=Y2Y1. Then, since AX = XΩ,
and
Thus,
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 A∈CSλ1 be with JCF
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.
Advertisement
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
has the property that PDP−1∈CSλ1 is 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 A∈CSλ1 with spectrum Λ, for each possible JCF associated with Λ.
Proof. Let D = diag{λ1, λ2, …, λn} and let P be the matrix in (2). Then PDP−1∈CSλ1 is positive (generalized stochastic) with spectrum Λ and linear elementary divisors. Let
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 A∈CSλ1 has 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
which are called lists of complex Suleimanova type. In both cases, the NIEP has a solution if and only if ∑i=1nλi≥0 (see [18, 19]).
Let Λ = {λ1, …, λn} be a list of complex numbers with Λ¯=Λ, ∑i=1nλi≥0, and λ1 ≥ |λi|, i = 2, …, n. In [9, Theorem 2.1], the authors define
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 A∈CSλ1 with 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 A∈CSλ1 with spectrum Λ if and only if ∑i=1nλi≥0.
Proof. The condition is necessary for the existence of a nonnegative matrix with spectrum Λ. The condition is also sufficient. In fact, since
then if λ1 + λ2 + ⋯ + λn ≥ 0, λ1≥−∑k=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λi≥0. 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 A∈CSλ1 with spectrum Λ if and only if ∑i=1nλi≥0.
In [20], Šmigoc extends the result in [19, Theorem 3.3], to the region
that is, she shows that if Λ = {λ1, …, λn} is a list of complex numbers with λi∈G, i = 2, …, n, then there exists a nonnegative matrix with spectrum Λ if and only if ∑i=1nλi≥0. The following result extends Corollary 1 to lists of complex numbers Λ = {λ1, …, λn}, with λi∈G, 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=A1abTc be an n × n matrix and let B be an m × m matrix with JCF JB=c00IB. Then the matrix
has JCF
Lemma 3 [12] Let Λ = {λ1, a ± bi, …, a ± bi} be a list of n complex numbers, with n ≥ 3, a < 0, b > 0. If
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 Λ = {λ1, a ± bi, …, a ± bi} be a list of n complex numbers, with 0 < b≤−3a. 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 < b≤−3a, it follows that
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 λi∈G, i = 2, …, n. Then, for each JCF associated with Λ, there exists a nonnegative matrix A with spectrum Λ and entry ann=∑i=1nλi if and only if ∑i=1nλi≥0.
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,…,λn−1,λn=λ¯n−1 be complex nonreal numbers, with s1Λ=∑i=1nλi≥0. Let m be the number of distinct pairs of complex conjugate. Consider the partition
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=n−p. The list Λ0 satisfies Corollary 2, and then, we can compute a matrix A0=aij0 with spectrum Λ0, the entry app0=s1Λ0 and with arbitrarily prescribed elementary divisors. Moreover, since 0<Imλp+r≤−3Reλp+r, r = 1, …, m, there exists, from Corollary 3, a nonnegative matrix Ar=aijr of 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
be given. We want to construct a 12 × 12 nonnegative matrix with elementary divisors
Consider the lists
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
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 λi∈G, 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
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.
Advertisement
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
We consider the initial matrix
Let S = [e|e2| ⋯ |e9] and E = E4,5 + E7,8. Then
It is clear that B∈CSλ1 has the desired JCF. Now, in order that B becomes nonnegative, we take
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
In this case, M = 3 and m = 10.
Case ii): Now, suppose we want to construct a nonnegative matrix A with elementary divisors
In this case, we take E = E2,3 + E4,5 + E7,8, and
By choosing
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λi≥0, and λ1 ≥ |λi|, i = 2, …, n. Let
if
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
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 A∈CSλ1 with spectrum Λ and with prescribed elementary divisors
Let A, X, C, and Ω be as in Theorem 3, with
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 A, X, Y, V, C, and Ω be as above. If the matrices B = Ω + CX and VAY have no common eigenvalues, then
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λi≥0. Let Λ=Λ0∪Λ1∪⋯∪Λp0 be 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,…,ωp0 be real numbers satisfying 0 ≤ ωk ≤ λ1, k = 1, …, p0. Suppose that
i) For each k = 1, …, p0, there exists a list Γk=ωkλk1…λkpk with ωk ≥ Mk + mk or ωk > Mk + mk, as in Theorem 6, where
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 M∈CSλ1 with spectrum Λ and with prescribed elementary divisors.
Proof. Let
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+εEkSk−1∈CSωk, k = 1, …, p0, and
From i), there exists an appropriate vector qkT=qk0qkp1…qkpk, with ∑j=0pkqkj=0, such that Ak+eqkT is nonnegative for each k = 1, …, p0. From Lemma 1, Ak+eqkT has 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
Consider the partition Λ = Λ0 ∪ Λ1 ∪ Λ2 ∪ Λ3 with
The matrix
has the spectrum Λ0 with diagonal entries 4, 1, 0. Then, from Theorem 7, we have
with the prescribed spectrum and elementary divisors.
Advertisement
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
the prescribed elementary divisors (prescribed JCF). Let M be as defined in (
4) and let mk = − min{0, Reλk, Imλk}, 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
for real λk ≠ 0, k = 2, …, p, or
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 (i, i + 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 A∈CSλ1,
which has the desired JCF. First, from Theorem 2, we can transform A into a nonnegative matrix A'∈CSλ1. Let
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
with
if the kth column of A has ε above Imλk or above a real λk, and
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 (i, i + 1), that
In position (k, 1), k = 2, …, n, we have from condition iii) that
Thus, all entries in B are nonnegative. Now we show that B,BT∈CSλ1: It is clear that B∈CSλ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 A∈CSλ1,
and the desired JCF:
We apply Theorem 2 to transform A into a nonnegative matrix A'=A+erT∈CSλ1, where for ε = − 1,
Then we obtain
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
Then B = A' + eq
T
is nonnegative generalized doubly stochastic, with same elementary divisors as A, provided that
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∪⋯∪Λp0 with
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
which is realizable by a nonnegative (positive) matrix Ak, with Ak,AkT∈CSωk, and with prescribed elementary divisors
ii) There exists a p0 × p0 nonnegative (positive) matrix B=biji,j=1n such that B,BT∈CSλ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,AT∈CSλ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
we take the partition
and we compute the positive generalized doubly stochastic matrices
with spectra Γ1, Γ2, Γ3, and elementary divisors (λ − 7), (λ − 2)2; (λ − 6), λ2 + 4λ + 5; and (λ − 4), (λ + 1)2, respectively. Moreover, we compute
Finally
is positive generalized doubly stochastic matrix with the prescribed elementary divisors.
Advertisement
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
and the following properties are straightforward:
Proposition 10 If A and B are persymmetric matrices, then i) aA + bB, with a, b ∈ ℝ, 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 {x1, x2, …, 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
where some of the lists Λk can be empty. For each list Λk, we associate the list
which is realizable by a (pk + 1) × (pk + 1) nonnegative matrix Ak. In particular, Ak can be chosen as Ak∈CSωk.
Let the n × p0 matrix
where, x
k = e = [1, 1, …, 1]
T
and yk=yk1…ykpk+1T≥0 are, 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λi≥0. 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
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 Ak∈CSωk. Then Ak
e = ωk
e, with e = (1, 1, …, 1)
T
. The matrix
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=Ω+sCIp0 be 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 A, X, and C are nonnegative, then M is also nonnegative. ■
In [10], the authors show the following result:
Theorem 13 [10] Let
be the companion matrix of the polynomial px=xn+∑k=1nck−1xn−k
. Then C is similar to a persymmetric matrix P
. In particular, if C is nonnegative, P is 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 Reλi ≤ 0, i = 2, …, n. Here we show that a realizable list of complex numbers, with Reλi ≤ 0, i = 2, …, n, is in particular realizable by a nonnegative persymmetric matrix.
Theorem 14 [10] Let Λ = {λ1, λ2, …, λn}, with Reλi ≤ 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 C is a nonnegative companion matrix with trC=0. Then from Theorem 13, C is similar to a nonnegative persymmetric matrix P with eigenvalues λ1 − α, λ2 − α, …, λn − α. Hence P+αI is 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 {a1, a2, …, 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
with
If k1, k2, …, kn are all nonpositive, then there exists an n × n nonnegative matrix, with spectrum Λ and with diagonal entries a1, a2, …, 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
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 P with 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,
Next, we compute a persymmetric matrix P with spectrum Λ and linear elementary divisors: Then we take the partition
We apply Theorem 12 with
to obtain the persymmetric nonnegative matrix A + XCX
F
with the required properties. Finally, we compute a persymmetric nonnegative matrix P with spectrum Λ and with elementary divisors (λ − 9), (λ + 3)2, (λ + 3). In this case, we take the partition
We compute the matrix B, with spectrum Λ0 and diagonal entries 0, 3, 0 (in that order), from Theorem 15, case n = 3:
Then,
Advertisement
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.