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

be its *Jordan canonical form* (hereafter, *JCF*). The *n*_{i} × *n*_{i} submatrices

are called the *Jordan blocks* of *J*(*A*). The *elementary divisors* of *A* are the polynomials *i* = 1, …, *k*. The inverse elementary divisors problem (*IEDP*) is the problem of determining necessary and sufficient conditions under which the polynomials *n* _{1} + ⋯ + *n*_{k} = *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 *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 **e** = (1, 1, …1)^{T} corresponding to the eigenvalue *α*. A nonnegative matrix *A* is called stochastic if *nonnegative generalized stochastic* to a nonnegative matrix *nonnegative generalized doubly stochastic* to a nonnegative matrix *A* with *Λ* = {*λ*_{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 **e**_{k} the vector with one in the *k*-th position and zeros elsewhere. Let *S* be a nonsingular matrix such that *S*^{− 1}*AS* = *J*(*A*) is the *JCF* of *A*. If *S* can be chosen so that *S***e**_{1} = **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*^{− 1}**e** = *λ*_{1}**e**, that is, *E*_{ij} 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 *λ*_{p}. Let *p* ≤ *k*, with *ξ* = 0 if *p* = 1, and let *J*(*A*) + *E*, with

we obtain a Jordan block of bigger size *J*_{γ}(*λ*_{p}), corresponding to the elementary divisor (*λ* − *λ*_{p})^{γ}, *γ* = *m*_{1} + *m*_{2} + … + *m*_{q}.

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

is the *JCF* of *A* + *SES*^{− 1}. If *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** = (*v*_{1},…, *v*_{n})^{T} *an eigenvector of A associated with the eigenvalue λ*_{k} *and let***q** = (*q*_{1},…, *q*_{n})^{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 x*_{1}, *x*_{2}, …, *x*_{r} *satisfy Ax*_{i} = *λ*_{i} *x*_{i}, *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 *UX* = *I*_{r}, *VY* = *I*_{n − r}, and *VX* = 0, *UY* = 0. Let *C* = [*C*_{1}|*C*_{2}], *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* *be with JCF*

*Let* **q**^{ T } = (*q*_{1}, …, *q*_{n}) *and* *i* = 2, …, *n*. *Then the JCF of A* + **eq**^{ T }*is* *In particular, if* *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

has the property that *Λ*. 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* *with spectrum Λ*, *for each possible JCF associated with Λ*.

**Proof**. Let *D* = *diag*{*λ*_{1}, *λ*_{2}, …, *λ*_{n}} and let *P* be the matrix in (2). Then *Λ* 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* **e**_{1} = **e**, the rows of *P*^{− 1} satisfy (1) and *PEP*^{− 1} **e** = 0. Thus

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

Let *Λ* = {*λ*_{1}, …, *λ*_{n}} be a list of complex numbers with *λ*_{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 *n*_{i} ≥ 2, are associated to a real eigenvalue *λ*_{i} < 0; or when there is at least one Jordan block *n*_{i} ≥ 2, associated to a real eigenvalue *λ*_{i} ≥ 0 with *i*_{0}, then there exists an *n* × *n* nonnegative matrix *Λ* 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* *with spectrum Λ if and only if*

**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,

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

**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* *with spectrum Λ if and only if*

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* = 2, …, *n*, then there exists a nonnegative matrix with spectrum *Λ* if and only if *Λ* = {*λ*_{1}, …, *λ*_{n}}, with *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* *be an n* × *n matrix and let B be an m* × *m matrix with JCF* *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* = (*a*_{ij}), *with spectrum Λ and entry a*_{nn} = *s*_{1}(*Λ*).

**Corollary 3** [12] *Let Λ* = {*λ*_{1}, *a* ± *bi*, …, *a* ± *bi*} *be a list of n complex numbers, with* 0 < *Then, for each JCF associated with Λ*, *there exists a nonnegative matrix A* = (*a*_{ij}) *with spectrum Λ and entry a*_{nn} = *s*_{1}(*Λ*), *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 <

Hence, from Lemma 3, *Λ* is the spectrum of a nonnegative matrix *A* = (*a*_{ij}) with entry *a*_{nn} = *s*_{1}(*Λ*), 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* = 2, …, *n*. *Then, for each JCF associated with Λ*, *there exists a nonnegative matrix A with spectrum Λ and entry* *if and only if*

**Proof**. It is clear that the condition is necessary. Let *λ*_{1} > 0 > *λ*_{2} ≥ ⋯ ≥ *λ*_{p} be real numbers and let *m* be the number of distinct pairs of complex conjugate. Consider the partition

with *Λ*_{r} having *n*_{r} + 1 elements, where *n*_{r} is the number of elements of *Λ*_{r} − {*s*_{1}(*Λ*_{r − 1})}, in such a way that *Λ*_{0} satisfies Corollary 2, and then, we can compute a matrix *Λ*_{0}, the entry *r* = 1, …, *m*, there exists, from Corollary 3, a nonnegative matrix *n*_{r} + 1, with spectrum *Λ*_{r}, entry *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 A*_{0}, *with elementary divisors* (*λ* − 23), (*λ* + 1)^{2}, (*λ* + 1), *and entry* *Λ*_{1} *and Λ*_{2} *are also realizable by nonnegative matrices A*_{1}, *with elementary divisors* (*λ* − 20), (*λ*^{2} + 4*λ* + 13)^{2}, *and entry* *and A*_{2}, *with linear elementary divisors* (*λ* − 12), (*λ* + 3 ± 5*i*), (*λ* + 3 ± 5*i*), *and entry* *respectively (see Corollary 3). By applying Lemma 2 to the matrices A*_{0} *and A*_{1} *we obtain an* 8 × 8 *nonnegative matrix B*_{1} = (*b*_{ij}) *with spectrum Λ*_{0} ∪ *Λ*_{1} − {20}, *elementary divisors*

*and entry b*_{88} = 12. *Next, we employ Lemma 2 again with the matrices B*_{1} *and A*_{2}, *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* = 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.

## 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 ± 3*i*, − 1 ± 3*i*}.

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

*We consider the initial matrix*

*Let S* = [**e**|**e**_{2}| ⋯ |**e**_{9}] *and E* = *E*_{4,5} + *E*_{7,8}. *Then*

*It is clear that* *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* = *E*_{2,3} + *E*_{4,5} + *E*_{7,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* *and λ*_{1} ≥ |*λ*_{i}|, *i* = 2, …, *n*. *Let*

*if*

*when all possible Jordan blocks* *, of size n*_{i} ≥ 2, *are associated to a real eigenvalue λ*_{i} < 0; *or when there is at least one Jordan block* *, of size n*_{i} ≥ 2, *associated to a real eigenvalue λ*_{i} ≥ 0 *with* *for some i*_{0} ≤ *n* − 1.

*or if*

*when at least one Jordan block* *, of size n*_{i} ≥ 2, *is associated to a real eigenvalue λ*_{i} ≥ 0 *with M* = *λ*_{k} ≥ 0,

*then there exists an n* × *n nonnegative matrix* *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*; *Let* *be a pairwise disjoint partition, with* *λ*_{11} = *λ*_{1}, *k* = 1, …, *p*_{0}, *where Λ*_{0} *is realizable, p*_{0} *is the number of elements of the list Λ*_{0} *and some lists Λ*_{k}, *k* = 1, …, *p*_{0}, *can be empty. Let* *be real numbers satisfying* 0 ≤ *ω*_{k} ≤ *λ*_{1}, *k* = 1, …, *p*_{0}. *Suppose that*

*i*) *For each k* = 1, …, *p*_{0}, *there exists a list* *with ω*_{k} ≥ *M*_{k} + *m*_{k} *or ω*_{k} > *M*_{k} + *m*_{k}, *as in Theorem 6, where*

*and*

*ii*) *there exists a p*_{0} × *p*_{0} *nonnegative matrix B with spectrum Λ*_{0} *and diagonal entries*

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

**Proof**. Let

with spectrum *Γ*_{k} and let *E*_{k} = ∑*E*_{i,i + 1} such that *D*_{k} + *εE*_{k} is the prescribed *JCF*. Let *k* = 1, …, *p*_{0}, and

From *i*), there exists an appropriate vector *k* = 1, …, *p*_{0}. From Lemma 1, *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 + 3*i*, − 1 − 3*i*}. *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.*

## 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* *λ*_{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 m*_{k} = − min{0, R*eλ*_{k}, I*mλ*_{k}}, *k* = 2, …, *n*. *If each of the following statements hold:*

*ii*) *λ*_{1} > *Reλ*_{k} + *Imλ*_{k} + *n*(*m*_{k}), *k* = 2, …, *n*,

*where ε* < 0, *with*

*for real λ*_{k} ≠ 0, *k* = 2, …, *p*, *or*

*if λ*_{k} = 0, *with λ*_{k} *being the zero of an elementary divisor* *n*_{k} ≥ 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 *x*_{j} = *Reλ*_{j} and *y*_{j} = *Imλ*_{j}, *j* = *p* + 1, …, *n* − 1. Consider the initial matrix

which has the desired *JCF*. First, from Theorem 2, we can transform *A* into a nonnegative matrix

Then from condition *i*), the matrix *A*^{'} = *A* + **er**^{ T }is nonnegative, *A*. We now describe how to perturb *A*^{'} to make it nonnegative generalized doubly stochastic. Define

with

if the *k*^{th} 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 *λ*_{1}, and from the way in which the *q*_{k} 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* *and the desired JCF*:

*We apply Theorem 2 to transform A into a nonnegative matrix* *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* *λ*_{1} > |*λ*_{i}|, *i* = 2, …, *n*. *Suppose there exists a partition* *with*

*where the lists Λ*_{k}, *k* = 1, …, *p*_{0}, *have cardinality p*, *in such a way that:*

*i*) *For each k* = 1, …, *p*_{0}, *there exists a list*

*which is realizable by a nonnegative (positive) matrix A*_{k}, *with* *and with prescribed elementary divisors*

*ii*) *There exists a p*_{0} × *p*_{0} *nonnegative (positive) matrix* *such that* *with spectrum Λ*_{0} *and diagonal entries* *and with certain of the prescribed elementary divisors.*

*Then there exists a nonnegative (positive) matrix A*, *such that* *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.

## 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* = (*a*_{ij})_{ mn}, then *A*^{ F } = (*a*_{n − 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}| ⋯ |**e**_{1}]. 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*)(*A*^{T})^{F}=(*A*^{F})^{T}=*A*^{T}.

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* {**x**_{1}, **x**_{2}, …, **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 (*p*_{k} + 1) × (*p*_{k} + 1) nonnegative matrix *A*_{k}. In particular, *A*_{k} can be chosen as

Let the *n* × *p*_{0} matrix

where, **x**_{ k} = **e** = [1, 1, …, 1]^{ T }and *A*_{k} and *p*_{0}, *X*^{ F }*X* is diagonal persymmetric nonnegative matrix with positive main diagonal. To apply Theorem 11, we need to find a *p*_{0} × *p*_{0} persymmetric nonnegative matrix *C*, where *B* = *Ω* + *CX*^{ F }*X* is persymmetric nonnegative with eigenvalues *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 *s* > 0, with the columns of *A*. Now we state the main result of this section, which was proven in [10]. We only consider the case of even *p*_{0}. 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* *Suppose there exists a partition of Λ as in (9), such that the following conditions are satisfied:*

*i*) *For each* *there exists a nonnegative matrix with spectrum*

*and with certain prescribed elementary divisors.*

*ii*) *There exists a persymmetric nonnegative matrix of order p*_{0}, *with spectrum Λ*_{0}, *diagonal entries* *and certain prescribed elementary divisors.*

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

**Proof**. From *i*), let *A*_{k} be a nonnegative matrix with spectrum *Γ*_{k}, and certain prescribed elementary divisors, *A*_{k} **e** = *ω*_{k} **e**, with **e** = (1, 1, …, 1)^{ T }. The matrix

is persymmetric nonnegative with spectrum *Λ*_{k}. Let *X* (or *s* > 0 (or *s* > 0). Now, from *ii*) let *p*_{0} × *p*_{0} persymmetric nonnegative matrix with spectrum *Λ*_{0} and diagonal entries *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* *. Then* *is similar to a persymmetric matrix* *. In particular, if* *is nonnegative,* *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 R*eλ*_{i} ≤ 0, *i* = 2, …, *n*. Here we show that a realizable list of complex numbers, with R*eλ*_{i} ≤ 0, *i* = 2, …, *n*, is in particular realizable by a nonnegative persymmetric matrix.

**Theorem 14** [10] *Let Λ* = {*λ*_{1}, *λ*_{2}, …, *λ*_{n}}, *with* R*eλ*_{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 *λ*_{1} − *α*, *λ*_{2} − *α*, …, *λ*_{n} − *α*. Hence *Λ*.

To apply Theorem 12, we need to know conditions under which there exists a *p*_{0} × *p*_{0} persymmetric nonnegative matrix with spectrum *Λ*_{0} and diagonal entries

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

with

*If k*_{1}, *k*_{2}, …, *k*_{n} *are all nonpositive, then there exists an n* × *n nonnegative matrix, with spectrum Λ and with diagonal entries a*_{1}, *a*_{2}, …, *a*_{n}.

**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 *k*_{1} = 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 *k*_{1}, …, *k*_{n} are all nonpositive, *A* is nonnegative.

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

*Next, we compute a persymmetric matrix* *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* *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,*

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