On the Universal Realizability Problem: New Results

Abstract

Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of complex numbers. Λ is said to be realizable if there is a nonnegative matrix with spectrum Λ. The list Λ is said to be universally realizable $\left(\mathcal{UR}\right)$ if it is realizable for each possible Jordan canonical form $\left(\mathit{JCF}\right)$ allowed by Λ. The problem of determining the universal realizability of Λ is called universal realizability problem $\left(\mathit{URP}\right)$. The first results concerning $\mathit{URP}$ (formerly called nonnegative inverse elementary divisors problem) are due to H. Minc and they establish that if Λ is the spectrum of a diagonalizable positive matrix, then Λ is $\mathcal{UR}$. In this chapter, we introduce new results that contain extensions of Minc’s results and that allow us to show the universal realizability of lists of complex numbers not positively realizable. We also prove new universal realizability criteria and structured universal realizability criteria.

1. Introduction

A list $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ of complex numbers (with repeats allowed) is said to be realizable if there is an n×n nonnegative matrix A whose spectrum is Λ. In this case, A is said to be a realizing matrix. It is well known that if A is a nonnegative matrix, then the spectral radius of A, $\rho \left(A\right)=max\{\left|{\lambda }_i\right|,$ ${\lambda }_i$ eigenvalue of A}, is an eigenvalue of A called its Perron eigenvalue. Throughout this chapter, if $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ is realizable, ${\lambda }_1$ will be the Perron eigenvalue of the corresponding realizing matrix. The problem of determining the realizability of Λ is called Nonnegative Inverse Eigenvalue Problem (NIEP, see Ref. [1]). If the realizing matrix A is diagonalizable, we say that Λ is diagonalizably realizable (DR). A list $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ is universally realizable $\left(\mathcal{UR}\right)$ if it is realizable for every possible Jordan canonical form (JCF) allowed by Λ. The problem of determining the universal realizability of a list Λ of complex numbers is called universal realizability problem (URP) (formerly called Nonnegative Inverse Elementary Divisors Problem (NIEDP, see Ref. [2])). Both problems, the NIEP and the URP, have been completely solved only for lists of $n\le 4$ complex numbers, which show the difficulty of both problems.

A matrix $A=\left[a_{\mathit{ij}}\right]$ of order n is said to have constant row sums if all its rows sum up to the same constant α. We denote by ${\mathcal{CS}}_{\alpha }$ the set of all n×n real matrices with constant row sums equal to $\alpha \in \mathrm{ℝ}$. It is clear that any matrix in ${\mathcal{CS}}_{\alpha }$ has an eigenvector $\mathbf{e}={\left[1,\dots ,1\right]}^T$ corresponding to the eigenvalue α. The relevance of the real matrices with constant row sums is due to the well-known fact that the problem of finding a nonnegative matrix with spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$, ${\lambda }_1$ being the Perron eigenvalue, is equivalent to the problem of finding a nonnegative matrix in ${\mathcal{CS}}_{{\lambda }_1}$ with spectrum Λ (see Ref. [3]). We define the kth moment of the list Λ to be $s_k\left(\mathrm{\Lambda }\right)≔{\sum }_{j=1}^n{\lambda }_j^k$, $k=1,2,\dots$. It is clear that if Λ is the spectrum of a nonnegative matrix A, then $s_k\left(\mathrm{\Lambda }\right)=\mathit{\text{trace}}\left(A^k\right)\ge 0$, for $k=1,2,\dots$. Moreover, we denote by ${\mathbf{e}}_k$ the vector with one in the kth position and zeros elsewhere. Finally, we denote by $E_{i,j}$ the matrix with 1 in position (i, j) and zero elsewhere, and we define the matrix $E={\sum }_{i\in K}{E}_{i,i+1},\subset \left\{2,\dots ,n-1\right\}$.

The URP includes the NIEP and both problems are equivalent if the elements of $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ are distinct. Since 1949, many works on the NIEP have been published. In contrast, few works are known about URP. As far as we know, the first results concerning URP (formerly NIEDP) are due to H. Minc. In Refs. [4, 5], Minc studied the problem for nonnegative and doubly stochastic matrices. In particular, he proved the following theorem, which we write in terms of the URP as:

Theorem 1.1 Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of complex numbers. If Λ is diagonalizably positively realizable, then Λ is universally realizable.

It is clear that the diagonalizability condition is necessary, while the positivity condition is essential for the proof of Minc’s result. Minc set the question whether his result holds for nonnegative realizations. This question was open for almost 40 years. Recently, two extensions of Minc’s result have been obtained, which we will discuss in Section 2.

In what follows we will use the following results, some of which have been employed with success to obtain sufficient conditions for the NIEP and the URP to have a solution. The first two are perturbation results: the first one, due to Brauer [6], shows how to change one single eigenvalue of an n×n matrix without changing any of the remaining n−1 eigenvalues. The second result, due to R. Rado and published by Perfect in Ref. [7], is a generalization of Brauer’s result. It shows how to change r eigenvalues of an n×n matrix without changing any of the remaining n−r eigenvalues. The third result, by Soto and Ccapa [8], shows how is the JCF of the Brauer perturbation $A+{\mathbf{vq}}^T$. Next two results are a symmetric version of Rado’s result [9] and a result, due to Laffey and Šmigoc [10], that solves the NIEP for left half-plane lists of complex numbers, that is, lists $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ with ${\lambda }_1>0,$ $Re{\lambda }_i\le 0,$ $i=2,\dots ,n$.

Theorem 1.2 [6] Let A be an n×n matrix with eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$. Let $\mathbf{v}={\left[v_1,\dots ,v_n\right]}^T$ be an eigenvector of A associated with the eigenvalue ${\lambda }_k$ and let q be any n-dimensional vector. Then $A+{\mathbf{vq}}^T$ has eigenvalues ${\lambda }_1,\dots ,{\lambda }_{k-1},{\lambda }_k+{\mathbf{v}}^T\mathbf{q},{\lambda }_{k+1},\dots ,{\lambda }_n$.

Theorem 1.3 [7] Let A be an n×n matrix with eigenvalues ${\lambda }_1,\dots ,{\lambda }_n.$ Let $X=\left[{\mathbf{x}}_1|\cdots |{\mathbf{x}}_r\right]$ be such that $\mathit{rank}\left(X\right)=r$ and $A{\mathbf{x}}_i={\lambda }_i{\mathbf{x}}_i,$ $i=1,\dots ,r,$ $r\le n.$ Let C be an r×n matrix. Then $A+\mathit{XC}$ has eigenvalues ${\mu }_1,\dots ,{\mu }_r,{\lambda }_{r+1},\dots ,{\lambda }_n,$ where ${\mu }_1,\dots ,{\mu }_r$ are eigenvalues of the matrix $\mathrm{\Omega }+\mathit{CX}$ with $\mathrm{\Omega }=\mathit{diag}\left\{{\lambda }_1,\dots ,{\lambda }_r\right\}$.

Theorem 1.4 [8] Let $\mathbf{q}={\left[q_1,\dots ,q_n\right]}^T$ be an arbitrary n-dimensional vector and let $E_{\mathit{ij}}$ be an n×n matrix with 1 in position $\left(i,j\right)$ and zeros elsewhere. Let $A\in {\mathcal{CS}}_{{\lambda }_1}$ with JCF $J\left(A\right)=S^{-1}\mathit{AS}=\mathit{diag}\left(J_1\left({\lambda }_1\right),J_{n_2}\left({\lambda }_2\right),\dots ,J_{n_k}\left({\lambda }_k\right)\right).$ If ${\lambda }_1+{\sum }_{i=1}^n{q}_i\ne {\lambda }_i,$ $i=2,\dots ,n$, then $A+{\mathbf{eq}}^T$ has Jordan canonical form $J\left(A+{\mathbf{eq}}^T\right)=J\left(A\right)+\left({\sum }_{i=1}^n{q}_i\right)E_{11}$. In particular, if ${\sum }_{i=1}^n{q}_i=0,$ then A and $A+{\mathbf{eq}}^T$ are similar.

Theorem 1.5 [9] Let A be an n×n symmetric matrix with eigenvalues ${\lambda }_1,\dots ,{\lambda }_n.$ Let $\left\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_r\right\}$ be an orthonormal set of eigenvectors of A such that $\mathit{AX}=X\mathrm{\Omega },$ where $X=\left[{\mathbf{x}}_1|\cdots |{\mathbf{x}}_r\right]$ and $\mathrm{\Omega }=\mathit{diag}\left\{{\lambda }_1,\dots ,{\lambda }_r\right\}.$ Let C be any r×r symmetric matrix. Then the symmetric matrix $A+{\mathit{XCX}}^T$ has eigenvalues ${\mu }_1,\dots ,{\mu }_r,{\lambda }_{r+1},\dots ,{\lambda }_n$, where ${\mu }_1,\dots ,{\mu }_r$ are eigenvalues of the matrix $\mathrm{\Omega }+C$.

Theorem 1.6 [10] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of complex numbers such that ${\lambda }_1>0$ and $Re{\lambda }_i\le 0$, $i=2,\dots ,n$. Then Λ is realizable if and only if the following conditions are satisfied:

$$s_1=\sum _{i=1}^n{\lambda }_i\ge 0,s_2=\sum _{i=1}^n{\lambda }_i^2\ge 0,s_1^2\le {\mathit{ns}}_2.$$

Since a list of complex numbers $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ is always the spectrum of some n×n matrix A (for instance, a diagonal matrix), from now on we will use, interchangeably, the term list or spectrum. Regarding Minc’s result, the following question arises: Are there spectra no positively realizable that are $\mathcal{UR}$? This question has a positive answer. The following results have been progressively obtained:

1. In Soto and Ccapa [8], it was proved that spectra of real Suleĭmanova type [11], that is,

   $$\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}\text{with}{\lambda }_1>0\ge {\lambda }_2\ge \cdots \ge {\lambda }_n,\mathrm{are}\mathcal{U}\mathrm{ℛ}.$$E1

2. In Soto et al. [12], it was proved that spectra of complex Suleĭmanova type, that is,

   $${\lambda }_1>0,Re{\lambda }_i\le 0,\mid Re{\lambda }_i\mid \ge \mid Im{\lambda }_i\mid ,i=2,\dots ,n\mathrm{are}\mathcal{U}\mathrm{ℛ},$$E2

3. In Diaz and Soto [13], it was proved that spectra of Šmigoc type, that is,

$${\lambda }_1>0,Re{\lambda }_i\le 0,\mid \sqrt{3}Re{\lambda }_i\mid \ge \mid Im{\lambda }_i\mid ,i=2,\dots ,n\mathrm{are}\text{also}\mathcal{U}\mathrm{ℛ}.$$E3

It is interesting to note that in all these three cases, Λ is $\mathcal{UR}$ if and only if Λ is realizable if and only if ${\sum }_{i=1}^n{\lambda }_i\ge 0$. Moreover, these three kinds of spectra are left half-plane spectra, and the good behavior of them led us to think, in a first moment, that any left half-plane spectra were $\mathcal{UR}$. In Julio et al. [14], the authors showed that this is not true. In fact, the spectra

$$\mathrm{\Lambda }=\left\{a,-\frac{a}{4}\pm \frac{\sqrt{5}a}{4}i,-\frac{a}{4}\pm \frac{\sqrt{5}a}{4}i\right\},a>0$$

are not DR, and therefore not $\mathcal{UR}$.

2. Extensions for Minc’s result

In Ref. [15], the authors Borobia and Moro prove the following result:

Theorem 2.1 [15] Let A be a nonnegative irreducible matrix with spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ and a positive row or column. Then A is similar to a positive.

Recently, two extensions of Minc’s result have been obtained in Collao et al. and Johnson et al. [16, 17]. In Ref. [16], Collao et al. showed that a nonnegative matrix $A\in {\mathcal{CS}}_{{\lambda }_1},$ with a positive column, is similar to a positive matrix (the irreducibility condition is not necessary if $A\in {\mathcal{CS}}_{{\lambda }_1}$). Note that if A is nonnegative with a positive row and A^T has a positive eigenvector, then A^T is also similar to a positive matrix. As a consequence we have:

Corollary 2.1 [16] If Λ is the spectrum of a diagonalizable nonnegative matrix $A\in {\mathcal{CS}}_{{\lambda }_1}$ having a positive column, then Λ is $\mathcal{UR}$. If A is diagonalizable nonnegative with a positive row and A^T has a positive eigenvector, then Λ is also $\mathcal{UR}$.

Regarding the second extension for Minc’s result, we have:

Definition 2.1 We call a realization $A=\left[a_{\mathit{ij}}\right]$ off-diagonally positive (ODP), if $a_{\mathit{ij}}>0$ whenever $i\ne j$, and on the diagonal, zero entries are allowed. Furthermore, a realization is quasi-ODP, if all off-diagonal entries are positive, except for one that is zero.

In Ref. [17], Johnson et al. introduced the concept of ODP matrices and proved that if Λ is diagonalizably ODP realizable, then Λ is $\mathcal{UR}$. Note that both extensions contain, as a particular case, Minc’s result in Ref. [4]. Both extensions allow us to significantly increase the set of spectra that can be proved to be $\mathcal{UR}$. The extension in Johnson et al. [17], for instance, allows us to prove that certain spectra $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ with $s_1\left(\mathrm{\Lambda }\right)=0,$ are $\mathcal{UR}$, which is not possible from Minc’s result.

There are a number of spectra that are ODP realizable, as for instance, spectra of real numbers of Suleĭmanova type, which are realizable if and only if ${\sum }_{i=1}^n{\lambda }_i\ge 0$ (see [7, 18]). Moreover, it was proved in Johnson et al. [17] that real spectra of Suleĭmanova type are diagonalizably ODP realizable, and therefore $\mathcal{UR}$. In fact, it is clear that Λ is the spectrum of

$$A=\left[\begin{array}{cccc}{\lambda }_1& & & \\ {\lambda }_1-{\lambda }_2& {\lambda }_2& & \\ & & \ddots & \\ {\lambda }_1-{\lambda }_n& & & {\lambda }_n\end{array}\right]\in {\mathcal{CS}}_{{\lambda }_1}.$$

Then since $A\mathbf{e}={\lambda }_1\mathbf{e}\mathbf{,}$ for ${\mathbf{q}}^T=\left[{\sum }_{i=2}^n{\lambda }_i,-{\lambda }_2,\dots ,-{\lambda }_n\right],$ $A+{\mathbf{eq}}^T$ is a diagonalizable ODP matrix with spectrum Λ. Thus, Λ is $\mathcal{UR}$.

Theorem 2.2 [17] Suppose that a spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ is realizable, with a certain JCF, by a matrix that is either ODP or quasi-ODP. Then, Λ is realizable, by a matrix with any coarser JCF, by a matrix that is ODP or quasi-ODP.

Proof: Suppose that Λ is ODP realizable, with a realizing matrix $A\in {\mathcal{CS}}_{{\lambda }_1}$, with JCF $J\left(A\right)=S^{-1}\mathit{AS}$. Let $B={\mathit{SES}}^{-1}$, where $E={\sum }_{i\in K}{E}_{i,i+1},K\subset \left\{2,\dots ,n-1\right\}$. Since B is such that $\mathit{tr}\left(B\right)=0$ and $B\in {\mathcal{CS}}_0$, then from Theorem 1.2 and Theorem 1.4 with $\mathbf{q}=-\mathbf{b}$ (b is the vector of entries diagonal of B), the matrix $B+{\mathbf{eq}}^T$ has all its diagonal entries zero. Therefore, by picking $\epsilon$ small enough, we have that $A+\epsilon \left(B+{\mathbf{eq}}^T\right)$ is nonnegative with the same eigenvalues as A, but the coarsened JCF. If A is quasi-ODP with a zero entry in position $\left(j,k\right),$ $j\ne k$ and $B+{\mathbf{eq}}^T$ has zero diagonal entries with a negative entry in position $\left(j,k\right),$ $j\ne k,$ then by choosing $\epsilon <0$ small enough, the $\left(j,k\right),$ $j\ne k$ entry in $A+\epsilon \left(B+{\mathbf{eq}}^T\right)$ will be positive. Since $\epsilon <0$ is small enough, it does not matter if the other possible positive entries in $B+{\mathbf{eq}}^T$ become negative. Anyway, $A+\epsilon \left(B+{\mathbf{eq}}^T\right)$ will be nonnegative, cospectral with A, and with the coarsened JCF.

In the event that the original realization is diagonalizable, we have the following important special case, which generalizes the classic result of Minc in [4].

Corollary 2.2 [17] If a spectrum Λ is diagonalizably ODP or quasi-ODP realizable, then Λ is $\mathcal{UR}$.

Proof: Apply Theorem 2.2 with the original blocks all 1×1 in the real eigenvalue case, and all blocks 2×2 (real blocks) in the complex conjugate eigenvalue case, any sequence of merged blocks may be achieved, resulting in any JCF allowed by the spectrum.

Example 2.1 Consider the list $\mathrm{\Lambda }=\left\{\mathrm{6,1,1},-4,-4\right\}$ which is diagonalizably ODP realizable with realizing matrix

$$A=\left[\begin{array}{ccccc}0& \frac{3+\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3+\sqrt{5}}{2}\\ \frac{3+\sqrt{5}}{2}& 0& \frac{3+\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}\\ \frac{3-\sqrt{5}}{2}& \frac{3+\sqrt{5}}{2}& 0& \frac{3+\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}\\ \frac{3-\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3+\sqrt{5}}{2}& 0& \frac{3+\sqrt{5}}{2}\\ \frac{3+\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3-\sqrt{5}}{2}& \frac{3+\sqrt{5}}{2}& 0\end{array}\right].$$

Let $S=\left[{\mathbf{s}}_1,{\mathbf{s}}_2,\dots ,{\mathbf{s}}_n\right]$ be the matrix of eigenvectors of A, where ${\mathbf{s}}_1=\mathbf{e}\mathbf{,}$ such that $S^{-1}\mathit{AS}=J\left(A\right)=\mathit{diag}\left\{\mathrm{6,1,1},-4,-4\right\}$. In particular, for $J\left(A\right)=\mathit{diag}\left\{J_1\left(6\right),J_2\left(1\right),J_2\left(-4\right)\right\},$ where $J_k\left(\lambda \right)$ denotes a k×k Jordan block corresponding to the eigenvalue $\lambda ,$ we have, for $\mathbf{q}={\left(-\frac{\sqrt{5}-1}{10},-\frac{2}{5},\frac{\sqrt{5}+1}{10},\frac{\sqrt{5}+1}{10},-\frac{\sqrt{5}-1}{10}\right)}^T$, the matrix

$${\mathit{SES}}^{-1}+{\mathbf{eq}}^T=\left[\begin{array}{ccccc}0& -\frac{\sqrt{5}}{10}-\frac{1}{2}& \frac{1}{2}-\frac{\sqrt{5}}{10}& \frac{2\sqrt{5}}{5}& -\frac{\sqrt{5}}{5}\\ -\frac{\sqrt{5}}{5}& 0& \frac{\sqrt{5}}{5}& -\frac{\sqrt{5}}{5}& \frac{\sqrt{5}}{5}\\ \frac{\sqrt{5}}{10}+\frac{1}{2}& \frac{\sqrt{5}}{10}-\frac{1}{2}& 0& \frac{\sqrt{5}}{5}& -\frac{2\sqrt{5}}{5}\\ -\frac{\sqrt{5}}{5}& \frac{\sqrt{5}}{10}-\frac{1}{2}& \frac{\sqrt{5}}{5}& 0& \frac{1}{2}-\frac{\sqrt{5}}{10}\\ -\frac{\sqrt{5}}{5}& -\frac{\sqrt{5}}{10}-\frac{1}{2}& \frac{\sqrt{5}}{5}& \frac{\sqrt{5}}{10}+\frac{1}{2}& 0\end{array}\right],$$

where $E=E_{23}+E_{45}$, having all its diagonal entries zero. Thus, we chose $\epsilon \ne 0$ small enough, to obtain $A+\epsilon \left({\mathit{SES}}^{-1}+{\mathbf{eq}}^T\right),$ which is a nonnegative ODP matrix with JCF having Jordan blocks $J_1\left(6\right),J_2\left(1\right),J_2\left(-4\right)$. In a similar way, we may obtain a nonnegative matrix with spectrum Λ, for each one of the other JCF allowed by Λ. Thus, Λ is $\mathcal{UR}$.

3. On universal realizability criteria

It has been commented in the Introduction that real and complex spectra of Suleĭmanova type are $\mathcal{UR}$ [8, 12]. In Collao et al. [19], the authors study lists with two positive eigenvalues and they prove that, under certain conditions, these types of lists are not only realizable, but also $\mathcal{UR}$.

Theorem 3.1 [19] Let $\mathrm{\Lambda }=\left\{p,q,-r_1,-r_2,\dots ,-r_{n-2}\right\}$ be a list of n real numbers with

$$p+q-\sum _{j=1}^{n-2}{r}_j=0,$$

in which $p,q,r_j>0;$ $p>q,r_j,$ $j=1,2,\dots ,n-2;$ $-r_j\ge -r_{j+1},j=1,2,\dots ,n-3.$ If there is a decomposition

$$\begin{array}{l}R=\left\{r_1,r_2,\dots ,r_{n-2}\right\}=R_1\cup R_2\text{with}\\ R_1=\left\{{\alpha }_1,\dots ,{\alpha }_s\right\},R_2=\left\{{\beta }_1,\dots ,{\beta }_{n-2-s}\right\},{\alpha }_i,{\beta }_i\in R,\end{array}$$

in such a way that

$$p\ge \sum _{i=1}^s{\alpha }_i\ge \sum _{i=1}^{n-2-s}{\beta }_i,\text{then}\mathrm{\Lambda }\text{is}\mathcal{U}\mathrm{ℛ}.$$

Proof: Take

$$\begin{array}{c}\mathrm{\Lambda }={\mathrm{\Lambda }}_0\cup {\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2\text{with}{\mathrm{\Lambda }}_0=\left\{p,q\right\},\\ {\mathrm{\Lambda }}_1=\left\{-{\alpha }_1,\dots ,-{\alpha }_s\right\},{\mathrm{\Lambda }}_2=\left\{-{\beta }_1,\dots ,-{\beta }_t\right\},t=n-2-s\\ {\alpha }_i,{\beta }_i>0;-{\alpha }_i,-{\beta }_i\in \left\{-r_1,-r_2,\dots ,-r_{n-2}\right\},\end{array}$$

with the associated lists

$${\mathrm{\Gamma }}_1=\left\{p-t,-{\alpha }_1,\dots ,-{\alpha }_s\right\},{\mathrm{\Gamma }}_2=\left\{q+t,-{\beta }_1,\dots ,-{\beta }_t\right\},$$

with $t\ge 0$ and $p-t=\sum _{i=1}^s{\alpha }_i,$ $q+t=\sum _{i=1}^t{\beta }_i.$ Note that the lists ${\mathrm{\Gamma }}_1,{\mathrm{\Gamma }}_2$ are of real Suleĭmanova type, then from Soto and Ccapa [8], they are $\mathcal{UR}$. Let $A_1$ and $A_2$ be the realizing matrices of ${\mathrm{\Gamma }}_1$ and ${\mathrm{\Gamma }}_2$, respectively. Since $p-q-t\ge t\ge 0,$

$$B=\left[\begin{array}{cc}p-t& t\\ p-q-t& q+t\end{array}\right]\text{is nonnegative with spectrum}{\mathrm{\Lambda }}_0$$

and the required diagonal entries. Thus, from Theorem 1.3 with X the n×2 nonnegative matrix of eigenvectors of $\left[\begin{array}{cc}{A}_1& \\ & A_2\end{array}\right]$ and C the 2×n nonnegative matrix, such that $\mathit{CX}=B-\mathrm{\Omega }$ with $\mathrm{\Omega }=\mathit{diag}\left\{p-t,q+t\right\},$

$$\left[\begin{array}{cc}{A}_1& \\ & A_2\end{array}\right]+\mathit{XC}\text{is nonnegative with spectrum},\mathrm{\Lambda }$$

and with the required JCF allowed by Λ. Then, Λ is $\mathcal{UR}$.

Note that if $\mathrm{\Lambda }=\left\{p,q,-r,-r,\dots ,-r\right\}$ with $p+q-\left(n-2\right)r=0,$ where $p,q,r>0,$ $p>q,r;$ $q>r,$ then if n is even, Λ is $\mathcal{UR}$. If n is odd with $p\ge \frac{\left(n-1\right)}{2}r,$ then Λ is also $\mathcal{UR}$.

Example 3.1 Let $\mathrm{\Lambda }=\left\{19,1,-2,-2,-3,-3,-5,-5\right\}$ (with)

$$\begin{array}{c}{\mathrm{\Lambda }}_0=\left\{19,1\right\},{\mathrm{\Lambda }}_1={\mathrm{\Lambda }}_2=\left\{-2,-3,-5\right\}\\ {\mathrm{\Gamma }}_1={\mathrm{\Gamma }}_2=\left\{10,-2,-3,-5\right\}.\end{array}$$

We want to construct a nonnegative matrix A with JCF

$$J=\mathit{diag}\left\{J_1\left(19\right),J_1\left(1\right),J_2\left(-2\right),J_2\left(-3\right),J_1\left(-5\right),J_1\left(-5\right)\right\}.$$

Then we compute

$$\begin{array}{c}{A}_1=\left[\begin{array}{cccc}10& 0& 0& 0\\ 15& -5& 0& 0\\ 13& 0& -2& -1\\ 13& 0& 0& -3\end{array}\right]+{\mathbf{eq}}^T=\left[\begin{array}{cccc}0& 5& 2& 3\\ 5& 0& 2& 3\\ 3& 5& 0& 2\\ 3& 5& 2& 0\end{array}\right]\\ A_2=\left[\begin{array}{cccc}10& 0& 0& 0\\ 13& -2& -1& 0\\ 13& 0& -3& 0\\ 15& 0& 0& -5\end{array}\right]+{\mathbf{eq}}^T=\left[\begin{array}{cccc}0& 2& 3& 5\\ 3& 0& 2& 5\\ 3& 2& 0& 5\\ 5& 2& 3& 0\end{array}\right]\text{and}B=\left[\begin{array}{cc}10& 9\\ 9& 10\end{array}\right].\end{array}$$

Then

$$A=\left[\begin{array}{cccccccc}0& 5& 2& 3& 0& 0& 0& 0\\ 5& 0& 2& 3& 0& 0& 0& 0\\ 3& 5& 0& 2& 0& 0& 0& 0\\ 3& 5& 2& 0& -1& 1& 0& 0\\ 0& 0& 0& 0& 0& 2& 3& 5\\ 0& 0& 0& 0& 3& 0& 2& 5\\ 0& 0& 0& 0& 3& 2& 0& 5\\ 0& 0& 0& 0& 5& 2& 3& 0\end{array}\right]+\left[\begin{array}{cc}1& 0\\ 1& 0\\ 1& 0\\ 1& 0\\ 0& 1\\ 0& 1\\ 0& 1\\ 0& 1\end{array}\right]\left[\begin{array}{cccccccc}0& 0& 0& 0& 9& 0& 0& 0\\ 9& 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

is the desired matrix. In the same way, we may construct a nonnegative matrix for each one of the remaining JCF.

Here, we consider more general lists of complex numbers and we give new sufficient conditions for the URP to have a solution. We know that diagonalizability is a necessary condition. Since normal matrices are diagonalizable, we set the following result [20], in which we use normal ODP matrices:

Theorem 3.2 [20] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of complex numbers with $\mathrm{\Lambda }=\overline{\mathrm{\Lambda }}$, ${\lambda }_1\ge {max}_i\left|{\lambda }_i\right|,$ $\sum _{i=1}^n{\lambda }_i\ge 0$ and let

$$\begin{array}{c}\mathrm{\Lambda }={\mathrm{\Lambda }}_0\cup {\mathrm{\Lambda }}_1\cup \cdots \cup {\mathrm{\Lambda }}_{p_0}\\ {\mathrm{\Lambda }}_0=\left\{{\lambda }_{01},{\lambda }_{02},\dots ,{\lambda }_{0p_0}\right\},{\lambda }_{01}={\lambda }_1\\ {\mathrm{\Lambda }}_k=\left\{{\lambda }_{k1},{\lambda }_{k2},\dots ,{\lambda }_{{\mathit{kp}}_k}\right\},k=1,\dots ,p_0,\end{array}$$

where some lists ${\mathrm{\Lambda }}_k,$ $k=1,\dots ,p_0,$ can be empty. Suppose that the following conditions are satisfied:

1. For each $k=1,\dots ,p_0,$ there exists a normal ODP matrix with spectrum

   $${\mathrm{\Gamma }}_k=\left\{{\omega }_k,{\lambda }_{k1},\dots ,{\lambda }_{{\mathit{kp}}_k}\right\},0\le {\omega }_k<{\lambda }_1,\text{where}{\omega }_k\text{is the Perron eigenvalue}.$$

2. There exists a $p_0\times p_0$ normal ODP matrix with spectrum ${\mathrm{\Lambda }}_0$ and diagonal entries ${\omega }_1\ge {\omega }_2\ge \cdots \ge {\omega }_{p_0}$.

Then Λ is $\mathcal{UR}$.

Proof: From i) let $A_k$ be a $\left(p_k+1\right)\times \left(p_k+1\right)$ normal ODP matrix with spectrum

$${\mathrm{\Gamma }}_k=\left\{{\omega }_k,{\lambda }_{k1},\dots ,{\lambda }_{{\mathit{kp}}_k}\right\},k=1,\dots ,p_0,0\le {\omega }_k<{\lambda }_1.$$

Then $A=\mathit{diag}\left\{A_1,A_2,\dots ,A_{p_0}\right\}$ is an n×n normal nonnegative matrix realizing $\mathrm{\Gamma }={\mathrm{\Gamma }}_1\cup \cdots \cup {\mathrm{\Gamma }}_{p_0}.$ Let

$$X=\left[\begin{array}{cccc}{\mathbf{x}}_1& \mathbf{0}& \cdots & \mathbf{0}\\ \mathbf{0}& {\mathbf{x}}_2& \cdots & \mathbf{0}\\ ⋮& ⋮& \ddots & ⋮\\ \mathbf{0}& \mathbf{0}& \cdots & {\mathbf{x}}_{p_0}\end{array}\right]$$

the matrix of normalized eigenvectors of A, where ${\mathbf{x}}_k={\left[x_{k1},\dots ,x_{{\mathit{kp}}_k}\right]}^T$ is the Perron eigenvector of $A_k,$ $A_k{\mathbf{x}}_k={\omega }_k{\mathbf{x}}_k$ with $‖{\mathbf{x}}_k‖=1.$ Since $A_k$ is an ODP matrix, it is nonnegative irreducible, and then ${\mathbf{x}}_k$ is a positive eigenvector.

From ii) let B be a $p_0\times p_0$ normal ODP matrix with spectrum ${\mathrm{\Lambda }}_0$ and diagonal entries ${\omega }_1,\dots ,{\omega }_{p_0}.$ Let $\mathrm{\Omega }=\mathit{diag}\left\{{\omega }_1,\dots ,{\omega }_{p_0}\right\},$ and $C=B-\mathrm{\Omega }.$ Then, since $A,X$ and C are nonnegative with A and C normal, $M=A+{\mathit{XCX}}^T$ is normal nonnegative with spectrum Λ. Moreover, since $A_k,$ $k=1,\dots ,p_0,$ and C are ODP matrices, M is also an ODP matrix. Thus, Λ is realizable by a normal ODP matrix, and from the extension in Johnson et al. [17] Λ is $\mathcal{UR}$.

Many of the known sufficient conditions in the literature about both problems, NIEP and URP, have been obtained from Theorem 1.3 (Rado’s Theorem). A number of distinct versions of Rado’s result have also been obtained. In Arrieta et al. [21], it has been proved as regards a Rado diagonalizable version. It will be useful for constructing diagonalizable nonnegative matrices, with prescribed spectrum, and for deciding about the universal realizability of spectra.

Theorem 3.3 [21] Let A be an n×n diagonalizable matrix with spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}.$ Let $X=\left[{\mathbf{x}}_1|{\mathbf{x}}_2|\cdots |{\mathbf{x}}_r\right]$ be an n×r matrix, with $\mathit{rank}\left(X\right)=r,$ $r\le n,$ such that $A{\mathbf{x}}_i={\lambda }_i{\mathbf{x}}_i,$ $i=1,\dots ,r$. Let

$\mathrm{\Omega }=\mathit{diag}\left\{{\lambda }_1,\dots ,{\lambda }_r\right\}$ and let $C=\left[c_{\mathit{ij}}\right]$ be an $r\times r$ matrix such that $B=\mathrm{\Omega }+C$ is a diagonalizable matrix. Let $J\left(A\right)=S^{-1}\mathit{AS}$ be the JCF of A, with $S=\left[X|Y\right],$ $S^{-1}=\left[\begin{array}{c}\tilde{X}\\ \tilde{Y}\end{array}\right].$ Then, the matrix $A+\mathit{XC}\tilde{X}$ is diagonalizable with spectrum ${\mu }_1,\dots ,{\mu }_r,{\lambda }_{r+1},\dots ,{\lambda }_n,$ where ${\mu }_1,\dots ,{\mu }_r$ are eigenvalues of B.

Proof: Since $S^{-1}S=I_n,$ then $\tilde{X}X=I_r,$ $\tilde{X}Y=0,$ $\tilde{Y}X=0,$ $\tilde{Y}Y=I_{n-r}$. Since $J\left(A\right)=\mathrm{\Omega }\oplus D,$ with $D=\mathit{diag}\left\{{\lambda }_{r+1},\dots ,{\lambda }_n\right\},$ then,

$$\begin{array}{c}{S}^{-1}\left(A+\mathit{XC}\tilde{X}\right)S=\mathrm{\Omega }\oplus D+S^{-1}\mathit{XC}\tilde{X}S\\ =\mathrm{\Omega }\oplus D+\left[\begin{array}{c}\tilde{X}\\ \tilde{Y}\end{array}\right]\mathit{XC}\tilde{X}\left[XY\right]\\ =\mathrm{\Omega }\oplus D+\left[\begin{array}{c}{I}_r\\ 0\end{array}\right]C\left[\begin{array}{cc}{I}_r& 0\end{array}\right]\\ =\mathrm{\Omega }\oplus D+\left[\begin{array}{cc}C& 0\\ 0& 0\end{array}\right]\\ =\left[\begin{array}{cc}B& \mathbf{0}\\ \mathbf{0}& D\end{array}\right].\end{array}$$

Then $A+\mathit{XC}\tilde{X}$ is diagonalizable, and from Theorem 1.3, it has the spectrum ${\mu }_1,\dots ,{\mu }_r,{\lambda }_{r+1},\dots ,{\lambda }_n,$ where ${\mu }_1,\dots ,{\mu }_r$ are eigenvalues of B.

Corollary 3.1 [21] If in Theorem 3.3, the matrices A and B are nonnegative diagonalizable and, $X,\tilde{X}$ are nonnegative, then $A+\mathit{XC}\tilde{X}$ is nonnegative diagonalizable with spectrum ${\mu }_1,\dots ,{\mu }_r,{\lambda }_{r+1},\dots ,{\lambda }_n$.

If in Theorem 3.3, the matrix A is block diagonal, with diagonalizable ODP blocks, and the matrix B is diagonalizable ODP, then Λ is $\mathcal{UR}$.

Example 3.2 Consider the spectrum

$$\mathrm{\Lambda }=\left\{\mathrm{7,2,0},-1,-2+i,-2-i,-2+i,-2-i\right\},$$

with ${\mathrm{\Lambda }}_0=\left\{\mathrm{7,2,0}\right\},$ ${\mathrm{\Gamma }}_1={\mathrm{\Gamma }}_2=\left\{4,-2+i,-2+i\right\},$ ${\mathrm{\Gamma }}_3=\left\{1,-1\right\}.$The matrices

$$\begin{array}{c}B=\left[\begin{array}{ccc}4& \sqrt{\frac{24}{5}}& \sqrt{\frac{6}{5}}\\ \sqrt{\frac{24}{5}}& 4& 2\\ \sqrt{\frac{6}{5}}& 2& 1\end{array}\right],\\ A_1=A_2=\left[\begin{array}{ccc}0& 2& 2\\ 3& 0& 1\\ 1& 3& 0\end{array}\right],A_3=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]\end{array}$$

are diagonalizable with spectrum ${\mathrm{\Lambda }}_0,$ ${\mathrm{\Gamma }}_1,$ ${\mathrm{\Gamma }}_2,$ and ${\mathrm{\Gamma }}_3,$_, respectively. Then,

$$A=\left(A_1\oplus A_2\oplus A_3\right)+\mathit{XC}\tilde{X}$$

is diagonalizable ODP with spectrum Λ. Hence, from the extension in Johnson et al. [17], Corollary 4.1, Λ is $\mathcal{UR}$.

The following result from Ref. [21] gives a diagonalizable version of a Lemma by Fiedler [22] that may be applied to decide the universal realizability of some lists of complex numbers. Although the result is more general, we establish it here, without proof, for diagonalizable nonnegative matrices.

Corollary 3.2 [21] Let A and B be n×n and m×m diagonalizable nonnegative matrices with spectrum ${\mathrm{\Gamma }}_1=\left\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n\right\}$ and ${\mathrm{\Gamma }}_2=\left\{{\beta }_1,{\beta }_2,\dots ,{\beta }_m\right\},$ respectively. Let u and v, with $‖\mathbf{u}‖=‖\mathbf{v}‖=1,$ be the Perron eigenvectors of A and B, associated to ${\alpha }_1$ and ${\beta }_1,$ respectively. Let $M=A\oplus B$ and let $J\left(M\right)=S^{-1}\mathit{MS}$ be the JCF of M, with $S=\left[X|Y\right],$ $S^{-1}=\left[\begin{array}{c}\tilde{X}\\ \tilde{Y}\end{array}\right].$ Then for $\rho >0,$ the matrix $F=\left[\begin{array}{cc}A& \rho {\mathbf{uv}}^{\ast }\\ \rho {\mathbf{vu}}^{\ast }& B\end{array}\right]$ is diagonalizable with spectrum $\mathrm{\Lambda }=\left\{{\gamma }_1,{\gamma }_2,{\alpha }_2,\dots ,{\alpha }_n,{\beta }_2,\dots ,{\beta }_m\right\},$ where ${\gamma }_1,{\gamma }_2$ are eigenvalues of $B=\left[\begin{array}{cc}{\alpha }_1& \rho \\ \rho & {\beta }_1\end{array}\right]$.

Corollary 3.3 [21] If in Corollary 3.2, A and B are normal nonnegative ODP matrices, then the matrix

$$F=\left[\begin{array}{cc}A& \rho {\mathbf{uv}}^{\ast }\\ \rho {\mathbf{vu}}^{\ast }& B\end{array}\right],$$

is normal nonnegative ODP with the prescribed spectrum Λ. Hence, Λ is $\mathcal{UR}$.

Proof: If A and B are ODP matrices, they are irreducible. Therefore, the Perron eigenvectors u and v are positive. Thus, F is normal nonnegative ODP, and Λ is $\mathcal{UR}$.

The following result also establishes a universal realizability criterion.

Theorem 3.4 [21] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\}$ be a realizable list of complex numbers, with ${\lambda }_1,{\lambda }_2$ being real numbers. Suppose that the lists

$${\mathrm{\Lambda }}_1=\left\{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_p\right\},{\mathrm{\Lambda }}_2=\left\{{\beta }_1,{\beta }_2,\dots ,{\beta }_q\right\},$$

with $p+q=n,$ ${\alpha }_i\in \mathrm{\Lambda },$ $i=2,3,\dots ,p,$ ${\beta }_j\in \mathrm{\Lambda },$ $j=2,3,\dots ,q,$ and ${\alpha }_1+{\beta }_1={\lambda }_1+{\lambda }_2,$ are diagonalizably ODP realizable. Then, Λ is $\mathcal{UR}$.

Proof: Let $A_1$ and $A_2$ be p×p and q×q diagonalizable ODP matrices, with spectrum ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2,$ respectively. Let u and $\mathbf{v}\mathbf{,}$ $‖\mathbf{u}‖=‖\mathbf{v}‖=1,$ be the Perron eigenvectors of $A_1$ and $A_2,$ associated to the Perron eigenvalues ${\alpha }_1$ and ${\beta }_1,$ respectively. Since $A_1$ and $A_2$ are irreducible, then u and v are positive. As ${\alpha }_1+{\beta }_1={\lambda }_1+{\lambda }_2,$ there is a real number $\rho >0,$ such that the $2\times 2$ matrix $\left[\begin{array}{cc}{\alpha }_1& \rho \\ \rho & {\beta }_1\end{array}\right]$ has eigenvalues ${\lambda }_1,{\lambda }_2.$ Therefore, from Corollary 3.2,

$$A=\left[\begin{array}{cc}{A}_1& \rho {\mathbf{uv}}^T\\ \rho {\mathbf{vu}}^T& A_2\end{array}\right]\text{is diagonalizable}\mathrm{ODP}\text{with spectrum}\mathrm{\Lambda }$$

Hence, from the extension in Johnson et al. [17] Λ is $\mathcal{UR}$.

Finally, we apply Theorem 3.3 to more general lists of complex numbers (not in the left half-plane). For instance,

i) $\mathrm{\Lambda }=\left\{\mathrm{8,6,3,3},-5,-5,-5,-5\right\}$, with ${\mathrm{\Lambda }}_0=\left\{8,6\right\},$ ${\mathrm{\Lambda }}_1={\mathrm{\Lambda }}_2=\left\{3,-5,-5\right\}$ and ${\mathrm{\Gamma }}_1={\mathrm{\Gamma }}_2=\left\{7,3,-5,-5\right\},$ is diagonalizably ODP realizable and therefore it is $\mathcal{UR}$. ii) $\mathrm{\Lambda }=\left\{\mathrm{7,5,1,1},-4,-4,-6\right\}$ with ${\mathrm{\Lambda }}_0=\left\{7,5\right\},$ ${\mathrm{\Gamma }}_1=\left\{\mathrm{6,1,1},-4,-4\right\},$ ${\mathrm{\Gamma }}_2=\left\{6,-6\right\}$ is also diagonalizably ODP realizable and therefore it is $\mathcal{UR}$. iii) $\mathrm{\Lambda }=\left\{\mathrm{10,3,2},-1,-1,3i,-3i,-1\pm 2i,-1\pm 2i\right\}$ with ${\mathrm{\Lambda }}_0=\left\{\mathrm{10,3,2}\right\},$ ${\mathrm{\Gamma }}_1=\left\{6,3i,-3i\right\},$ ${\mathrm{\Gamma }}_2={\mathrm{\Gamma }}_3=\left\{\frac{9}{2},-1,-1\pm 2i\right\}$ is the spectrum of a diagonalizable nonnegative matrix $A\in {\mathcal{CS}}_{10}$ with a positive column. Hence, it is also $\mathcal{UR}$. iv) $\mathrm{\Lambda }=\left\{\mathrm{13,3,1}+4i,1-4i,1+4i,1-4i\right\}$ with ${\mathrm{\Lambda }}_0=\left\{13,3\right\},$ ${\mathrm{\Gamma }}_1={\mathrm{\Gamma }}_2=\left\{8,1+4i,1-4i\right\}$ is the spectrum of a diagonalizable positive matrix. Hence, it is also $\mathcal{UR}$. One of the advantages of applying this procedure is that to decide whether $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ is $\mathcal{UR}$ we do not need to compute a nonnegative matrix for each JCF allowed by Λ. It is enough to show that Λ is diagonalizably ODP realizable or Λ is the spectrum of a diagonalizable nonnegative matrix with constant row sums and a positive column.

4. The URP for structured matrices

4.1 The URP for permutative matrices

An n×n permutative matrix is a matrix in which every row is a permutation of its first row, that is,

Definition 4.1 Let $\mathbf{x}\in {\mathrm{ℝ}}^n$ and let $P_2,P_3,\dots ,P_n$ be n×n permutation matrices. A permutative matrix is any matrix of the form

$$P=\left[\begin{array}{c}{\mathbf{x}}^T\\ {\left(P_2\mathbf{x}\right)}^T\\ ⋮\\ {\left(P_n\mathbf{x}\right)}^T\end{array}\right].$$

It is clear that $P\in {\mathcal{CS}}_S,$ where S is the sum of the entries of the vector x. Permutative matrices were introduced and first studied in Hu et al. [23]. In this section, we study the permutative universal realizability problem, that is, the problem of determining the existence and construction of a nonnegative permutative matrix, with prescribed complex spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$, for each possible JCF allowed by Λ.

The following result gives a sufficient condition for that a list $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ of real numbers, with ${\lambda }_1>0>{\lambda }_2>{\lambda }_3\ge {\lambda }_4\ge \cdots \ge {\lambda }_n,$ to be permutatively universally realizable.

Theorem 4.1 [24] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of real numbers, with ${\lambda }_1>0>{\lambda }_2>{\lambda }_3\ge {\lambda }_4\ge \cdots \ge {\lambda }_n.$ Then the following statements are equivalent:

1. ${\sum }_{i=1}^n{\lambda }_i\ge 0,$

2. Λ is permutatively realizable,

3. Λ is permutatively $\mathcal{UR}$.

The following example illustrates Theorem 4.1. It shows how we may obtain, a permutative realization, for each JCF allowed by a given real list ${\lambda }_1>0>{\lambda }_2>{\lambda }_3\ge \cdots \ge {\lambda }_n$.

Example 4.1 Let us consider the list

$$\mathrm{\Lambda }=\left\{30,-1,-5,-5,-5,-7,-7\right\}.$$

We start with

$$B=\left[\begin{array}{ccccccc}30& 0& 0& 0& 0& 0& 0\\ 31& -1& 0& 0& 0& 0& 0\\ 35& 4& -5& -4& 0& 0& 0\\ 35& 4& 0& -5& -4& 0& 0\\ 35& 0& 0& 0& -5& 0& 0\\ 31& 6& 2& 0& 0& -7& -2\\ 31& 6& 0& 0& 0& 0& -7\end{array}\right].$$

Then, for ${\mathbf{q}}^T=\left[\begin{array}{ccccccc}-30& 1& 5& 5& 5& 7& 7\end{array}\right],$ we have that

$$B+{\mathbf{eq}}^T=\left[\begin{array}{ccccccc}0& 1& 5& 5& 5& 7& 7\\ 1& 0& 5& 5& 5& 7& 7\\ 5& 5& 0& 1& 5& 7& 7\\ 5& 5& 5& 0& 1& 7& 7\\ 5& 1& 5& 5& 0& 7& 7\\ 1& 7& 7& 5& 5& 0& 5\\ 1& 7& 5& 5& 5& 7& 0\end{array}\right]$$

is permutative with JCF $J\left(B+{\mathbf{eq}}^T\right)=\mathit{diag}\left\{J_1\left(30\right),J_1\left(-1\right),J_3\left(-5\right),J_2\left(-7\right)\right\}.$ For

$$B+{\mathbf{eq}}^T=\left[\begin{array}{ccccccc}30& 0& 0& 0& 0& 0& 0\\ 31& -1& 0& 0& 0& 0& 0\\ 35& 4& -5& -4& 0& 0& 0\\ 35& 0& 0& -5& 0& 0& 0\\ 35& 0& 0& 0& -5& 0& 0\\ 31& 6& 2& 0& 0& -7& -2\\ 31& 6& 0& 0& 0& 0& -7\end{array}\right]+{\mathbf{eq}}^T,$$

we obtain the JCF $J\left(B+{\mathbf{eq}}^T\right)=\mathit{diag}\left\{J_1\left(30\right),J_1\left(-1\right),J_2\left(-5\right),J_1\left(-5\right),J_2\left(-7\right)\right\},$ and so on.

From Theorem 1.3, we have the following Rado permutative version:

Theorem 4.2 [24] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a realizable list of real numbers, where ${\lambda }_1>{\lambda }_2>\cdots >{\lambda }_p>0>{\lambda }_{p+1}\ge {\lambda }_{p+2}\ge \cdots \ge {\lambda }_n,$ with $-{\lambda }_n\ge {\lambda }_2,$ $n\ge 2p$ for n even, and $n\ge 2p+1$ for n odd n, $p\ge 2.$ Suppose that:

1. Λ admits a decomposition $\mathrm{\Lambda }={\mathrm{\Lambda }}_0\cup \underset{p\text{times}}{\underbrace{{\mathrm{\Lambda }}_1\cup \cdots \cup {\mathrm{\Lambda }}_1}},$ where

   $$\begin{array}{l}{\mathrm{\Lambda }}_0=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_p\right\},{\mathrm{\Lambda }}_1=\left\{{\lambda }_{11},{\lambda }_{12},\dots ,{\lambda }_{1r}\right\},\\ {\lambda }_{1k}\in \left\{{\lambda }_{p+1},{\lambda }_{p+2},\dots ,{\lambda }_n\right\},k=1,2,\dots ,r,\end{array}$$

   such that ${\mathrm{\Gamma }}_1=\left\{\lambda \right\}\cup {\mathrm{\Lambda }}_1,$ $0\le \lambda \le {\lambda }_1,$ is permutatively (circulant) realizable.

2. There exists a p×p permutative (circulant) nonnegative matrix with spectrum ${\mathrm{\Lambda }}_0$ and diagonal entries $\lambda ,\lambda ,\dots ,\lambda$ (p times).

Then, Λ is permutatively $\mathcal{UR}$.

Example 4.2 Consider the spectrum

$$\begin{array}{c}\mathrm{\Lambda }=\left\{\mathrm{4,1,1},-2,-2,-2\right\},\text{with}\\ {\mathrm{\Lambda }}_0=\left\{\mathrm{4,1,1}\right\},{\mathrm{\Gamma }}_1=\left\{2,-2\right\}.\end{array}$$

Then,

$$B=\left[\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right],\text{and}{A}_1^{\prime }=\left[\begin{array}{cc}0& 2\\ 2& 0\end{array}\right],$$

are permutative, realizing ${\mathrm{\Lambda }}_0$ and ${\mathrm{\Gamma }}_1,$ respectively. Then,

$$A_1=A_1^{\prime }\oplus A_1^{\prime }\oplus A_1^{\prime }+\mathit{XC}=\left[\begin{array}{cccccc}0& 2& 1& 0& 1& 0\\ 2& 0& 1& 0& 1& 0\\ 1& 0& 0& 2& 1& 0\\ 1& 0& 2& 0& 1& 0\\ 1& 0& 1& 0& 0& 2\\ 1& 0& 1& 0& 2& 0\end{array}\right]$$

is nonnegative permutative with diagonal JCF. Next, for

$$A^{″}=\left[\begin{array}{cccccc}0& 2& 0& 0& 0& 0\\ 2& 0& 0& 0& 0& 0\\ 0& 0& 0& 2& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 0& 0& 2\\ -1& 1& 0& 0& 2& 0\end{array}\right],$$

we obtain $A_2=A^{″}+\mathit{XC},$ nonnegative permutative, with JCF having one 2×2 Jordan block $J_2\left(-2\right).$ Next, for

$$A^{‴}=\left[\begin{array}{cccccc}0& 2& 0& 0& 0& 0\\ 2& 0& 0& 0& 0& 0\\ -1& 1& 0& 2& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& -1& 1& 0& 2\\ 0& 0& 0& 0& 2& 0\end{array}\right],$$

we obtain $A_3=A^{‴}+\mathit{XC},$ nonnegative permutative, with JCF having a 3×3 Jordan block $J_3\left(-2\right).$ Thus, $\mathrm{\Lambda }=\left\{\mathrm{4,1,1},-2,-2,-2\right\}$ is permutatively $\mathcal{UR}$.

4.2 The URP for centrosymmetric matrices

Centrosymmetric matrices have applications in many fields, such as physics, communication theory, differential equations, numerical analysis, engineering and statistics. An n×n real matrix $C=\left[c_{\mathit{ij}}\right]$ is said to be centrosymmetric, if its entries satisfy the relation $c_{\mathit{ij}}=c_{n-i+1,n-j+1}$, or equivalently if $J_n{\mathit{CJ}}_n=C$, where $J_n=\left[{\mathbf{e}}_n,{\mathbf{e}}_{n-1},\dots ,{\mathbf{e}}_1\right]$. In this section, we study the centrosymmetric universal realizability problem, that is, the problem of determining conditions for the existence and construction of a centrosymmetric realizing matrix, for each JCF allowed by a given list Λ of complex numbers.

The following two results are of constructive nature, in the sense that if they are satisfied, then a centrosymmetric realizing matrix with spectrum Λ can be constructed for each JCF associated to Λ. We introduce them here without proof.

Theorem 4.3 [25] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a realizable list of complex numbers with ${\lambda }_1$ simple, $n=2m.$ Suppose $\mathrm{\Lambda }={\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2$ with ${\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2=\varnothing$, where ${\mathrm{\Lambda }}_1$ is diagonalizably realizable by an m×m matrix $W_1$ and ${\mathrm{\Lambda }}_2$ is the spectrum of an m×m real diagonalizable matrix $W_2$ (not necessarily nonnegative). If $W_1+W_2$ is ODP and $W_1-W_2$ is positive, then Λ is centrosymmetrically $\mathcal{UR}$.

Theorem 4.4 [25] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a realizable list of complex numbers with ${\lambda }_1$ simple, $n=2m+1$. Suppose $\mathrm{\Lambda }={\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2$ with ${\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2=\varnothing$, where ${\mathrm{\Lambda }}_1$ is diagonalizably realizable by the $\left(m+1\right)\times \left(m+1\right)$ ODP matrix

$$\left[\begin{array}{cc}{W}_1& \mathbf{a}\\ {\mathbf{b}}^T& c\end{array}\right]$$

and ${\mathrm{\Lambda }}_2$ is the spectrum of an m×m real diagonalizable matrix $W_2$. If $W_1+W_2$ is ODP and $W_1-W_2$ is positive, then Λ is centrosymmetrically $\mathcal{UR}$.

Example 4.3 Consider the list

$$\mathrm{\Lambda }=\left\{10,-2,-2,-2,-1+2i,-1-2i,-1+2i,-1-2i\right\}.$$

We apply Theorem 4.3 to show that Λ is centrosymmetrically $\mathcal{UR}$. We take

$${\mathrm{\Lambda }}_1=\left\{10,-2,-2,-2\right\},{\mathrm{\Lambda }}_2=\left\{-1+2i,-1-2i,-1+2i,-1-2i\right\}$$

which are the spectrum of

$$W_1=\left[\begin{array}{cccc}1& 3& 3& 3\\ 3& 1& 3& 3\\ 3& 3& 1& 3\\ 3& 3& 3& 1\end{array}\right]\text{and}{W}_2=\left[\begin{array}{cccc}-1& -2& 0& 0\\ 2& -1& 0& 0\\ 0& 0& -1& -2\\ 0& 0& 2& -1\end{array}\right]$$

respectively. Next, we compute the centrosymmetric ODP matrix

$$C_1=\frac{1}{2}\left[\begin{array}{cc}{W}_1+W_2& \left(W_1-W_2\right)J_4\\ J_4\left(W_1-W_2\right)& J_4\left(W_1+W_2\right)J_4\end{array}\right]=\frac{1}{2}\left[\begin{array}{cccccccc}0& 1& 3& 3& 3& 3& 5& 2\\ 5& 0& 3& 3& 3& 3& 2& 1\\ 3& 3& 0& 1& 5& 2& 3& 3\\ 3& 3& 5& 0& 2& 1& 3& 3\\ 3& 3& 1& 2& 0& 5& 3& 3\\ 3& 3& 2& 5& 1& 0& 3& 3\\ 1& 2& 3& 3& 3& 3& 0& 5\\ 2& 5& 3& 3& 3& 3& 1& 0\end{array}\right]$$

with diagonal JCF. Now, we compute a centrosymmetric ODP matrix $C_2$ with JCF

$$J\left(C_2\right)=\mathit{diag}\left\{J_1\left(10\right),J_2\left(-2\right),J_1\left(-2\right),J_2\left(-1+2i\right),J_2\left(-1-2i\right)\right\}.$$

To do this, we first compute the matrix of eigenvectors of $C_1:$

$$S=\left[\begin{array}{cccccccc}1& 0& 0& 1& 0& -1& 0& -1\\ 1& 0& 1& 0& 0& -i& 0& i\\ 1& 1& 0& 0& -1& 0& -1& 0\\ 1& -1& -1& -1& -i& 0& i& 0\\ 1& -1& -1& -1& i& 0& -i& 0\\ 1& 1& 0& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 0& i& 0& -i\\ 1& 0& 0& 1& 0& 1& 0& 1\end{array}\right].$$

Then for $E=E_{2,3}+E_{5,6}+E_{7,8},$ we have

$${\mathit{SES}}^{-1}=\left[\begin{array}{cccccccc}0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\\ \frac{3}{8}& \frac{3}{8}& -\frac{1}{8}& -\frac{1}{8}& -\frac{1}{8}& -\frac{1}{8}& \frac{3}{8}& -\frac{5}{8}\\ \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& -\frac{7}{8}& \frac{1}{8}\\ \frac{1}{8}& -\frac{7}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}& \frac{1}{8}\\ -\frac{5}{8}& \frac{3}{8}& -\frac{1}{8}& -\frac{1}{8}& -\frac{1}{8}& -\frac{1}{8}& \frac{3}{8}& \frac{3}{8}\\ 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0\end{array}\right]$$

and taking $\mathbf{q}=-\mathbf{d}$, where d is the vector of the diagonal entries of ${\mathit{SES}}^{-1}$ we obtain that ${\mathit{SES}}^{-1}+{\mathbf{eq}}^T$ has all its diagonal entries being zero. Thus,

$$C_2=C_1+\left({\mathit{SES}}^{-1}+{\mathbf{eq}}^T\right)=\left[\begin{array}{cccccccc}0& \frac{1}{2}& \frac{13}{8}& \frac{11}{8}& \frac{11}{8}& \frac{13}{8}& \frac{5}{2}& 1\\ \frac{5}{2}& 0& \frac{13}{8}& \frac{11}{8}& \frac{11}{8}& \frac{13}{8}& 1& \frac{1}{2}\\ \frac{15}{8}& \frac{15}{8}& 0& \frac{1}{4}& \frac{9}{4}& 1& \frac{15}{8}& \frac{7}{8}\\ \frac{13}{8}& \frac{13}{8}& \frac{11}{4}& 0& 1& \frac{3}{4}& \frac{5}{8}& \frac{13}{8}\\ \frac{13}{8}& \frac{5}{8}& \frac{3}{4}& 1& 0& \frac{11}{4}& \frac{13}{8}& \frac{13}{8}\\ \frac{7}{8}& \frac{15}{8}& 1& \frac{9}{4}& \frac{1}{4}& 0& \frac{15}{8}& \frac{15}{8}\\ \frac{1}{2}& 1& \frac{13}{8}& \frac{11}{8}& \frac{11}{8}& \frac{13}{8}& 0& \frac{5}{2}\\ 1& \frac{5}{2}& \frac{13}{8}& \frac{11}{8}& \frac{11}{8}& \frac{13}{8}& \frac{1}{2}& 0\end{array}\right]$$

is nonnegative centrosymmetric with spectrum Λ and with the desired JCF $J\left(C_2\right).$ Applying the same procedure, changing the matrix E, say by, $E_1=E_{2,3}$, $E_2=E_{2,3}+E_{3,4}$, $E_3=E_{2,3}+E_{3,4}+E_{5,6}+E_{7,8}$, $E_4=E_{5,6}+E_{7,8}$, we may construct a nonnegative centrosymmetric matrix with spectrum Λ, for each one of the other four JCF allowed by Λ.

Theorems 4.3 and 4.4 allow us to show that certain real spectra of nonnegative numbers and of the Suleĭmanova type are centrosymmetrically $\mathcal{UR}$ (Corollaries 4.1 and 4.2 below).

In Ref. [7], Perfect introduces the n×n (matrix)

$$P=\left[\begin{array}{ccccc}1& 1& \cdots & 1& 1\\ 1& 1& \cdots & 1& -1\\ 1& 1& \cdots & -1& 0\\ ⋮& ⋮& \cdots & ⋮& ⋮\\ 1& -1& \cdots & 0& 0\end{array}\right]$$E4

and she proves that if $D=\mathit{diag}\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\}$ with ${\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0,$ then ${\mathit{PDP}}^{-1}$ is a positive matrix in ${\mathcal{CS}}_{{\lambda }_1}$.

Corollary 4.1 [25] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a list of nonnegative real numbers with ${\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0$. If ${\lambda }_m>{\lambda }_{m+1}$ when $n=2m$ and ${\lambda }_{m+1}>{\lambda }_{m+2}$ when $n=2m+1$, then Λ is centrosymmetrically UR.

Proof: For $n=2m$, we define the m×m diagonalizable positive matrix with spectrum ${\mathrm{\Lambda }}_1=\left\{{\lambda }_1,\dots ,{\lambda }_m\right\}$ as $W_1={\mathit{PDP}}^{-1}$, where $D=\mathit{diag}\left\{{\lambda }_1,\dots ,{\lambda }_m\right\}$ and P is the matrix in (4). Let $W_2=\mathit{diag}\left\{{\lambda }_{m+1},\dots ,{\lambda }_n\right\}$ with spectrum ${\mathrm{\Lambda }}_2$. Note that $\mathrm{\Lambda }={\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2$ and since ${\lambda }_m>{\lambda }_{m+1}$, ${\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2=\varnothing$. Moreover, it is clear that $W_1+W_2$ is ODP. On the other hand, in [Julio et al. [26], Theorem 3.2], it was proved that if $d_{\mathit{jj}}$, $j=1,2,\dots ,m,$ are the diagonal entries of ${\mathit{PDP}}^{-1},$ then $d_{\mathit{jj}}>{\lambda }_{m+j}$, for all $j=1,2,\dots ,m.$ Thus, $W_1-W_2$ is positive. Then, from Theorem 4.3, Λ is centrosymmetrically $\mathcal{UR}$.

For $n=2m+1$, we define the $\left(m+1\right)\times \left(m+1\right)$ diagonalizable positive matrix with spectrum ${\mathrm{\Lambda }}_1=\left\{{\lambda }_1,\dots ,{\lambda }_{m+1}\right\}$ as ${\mathit{PDP}}^{-1}=\left[\begin{array}{cc}{W}_1& \mathbf{a}\\ {\mathbf{b}}^T& c\end{array}\right]$, where $D=\mathit{diag}\left\{{\lambda }_1,\dots ,{\lambda }_{m+1}\right\}$ and P is the $\left(m+1\right)\times \left(m+1\right)$ matrix in (4). Let $W_2=\mathit{diag}\left\{{\lambda }_{m+2},\dots ,{\lambda }_n\right\}$ with spectrum ${\mathrm{\Lambda }}_2$. Again $\mathrm{\Lambda }={\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2$, ${\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2=\varnothing$, $W_1+W_2$ is ODP and $W_1-W_2$ is positive. Then, from Theorem 4.4, Λ is centrosymmetrically $\mathcal{UR}$.

Corollary 4.2 [25] Let $\mathrm{\Lambda }=\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ be a realizable list of real numbers with ${\lambda }_1>0>{\lambda }_2\ge \cdots \ge {\lambda }_n$. If ${\lambda }_m>{\lambda }_{m+1}$ when $n=2m$ and ${\lambda }_{m+1}>{\lambda }_{m+2}$ when $n=2m+1$, then Λ is centrosymmetrically $\mathcal{UR}$.

Proof: We assume without loss of generality that $\sum _{i=1}^n{\lambda }_i=0$. For $n=2m$ we define

$$\begin{array}{c}{W}_1=\left[\begin{array}{cccc}{\lambda }_1& & & \\ {\lambda }_1-{\lambda }_2& {\lambda }_2& & \\ ⋮& ⋮& \ddots & \\ {\lambda }_1-{\lambda }_m& 0& \cdots & {\lambda }_m\end{array}\right]+{\mathbf{eq}}^T\\ =\left[\begin{array}{cccc}-{\lambda }_{m+1}& -{\lambda }_{m+2}-{\lambda }_2& \cdots & -{\lambda }_n-{\lambda }_m\\ -{\lambda }_{m+1}-{\lambda }_2& -{\lambda }_{m+2}& \cdots & -{\lambda }_n-{\lambda }_m\\ ⋮& ⋮& \ddots & ⋮\\ -{\lambda }_{m+1}-{\lambda }_m& -{\lambda }_{m+2}-{\lambda }_2& \cdots & -{\lambda }_n\end{array}\right],\end{array}$$

where ${\mathbf{q}}^T=\left[-{\lambda }_{m+1}-{\lambda }_1,-{\lambda }_{m+2}-{\lambda }_2,\cdots ,-{\lambda }_n-{\lambda }_m\right].$ Note that $W_1$ is an m×m diagonalizable positive matrix with spectrum ${\mathrm{\Lambda }}_1=\left\{{\lambda }_1,\dots ,{\lambda }_m\right\}$. Let $W_2=\mathit{diag}\left\{{\lambda }_{m+1},\dots ,{\lambda }_n\right\}$ with spectrum Λ₂. It is clear that $\mathrm{\Lambda }={\mathrm{\Lambda }}_1\cup {\mathrm{\Lambda }}_2$ and since ${\lambda }_m>{\lambda }_{m+1}$, ${\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2=\varnothing$. Moreover,

$$W_1+W_2=\left[\begin{array}{cccc}0& -{\lambda }_{m+2}-{\lambda }_2& \cdots & -{\lambda }_n-{\lambda }_m\\ -{\lambda }_{m+1}-{\lambda }_2& 0& \cdots & -{\lambda }_n-{\lambda }_m\\ ⋮& ⋮& \ddots & ⋮\\ -{\lambda }_{m+1}-{\lambda }_m& -{\lambda }_{m+2}-{\lambda }_2& \cdots & 0\end{array}\right]$$

is ODP and

$$W_1-W_2=\left[\begin{array}{cccc}-2{\lambda }_{m+1}& -{\lambda }_{m+2}-{\lambda }_2& \cdots & -{\lambda }_n-{\lambda }_m\\ -{\lambda }_{m+1}-{\lambda }_2& -2{\lambda }_{m+2}& \cdots & -{\lambda }_n-{\lambda }_m\\ ⋮& ⋮& \ddots & ⋮\\ -{\lambda }_{m+1}-{\lambda }_m& -{\lambda }_{m+2}-{\lambda }_2& \cdots & -2{\lambda }_n\end{array}\right]$$

is positive. Then, from Theorem 4.3, Λ is centrosymmetrically $\mathcal{UR}$.

For $n=2m+1$ we define the $\left(m+1\right)\times \left(m+1\right)$ diagonalizable nonnegative matrix with spectrum ${\mathrm{\Lambda }}_1=\left\{{\lambda }_1,\dots ,{\lambda }_{m+1}\right\}$ as

$$\begin{array}{c}\left[\begin{array}{cc}{W}_1& \mathbf{a}\\ {\mathbf{b}}^T& c\end{array}\right]=\left[\begin{array}{ccccc}{\lambda }_1& & & & \\ {\lambda }_1-{\lambda }_2& {\lambda }_2& & & \\ ⋮& ⋮& \ddots & & \\ {\lambda }_1-{\lambda }_m& 0& \cdots & {\lambda }_m& \\ {\lambda }_1-{\lambda }_{m+1}& 0& \cdots & 0& {\lambda }_{m+1}\end{array}\right]+{\mathbf{eq}}^T\\ =\left[\begin{array}{ccccc}-{\lambda }_{m+2}& -{\lambda }_{m+3}-{\lambda }_2& \cdots & -{\lambda }_n-{\lambda }_m& -{\lambda }_{m+1}\\ -{\lambda }_{m+2}-{\lambda }_2& -{\lambda }_{m+3}& \cdots & -{\lambda }_n-{\lambda }_m& -{\lambda }_{m+1}\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ -{\lambda }_{m+2}-{\lambda }_m& -{\lambda }_{m+3}-{\lambda }_2& \cdots & -{\lambda }_n& -{\lambda }_{m+1}\\ -{\lambda }_{m+2}-{\lambda }_{m+1}& -{\lambda }_{m+3}-{\lambda }_2& \cdots & -{\lambda }_n-{\lambda }_m& 0\end{array}\right],\end{array}$$

where ${\mathbf{q}}^T=\left[-{\lambda }_{m+2}-{\lambda }_1,-{\lambda }_{m+3}-{\lambda }_2,\cdots ,-{\lambda }_n-{\lambda }_m,-{\lambda }_{m+1}\right]$.

Let $W_2=\mathit{diag}\left\{{\lambda }_{m+2},\dots ,{\lambda }_n\right\}$ with spectrum ${\mathrm{\Lambda }}_2$. Then from Theorem 4.4, the result follows.

4.3 The URP for M-matrices

M-matrices appear in many applications in the physical, biological and social sciences. A real matrix A is said to be an M-matrix if it is of the form $A=\mathit{\alpha I}-B,$ where B is a nonnegative matrix and Although M-matrices are not nonnegative, they are related to nonnegative matrices. For instance, it is well known that the inverse of a nonsingular M-matrix is nonnegative. Moreover, the problem of finding an M-matrix $A=\mathit{\alpha I}-B$ with prescribed complex spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\}$ can be seen as the problem of finding a nonnegative matrix B with eigenvalues $\alpha -{\lambda }_1,\alpha -{\lambda }_2,\dots ,\alpha -{\lambda }_n.$ In Soto et al. [27], the authors study the URP for M-matrices. More precisely, they give sufficient conditions for the existence of M-matrices with prescribed elementary divisors. In particular, they solve the URP for certain lists of real numbers and for lists of complex numbers of the form $\mathrm{\Lambda }=\left\{{\lambda }_1,a\pm \mathit{bi},\dots ,a\pm \mathit{bi}\right\}.$ In Soto et al. [27], the inverse M-matrix problem for symmetric generalized doubly stochastic M-matrices is also considered.

Proposition 4.1 Let $A=\mathit{\alpha I}-B$ be an n×n M-matrix. Then.

1. $B\in {\mathcal{CS}}_{{\lambda }_1}$ if and only if $A\in {\mathcal{CS}}_{\alpha -{\lambda }_1}$.

2. $B,B^T\in {\mathcal{CS}}_{{\lambda }_1}$ if and only if $A,A^T\in {\mathcal{CS}}_{\alpha -{\lambda }_1}$.

3. B is normal if and only if A is normal.

4. B is symmetric if and only if A is symmetrix.

5. B is circulant if and only if A is circulant.

6. A and B have the same eigenvectors.

Next result is an M-matrix version of Brauer Theorem.

Theorem 4.5 Let $A=\left(\mathit{\alpha I}-B\right)\in {\mathcal{CS}}_{{\lambda }_1}$ be an M-matrix with spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\},$ ${\lambda }_1>\left|{\lambda }_i\right|,$ $i=2,\dots ,n.$ Let B be with a positive column. Then $A+{\mathbf{eq}}^T$ is also an M-matrix with the same spectrum and with elementary divisors as A.

Proof: $A+{\mathbf{eq}}^T=\mathit{\alpha I}-B+{\mathbf{eq}}^T=\mathit{\alpha I}-\left(B-{\mathbf{eq}}^T\right).$ As B is nonnegative with its kth column being positive, then by taking $\mathbf{q}=\left[q_i\right],$ $q_i\le 0,$ $i\ne k,$ $q_k=-\sum _{i\ne k}{q}_i\le \underset{1\le i\le n}{min}\left\{b_{\mathit{ik}}\right\},$ we have that $B-{\mathbf{eq}}^T$ is nonnegative and $\sum _{i=1}^n{q}_i=0.$ Thus, from Theorem 1.4, $A+{\mathbf{eq}}^T$ is also an M-matrix with the same spectrum and with elementary divisors as A.

Theorem 4.6 Let $A=\mathit{\alpha I}-B$ be a diagonalizable M-matrix with spectrum $\mathrm{\Lambda }=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\},$ where B is positive. Then there is an M-matrix with spectrum Λ for each JCF allowed by Λ.

Proof: Since A is diagonalizable then $B=\left(b_{\mathit{ij}}\right)$ is diagonalizable and positive. Then there is a positive matrix $B^{\text{'}}$ with same spectrum as B for each JCF allowed by the spectrum of B. Hence, $A^{\text{'}}=\mathit{\alpha I}-B^{\text{'}}$ is an M-matrix with same spectrum as $A$ for each JCF allowed by Λ.

Theorem 4.7 Let $\mathrm{\Lambda }=\left\{{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n\right\}$ be with ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_{n-1}>{\lambda }_n\ge 0.$ Then there exists a generalized stochastic M-matrix $A\in {\mathcal{CS}}_{{\lambda }_n}$ with spectrum Λ for each JCF allowed by Λ.

Proof: Let $\alpha \ge {\lambda }_1.$ Consider the list

$${\mathrm{\Lambda }}^{\prime }=\left\{\alpha -{\lambda }_n,\alpha -{\lambda }_{n-1},\dots ,\alpha -{\lambda }_2,\alpha -{\lambda }_1\right\}.$$

Let $D=\mathit{diag}\left\{\alpha -{\lambda }_n,\alpha -{\lambda }_{n-1},\dots ,\alpha -{\lambda }_1\right\}$ and let P the Perfect matrix in (4). Then $B={\mathit{PDP}}^{-1}\in {\mathcal{CS}}_{\alpha -{\lambda }_n}$ is positive with spectrum ${\mathrm{\Lambda }}^{\text{'}}$ and diagonal JCF. Let $D+E,$ with E the matrix defined in the Introduction, the desired JCF. Then we have

$$D+E=P^{-1}\mathit{BP}+E=P^{-1}\left(B+{\mathit{PEP}}^{-1}\right)P.$$

It is clear that for $\epsilon >0$ small enough, $B+\epsilon {\mathit{PEP}}^{-1}$ is positive with JCF D+E Therefore, since $D+\mathit{\epsilon E}$ and D+E are similar (with the matrix $M=\mathit{diag}\left\{1,\epsilon ,{\epsilon }^2.\dots ,{\epsilon }^{n-1}\right\}$)$,$ $A=\mathit{\alpha I}-\left(B+\epsilon {\mathit{PEP}}^{-1}\right)$ is an M-matrix in ${\mathcal{CS}}_{{\lambda }_1}$ with the prescribed elementary divisors.

Theorem 4.8 Let $\mathrm{\Lambda }=\left\{{\lambda }_1,a\pm \mathit{bi},\dots ,a\pm \mathit{bi}\right\}$ be a list of n complex numbers with ${\lambda }_1\ge 0,$ $a\ge 0,$ $b>0.$ If

$${\lambda }_1\le a-\frac{n+1}{2}b,$$E5

then there exists an n×n M-matrix with spectrum Λ for each JCF allowed by Λ.

Proof: Let $\alpha \ge a.$ Consider the list

$${\mathrm{\Lambda }}^{\prime }=\left\{\alpha -{\lambda }_1,\left(\alpha -a\right)\pm \mathit{bi},\dots ,\left(\alpha -a\right)\pm \mathit{bi}\right\}$$

Since ${\lambda }_1\le a-\frac{n+1}{2}b,$ then $\alpha -{\lambda }_1\ge \alpha -a+\frac{n+1}{2}b.$ From [Arrieta et al. (21), Theorem 2.1], if (5) holds then there exists a nonnegative matrix $B\in {\mathcal{CS}}_{\alpha -{\lambda }_1}$ with spectrum ${\mathrm{\Lambda }}^{\text{'}}$ and the prescribed elementary divisors. Then $A=\mathit{\alpha I}-B$ is an M-matrix with spectrum Λ for each JCF allowed by Λ.

5. Conclusions

In this chapter, we revisit the problem of universal realizability of spectra [2], with new advances and results, which contain two important extensions of the Minc result [4] and new universal realizability criteria for general and structured matrices. Several open questions have been answered, while others remain open, such as under what conditions diagonalizably realizable implies universally realizable? Recent developments on this question are introduced in Soto and Marijuán [28].