Nonnegative Inverse Eigenvalue Problem

1. Introduction

Nonnegative matrices have long been a sorce of interesting and challenging mathematical problems. They are real matrices with all their entries being nonnegative and arise in a number of important application areas: communications systems, biological systems, economics, ecology, computer sciences, machine learning, and many other engineering systems. Inverse eigenvalue problems 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 [1]-[2].

The nonnegative inverse eigenvalue problem $($NIEP$)$ is the problem of characterizing those lists $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ of complex numbers which can be the spectra of $n\times n$ entrywise nonnegative matrices. If there exists a nonnegative matrix $A$ with spectrum $\Lambda$ we say that $\Lambda$ is realized by $A$ and that $A$ is the realizing matrix. A set $K$of conditions is said to be a realizability criterion if any list $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\},$ real or complex, satisfying conditions $K$ is realizable. The NIEP is an open problem. A full solution is unlikely in the near future. The problem has only been solved for $n=3$ by Loewy and London ([3], 1978) and for $n=4$ by Meehan ([4], 1998) and Torre-Mayo et al.([5], 2007). The case $n=5$ has been solved for matrices of trace zero in ([6], 1999). Other results, mostly in terms of sufficient conditions for the problem to have a solution (in the case of a complex list $\Lambda$), have been obtained, in chronological order, in [7]-[8].

Two main subproblems of the NIEP are of great interest: the real nonnegative inverse eigenvalue problem (RNIEP), in which $\Lambda$ is a list of real numbers, and the symmetric nonnegative inverse eigenvalue problem (SNIEP), in which the realizing matrix must be symmetric. Both problems, RNIEP and SNIEP are equivalent for $n\le 4$ (see [9]), but they are different otherwise (see [10]). Moreover, both problems remains unsolved for $n\ge 5.$ The NIEP is also of interest for nonnegative matrices with a particular structure, like stochastic and doubly stochastic, circulant, persymmetric, centrosymmetric, Hermitian, Toeplitz, etc.

The first sufficient conditions for the existence of a nonnegative matrix with a given real spectrum (RNIEP) were obtained by Suleimanova ([11], 1949) and Perfect ([12], [13], 1953 and 1955). Other sufficient conditions have also been obtained, in chronological order in [14]-[15], (see also [16], [17], and references therein for a comprehensive survey).

The first sufficient conditions for the SNIEP were obtained by Fiedler ([18], 1974). Other results for symmetric realizability have been obtained in [19], [7] and [20]-[21]. Recently, new sufficient conditions for the SNIEP have been given in [22]-[23].

1.1. Necessary conditions

Let $A$ be a nonnegative matrix with spectrum $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}.$ Then, from the Perron Frobenius theory we have the following basic necessary conditions

$$\begin{array}{cc}\left(1\right)& \overline{\Lambda }=\{\overline{{\lambda }_1},...,\overline{{\lambda }_n}\}=\Lambda \\ \left(2\right)& \underset{j}{max}\left\{\left|{\lambda }_j\right|\right\}\in \Lambda \\ \left(3\right)& s_m\left(\Lambda \right)=\sum _{j=1}^n{\lambda }_j^m\ge 0,m=1,2,...,\end{array}$$uid2

where $\overline{\Lambda }=\Lambda$ means that $\Lambda$ is closed under complex comjugation.

Moreover, we have

$$\begin{array}{cc}\left(4\right)& {\left(s_k\left(\Lambda \right)\right)}^m\le n^{m-1}{s}_{km}\left(\Lambda \right),k,m=1,2,...\\ \left(5\right)& {\left(s_2\left(\Lambda \right)\right)}^2\le (n-1)s_4\left(\Lambda \right),n\text{odd,}tr\left(A\right)=0.\end{array}$$uid3

Necessary condition $\left(4\right)$ is due to Loewy and London [3]. Necessary condition $\left(5\right),$ which is a refinement of $\left(4\right),$ is due to Laffey and Meehan [24]. The list $\Lambda =\{5,4,-3,-3,-3\}$ for instance, satisfies all above necessary conditions, except condition $\left(5\right).$ Therefore $\Lambda$ is not a realizable list. In [25] it was obtained a new necessary condition, which is independent of the previous ones. This result is based on the Newton's inequalities associated to the normalized coefficients of the characteristic polynomial of an M-matrix or an inverse M-matrix.

The chapter is organized as follows: In section 2 we introduce two important matrix results, due to Brauer and Rado, which have allowed to obtain many of the most general sufficient conditions for the RNIEP, the SNIEP and the complex case. In section 3 we consider the real case and we introduce, without proof (we indicate where the the proofs can be found), two sufficient conditions with illustrative examples. We consider, in section 4, the symmetric case. Here we introduce a symmetric version of the Rado result, Theorem ▭, and we set, without proof (see the appropriate references), three sufficient conditions, which are, as far as we know, the most general sufficient conditions for the SNIEP. In section $5,$ we discuss the complex (non real) case. Here we present several results with illustrative examples. Section 6 is devoted to discuss some Fiedler results and Guo results, which are very related with the problem and have been employed with success to derive sufficient conditions. Finally, in section 7, we introduce some open questions.

2. Brauer and Rado Theorems

A real matrix $A={\left(a_{ij}\right)}_{i=1}^n$ is said to have constant row sums if all its rows sum up to the same constant, say, $\alpha ,$ that is, ${}_{j=1}^n{a}_{ij}=\alpha ,$ $i=1,...,n.$ The set of all real matrices with constant row sums equal to $\alpha$ is denoted by ${\mathrm{𝒞𝒮}}_{\alpha }.$ It is clear that any matrix in ${\mathrm{𝒞𝒮}}_{\alpha }$ has eigenvector $𝐞={(1,1,...,1)}^T$ corresponding to the eigenvalue $\alpha .$ Denote by ${𝐞}_k$ the $n-$dimensional vector with one in the $k-th$ position and zeros elsewhere.

It is well known that the problem of finding a nonnegative matrix with spectrum $\Lambda =\{{\lambda }_1,...,{\lambda }_n\}$ is equivalent to the problem of finding a nonnegative matrix in ${\mathrm{𝒞𝒮}}_{{\lambda }_1}$ with spectrum $\Lambda$ (see [26]). This will allow us to exploit the advantages of two important theorems, Brauer Theorem and Rado Theorem, which will be introduced in this section.

The spectra of circulant nonnegative matrices have been characterized in [27], while in [28], a simple complex generalization of Suleimanova result has been proved, and efficient and general sufficient conditions for the realizability of partitioned spectra, with the partition allowing some of its pieces to be nonrealizable, provided there are other pieces, which are realizable and, in certain way, compensate the nonnrealizability of the former, have been obtained. This is the procedure which we call negativity compensation. This strategy, based in the use of the following two perturbation results, together with the properties of real matrices with constant row sums, has proved to be successful.

Theorem 1 Brauer [29] Let $A$ be an $n\times n$ arbitrary matrix with eigenvalues ${\lambda }_1,...,{\lambda }_n.$ Let $𝐯={(v_1,...,v_n)}^T$ an eigenvector of $A$ associated with the eigenvalue ${\lambda }_k$ and let $𝐪={(q_1,...,q_n)}^T$ be any $n$-dimensional vector. Then the matrix $A+{\mathrm{𝐯𝐪}}^T$ has eigenvalues ${\lambda }_1,...,{\lambda }_{k-1},{\lambda }_k+v^{T}q,{\lambda }_{k+1},...,{\lambda }_n.$

Let $U$ be an $n\times n$ nonsingular matrix such that

$$U^{-1}AU=\left[\begin{array}{cccc}{\lambda }_1& *& \cdots & *\\ & {\lambda }_2& \ddots & ⋮\\ & & \ddots & *\\ & & & {\lambda }_n\end{array}\right]$$

is an upper triangular matrix, where we choose the first column of $U$ as $𝐯$ ($U$ there exists from a well known result of Schur). Then,

$$\begin{array}{c}\hfill U^{-1}(A+{\mathrm{𝐯𝐪}}^T)U=U^{-1}AU+\left[\begin{array}{cccc}{q}_1& q_2& \cdots & q_n\\ & & & \\ & & & \\ & & \end{array}\right]U=\left[\begin{array}{cccc}{\lambda }_1+{𝐪}^T𝐯& *& \cdots & *\\ & {\lambda }_2& \ddots & ⋮\\ & & \ddots & *\\ & & & {\lambda }_n\end{array}\right].\end{array}$$

and the result follows.

This proof is due to Reams [30].

Theorem 2 Rado [13] Let $A$ be an $n\times n$ arbitrary matrix with eigenvalues ${\lambda }_1,...,{\lambda }_n$ and let $\Omega =diag\{{\lambda }_1,...,{\lambda }_r\}$ for some $r\le n.$ Let $X$ be an $n\times r$ matrix with rank $r$ such that its columns $x_1,x_2,...,x_r$ satisfy $A{x}_i={\lambda }_i{x}_i,$ $i=1,...,r.$ Let $C$ be an $r\times n$ arbitrary matrix. Then the matrix $A+XC$ has eigenvalues ${\mu }_1,...,{\mu }_r,{\lambda }_{r+1},...,{\lambda }_n,$ where ${\mu }_1,...,{\mu }_r$ are eigenvalues of the matrix $\Omega +CX.$

Let $S=\left[X\mid Y\right]$ a nonsingular matrix with $S^{-1}=\left[\right]UV.$ Then $UX=I_r,$ $VY=I_{n-r}$ and $VX=0,$ $UY=0.$ Let $C=\left[C_1\mid C_2\right],$ $X=\left[\right]X_1{X}_2,$ $Y=\left[\right]Y_1{Y}_2.$ Then, since $AX=X\Omega ,$

$$S^{-1}AS=\left[\right]UV\left[X\Omega \mid AY\right]=\left[\begin{array}{cc}\Omega & UAY\\ 0& VAY\end{array}\right]$$

and

$$S^{-1}XCS=\left[\right]I_{r}0\left[C_1\mid C_2\right]S=\left[\begin{array}{cc}{C}_1& C_2\\ 0& 0\end{array}\right]\left[\begin{array}{cc}{X}_1& Y_1\\ X_2& Y_2\end{array}\right]=\left[\begin{array}{cc}CX& CY\\ 0& 0\end{array}\right].$$

Thus,

$$S^{-1}(A+XC)S=S^{-1}AS+S^{-1}XCS=\left[\begin{array}{cc}\Omega +CX& UAY+CY\\ 0& VAY\end{array}\right],$$

and we have $\sigma (A+XC)=\sigma (\Omega +CX)+\sigma \left(A\right)-\sigma \left(\Omega \right).$

3. Real nonnegative inverse eigenvalue problem.

Regarding the RNIEP, by applying Brauer Theorem and Rado Theorem, efficient and general sufficient conditions have been obtained in [13], [31], [32], [33].

Theorem 3 [32] Let $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ be a given list of real numbers. Suppose that:

$i)$ There exists a partition $\Lambda ={\Lambda }_1\cup ...\cup {\Lambda }_t,$ where

$${\Lambda }_k=\{{\lambda }_{k1},{\lambda }_{k2},...{\lambda }_{k{p}_k}\},{\lambda }_{11}={\lambda }_1,{\lambda }_{k1}\ge \cdots \ge {\lambda }_{k{p}_k},{\lambda }_{k1}\ge 0,$$

$k=1,...,t,$ such that for each sublist ${\Lambda }_k$ we associate a corresponding list

$${\Gamma }_k=\{{\omega }_k,{\lambda }_{k2},...,{\lambda }_{k{p}_k}\},0\le {\omega }_k\le {\lambda }_1,$$

which is realizable by a nonnegative matrix $A_k\in C{S}_{{\omega }_k}$ of order $p_k.$

$ii)$ There exists a nonnegative matrix $B\in C{S}_{{\lambda }_1}$ with eigenvalues ${\lambda }_1,{\lambda }_{21},...,{\lambda }_{t1}$ (the first elements of the lists ${\Lambda }_k$) and diagonal entries ${\omega }_1,{\omega }_2,...,{\omega }_t$ (the first elements of the lists ${\Gamma }_k$).

Then $\Lambda$ is realizable by a nonnegative matrix $A\in C{S}_{{\lambda }_1}.$

Perfect [13] gave conditions under which ${\lambda }_1,{\lambda }_2,...,{\lambda }_t$ and ${\omega }_1,{\omega }_2,...,{\omega }_t$ are the eigenvalues and the diagonal entries, respectively, of a $t\times t$ nonnegative matrix $B\in C{S}_{{\lambda }_1}.$ For $t=2$ it is necessary and sufficient that ${\lambda }_1+{\lambda }_2={\omega }_1+{\omega }_2,$ with $0\le {\omega }_i\le {\lambda }_1.$ For $t=3$ Perfect gave the following result:

Theorem 4 [13] The real numbers ${\lambda }_1,{\lambda }_2,{\lambda }_3$ and ${\omega }_1,{\omega }_2,{\omega }_3$ are the eigenvalues and the diagonal entries, respectively, of a $3\times 3$ nonnegative matrix $B\in C{S}_{{\lambda }_1},$ if and only if:

$$\begin{array}{cc}i)& 0\le {\omega }_i\le {\lambda }_1,i=1,2,3\\ ii)& {\lambda }_1+{\lambda }_2+{\lambda }_3={\omega }_1+{\omega }_2+{\omega }_3\\ iii)& {\lambda }_1{\lambda }_2+{\lambda }_1{\lambda }_3+{\lambda }_2{\lambda }_3\le {\omega }_1{\omega }_2+{\omega }_1{\omega }_3+{\omega }_2{\omega }_3\\ iv)& ma{x}_k{\omega }_k\ge {\lambda }_2\end{array}$$uid8

Then, an appropriate $3\times 3$ nonnegative matrix $B$ is

$$B=\left[\begin{array}{ccc}{\omega }_1& 0& {\lambda }_1-{\omega }_1\\ {\lambda }_1-{\omega }_2-p& {\omega }_2& p\\ 0& {\lambda }_1-{\omega }_3& {\omega }_3\end{array}\right],$$uid9

where

$$p=\frac{1}{{\lambda }_1-{\omega }_3}({\omega }_1{\omega }_2+{\omega }_1{\omega }_3+{\omega }_2{\omega }_3-{\lambda }_1{\lambda }_2+{\lambda }_1{\lambda }_3+{\lambda }_2{\lambda }_3).$$

For $t\ge 4,$ we only have a sufficient condition:

$$\begin{array}{cc}i)& 0\le {\omega }_k\le {\lambda }_1,k=1,2,...t,\\ ii)& {\omega }_1+{\omega }_2\cdots +{\omega }_t={\lambda }_1+{\lambda }_2\cdots +{\lambda }_t,\\ iii)& {\omega }_k\ge {\lambda }_k,{\omega }_1\ge {\lambda }_k,k=2,3,...,t,\end{array}$$uid10

with the following matrix $B\in C{S}_{{\lambda }_1}$ having eigenvalues and diagonal entries ${\lambda }_1,{\lambda }_2,...,{\lambda }_t$ and ${\omega }_1,{\omega }_2,...,{\omega }_t,$ respectively:

$$B=\left[\begin{array}{cccc}{\omega }_1& {\omega }_2-{\lambda }_2& \cdots & {\omega }_r-{\lambda }_t\\ {\omega }_1-{\lambda }_2& {\omega }_2& \cdots & {\omega }_r-{\lambda }_t\\ ⋮& ⋮& \ddots & ⋮\\ {\omega }_1-{\lambda }_t& {\omega }_2-{\lambda }_2& \cdots & {\omega }_t\end{array}\right].$$uid11

Example 1 Let us consider the list $\Lambda =\{6,1,1,-4,-4\}$ with the partition

$${\Lambda }_1=\{6,-4\},{\Lambda }_2=\{1,-4\},{\Lambda }_3=\left\{1\right\}$$

and the realizable associated lists

$${\Gamma }_1=\{4,-4\},{\Gamma }_2=\{4,-4\},{\Gamma }_3=\left\{0\right\}.$$

From (▭) we compute the $3\times 3$ nonnegative matrix

$$B=\left[\begin{array}{ccc}4& 0& 2\\ \frac{3}{2}& 4& \frac{1}{2}\\ 0& 6& 0\end{array}\right]$$

with eigenvalues $6,1,1,$ and diagonal entries $4,4,0.$ Then

$$\begin{array}{ccc}\hfill A& =& \left[\begin{array}{ccccc}0& 4& 0& 0& 0\\ 4& 0& 0& 0& 0\\ 0& 0& 0& 4& 0\\ 0& 0& 4& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]+\left[\begin{array}{ccc}1& 0& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccccc}0& 0& 0& 0& 2\\ \frac{3}{2}& 0& 0& 0& \frac{1}{2}\\ 0& 0& 6& 0& 0\end{array}\right]\hfill \\ & =& \left[\begin{array}{ccccc}0& 4& 0& 0& 2\\ 4& 0& 0& 0& 2\\ \frac{3}{2}& 0& 0& 4& \frac{1}{2}\\ \frac{3}{2}& 0& 4& 0& \frac{1}{2}\\ 0& 0& 6& 0& 0\end{array}\right]\hfill \end{array}$$

is nonnegative with spectrum $\Lambda .$

A map of sufficient conditions for the RNIEP it was constructed in [17], There, the sufficient conditions were compared to establish inclusion or independence relations between them. It is also shown in [17] that the criterion given by Theorem ▭ contains all realizability criteria for lists of real numbers studied therein. In [33], from a new special partition, Theorem ▭ is extended. Now, the first element ${\lambda }_{k1}$ of the sublist ${\Lambda }_k$ need not to be nonnegative and the realizable auxiliar list ${\Gamma }_k=\{{\omega }_k,{\lambda }_{k1},...,{\lambda }_{k{p}_k}\}$ contains one more element. Moreover, the number of lists of the partition depend on the number of elements of the first list ${\Lambda }_1,$ and some lists ${\Lambda }_k$ can be empty.

Theorem 5 [33] Let $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ be a list of real numbers and let the partition $\Lambda ={\Lambda }_1\cup \cdots \cup {\Lambda }_{p_1+1}$ be such that

$${\Lambda }_k=\{{\lambda }_{k1},{\lambda }_{k2},...{\lambda }_{k{p}_k}\},{\lambda }_{11}={\lambda }_1,{\lambda }_{k1}\ge {\lambda }_{k2}\ge \cdots \ge {\lambda }_{k{p}_k},$$

$k=1,...,p_1+1,$ where $p_1$ is the number of elements of the list ${\Lambda }_1$ and some of the lists ${\Lambda }_k$ can be empty. Let ${\omega }_2,...,{\omega }_{p_1+1}$ be real numbers satisfying $0\le {\omega }_k\le {\lambda }_1,$ $k=2,...,p_1+1.$ Suppose that the following conditions hold:

$i)$ For each $k=2,...,p_1+1,$ there exists a nonnegative matrix $A_k\in C{S}_{{\omega }_k}$ with spectrum ${\Gamma }_k=\{{\omega }_k,{\lambda }_{k1},...,{\lambda }_{k{p}_k}\},$

$ii)$ There exists a $p_1\times p_1$ nonnegative matrix $B\in C{S}_{{\lambda }_1,}$ with spectrum ${\Lambda }_1$ and with diagonal entries ${\omega }_2,...,{\omega }_{p_1+1}.$

Then $\Lambda$ is realizable by a nonnegative matrix $A\in C{S}_{{\lambda }_1}.$

Example 2 With this extension, the authors show for instance, that the list

$$\{5,4,0,-3,-3,-3\}$$

is realizable, which can not be done from the criterion given by Theorem ▭. In fact, let the partition

$$\begin{array}{ccc}\hfill {\Lambda }_1& =& \{5,4,0,-3\},{\Lambda }_2=\{-3\},{\Lambda }_3=\{-3\}\text{with}\hfill \\ \hfill {\Gamma }_2& =& \{3,-3\},{\Gamma }_3=\{3,-3\},{\Gamma }_4={\Gamma }_5=\left\{0\right\}.\hfill \end{array}$$

The nonnegative matrix

$$B=\left[\begin{array}{cccc}3& 0& 2& 0\\ 0& 3& 0& 2\\ 3& 0& 0& 2\\ 0& 3& 2& 0\end{array}\right]$$

has spectrum ${\Lambda }_1$ and diagonal entries $3,3,0,0.$ It is clear that

$$A_2=A_3=\left[\begin{array}{cc}0& 3\\ 3& 0\end{array}\right]\text{realizes}{\Gamma }_2={\Gamma }_3.$$

Then

$$\begin{array}{c}\hfill A=\left[\begin{array}{cccc}{A}_2& & & \\ & A_3& & \\ & & 0& \\ & & & 0\end{array}\right]+\left[\begin{array}{cccc}1& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right]\left[\begin{array}{cccccc}0& 0& 0& 0& 2& 0\\ 0& 0& 0& 0& 0& 2\\ 3& 0& 0& 0& 0& 2\\ 0& 0& 3& 0& 2& 0\end{array}\right]=\left[\begin{array}{cccccc}0& 3& 0& 0& 2& 0\\ 3& 0& 0& 0& 2& 0\\ 0& 0& 0& 3& 0& 2\\ 0& 0& 3& 0& 0& 2\\ 3& 0& 0& 0& 0& 2\\ 0& 0& 3& 0& 2& 0\end{array}\right]\end{array}$$

has the desired spectrum $\{5,4,0,-3,-3,-3\}.$

4. Symmetric nonnegative inverse eigenvalue problem

Several realizability criteria which were first obtained for the RNIEP have later been shown to be symmetric realizability criteria as well. For example, Kellogg criterion [14] was showed by Fiedler [18] to imply symmetric realizability. It was proved by Radwan [7] that Borobia's criterion [34] is also a symmetric realizability criterion, and it was proved in [21] that Soto's criterion for the RNIEP is also a criterion for the SNIEP. In this section we shall consider the most general and efficient symmetric realizability criteria for the SNIEP (as far as we know they are). We start by introducing a symmetric version of the Rado Theorem:.

Theorem 6 [22] Let $A$ be an $n\times n$ symmetric matrix with spectrum $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ and for some $r\le n,$ let $\{{𝐱}_1,{𝐱}_2,...,{𝐱}_r\}$ be an orthonormal set of eigenvectors of $A$ spanning the invariant subspace associated with ${\lambda }_1,{\lambda }_2,...,{\lambda }_r.$ Let $X$ be the $n\times r$ matrix with $i-th$ column ${𝐱}_i,$ let $\Omega =diag\{{\lambda }_1,...,{\lambda }_r\},$ and let $C$ be any $r\times r$ symmetric matrix. Then the symmetric matrix $A+XC{X}^T$ has eigenvalues ${\mu }_1,{\mu }_2,...,{\mu }_r,{\lambda }_{r+1},...,{\lambda }_n,$ where ${\mu }_1,{\mu }_2,...,{\mu }_r$ are the eigenvalues of the matrix $\Omega +C.$

Since the columns of $X$ are an orthonormal set, we may complete $X$ to an orthogonal matrix $W=[X$ $Y],$ that is, $X^{T}X=I_r,$ $Y^{T}Y=I_{n-r},$ $X^{T}Y=0,$ $Y^{T}X=0.$ Then

$$\begin{array}{ccc}\hfill W^{-1}AW& =& \left[\right]X^T{Y}^{T}A\left[XY\right]=\left[\begin{array}{cc}\Omega & X^{T}AY\\ 0& Y^{T}AY\end{array}\right]\hfill \\ & & \\ \hfill W^{-1}\left(XC{X}^T\right)W& =& \left[\right]I_{r}0C\left[I_{r}0\right]=\left[\begin{array}{cc}C& 0\\ 0& 0\end{array}\right].\hfill \end{array}$$

Therefore,

$$W^{-1}(A+XC{X}^T)W=\left[\begin{array}{cc}\Omega +C& X^{T}AY\\ 0& Y^{T}AY\end{array}\right]$$

and $A+XC{X}^T$ is symmetric with eigenvalues ${\mu }_1,...,{\mu }_r,{\lambda }_{r+1},...,{\lambda }_n.$

By using Theorem ▭, the following sufficient condition was proved in [22]:

Theorem 7 [22] Let $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ be a list of real numbers with ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ and, for some $t\le n,$ let ${\omega }_1,...,{\omega }_t$ be real numbers satisfying $0\le {\omega }_k\le {\lambda }_1,$ $k=1,...,t.$ Suppose there exists:

$i)$ a partition $\Lambda ={\Lambda }_1\cup \cdots \cup {\Lambda }_t$ with

$${\Lambda }_k=\{{\lambda }_{k1},{\lambda }_{k2},...{\lambda }_{k{p}_k}\},{\lambda }_{11}={\lambda }_1,{\lambda }_{k1}\ge 0,{\lambda }_{k1}\ge {\lambda }_{k2}\ge \cdots \ge {\lambda }_{k{p}_k},$$

such that for each $k=1,...,t,$ the list ${\Gamma }_k=\{{\omega }_k,{\lambda }_{k2},...,{\lambda }_{k{p}_k}\}$ is realizable by a symmetric nonnegative matrix $A_k$ of order $p_k,$ and

$ii)$ a $t\times t$ symmetric nonnegative matrix $B$ with eigenvalues ${\lambda }_{11},{\lambda }_{21},...,{\lambda }_{t1}\}$ and with diagonal entries ${\omega }_1,{\omega }_2,...,{\omega }_t.$

Then $\Lambda$ is realizable by a symmetric nonnegative matrix.

Since $A_k$ is a $p_k\times p_k$ symmetric nonnegative matrix realizing ${\Gamma }_k,$ then $A=diag\{A_1,A_2,...,A_t\}$ is symmetric nonnegative with spectrum ${\Gamma }_1\cup {\Gamma }_2\cup \cdots \cup {\Gamma }_t.$ Let $\{{𝐱}_1,...,{𝐱}_t\}$ be an orthonormal set of eigenvectors of $A$ associated with ${\omega }_1,...,{\omega }_t,$ respectively. Then the $n\times t$ matrix $X$ with $i-th$ column ${𝐱}_i$ satisfies $AX=X\Omega$ for $\Omega =dig\{{\omega }_1,...,{\omega }_t\}.$ Moreover, $X$ is entrywise nonnegative, since each ${𝐱}_i$ contains the Perron eigenvector of $A_i$ and zeros. Now, if we set $C=B-\Omega ,$ the matrix $C$ is symmetric nonnegative and $\Omega +C$ has eigenvalues ${\lambda }_1,...,{\lambda }_t.$ Therefore, by Theorem ▭ the symmetric matrix $A+XC{X}^T$ has spectrum $\Lambda .$ Besides, it is nonnegative since all the entries of $A,X,$ and $C$ are nonnegative.

Theorem ▭ not only ensures the existence of a realizing matrix, but it also allows to construct the realizing matrix. Of course, the key is to know under which conditions does there exists a $t\times t$ symmetrix nonnegative matrix $B$ with eigenvalues ${\lambda }_1,...,{\lambda }_t$ and diagonal entries ${\omega }_1,...,{\omega }_t.$

The following conditions for the existence of a real symmetric matrix, not necessarily nonnegative, with prescribed eigenvalues and diagonal entries are due to Horn [35]: There exists a real symmetric matrix with eigenvalues ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_t$ and diagonal entries ${\omega }_1\ge {\omega }_2\ge \cdots \ge {\omega }_t$ if and only if

$$\left.\begin{array}{c}{}_{i=1}^k{\lambda }_i{\ge }_{i=1}^k{\omega }_i,k=1,...,t-1\\ {}_{i=1}^t{\lambda }_i{=}_{i=1}^t{\omega }_i\end{array}\right\}$$uid17

For $t=2,$ the conditions (▭) become

$${\lambda }_1\ge {\omega }_1,{\lambda }_1+{\lambda }_2={\omega }_1+{\omega }_2,$$

and they are also sufficient for the existence of a $2\times 2$ symmetric nonnegative matrix $B$ with eigenvalues ${\lambda }_1\ge {\lambda }_2$ and diagonal entries ${\omega }_1\ge {\omega }_2\ge 0,$ namely,

$$B=\left[\begin{array}{cc}{\omega }_1& \sqrt{({\lambda }_1-{\omega }_1)({\lambda }_1-{\omega }_2)}\\ \sqrt{({\lambda }_1-{\omega }_1)({\lambda }_1-{\omega }_2)}& {\omega }_2\end{array}\right].$$

For $t=3,$ we have the following conditions:

Lemma 1 [18] The conditions

$$\left.\begin{array}{c}{\lambda }_1\ge {\omega }_1\\ {\lambda }_1+{\lambda }_2\ge {\omega }_1+{\omega }_2\\ {\lambda }_1+{\lambda }_2+{\lambda }_3={\omega }_1+{\omega }_2+{\omega }_3\\ {\omega }_1\ge {\lambda }_2\end{array}\right\}$$uid19

are necessary and sufficient for the existence of a $3\times 3$ symmetric nonnegative matrix $B$ with eigenvalues ${\lambda }_1\ge {\lambda }_2\ge {\lambda }_3$ and diagonal entries ${\omega }_1\ge {\omega }_2\ge {\omega }_3\ge 0.$

In [22], the following symmetric nonnegative matrix $B,$ satisfying conditions (▭), it was constructed:

$$B=\left[\begin{array}{ccc}{\omega }_1& \sqrt{\frac{\mu -{\omega }_3}{2\mu -{\omega }_2-{\omega }_3}}s& \sqrt{\frac{\mu -{\omega }_2}{2\mu -{\omega }_2-{\omega }_3}}s\\ \sqrt{\frac{\mu -{\omega }_3}{2\mu -{\omega }_2-{\omega }_3}}s& {\omega }_2& \sqrt{(\mu -{\omega }_2)(\mu -{\omega }_3)}\\ \sqrt{\frac{\mu -{\omega }_2}{2\mu -{\omega }_2-{\omega }_3}}s& \sqrt{(\mu -{\omega }_2)(\mu -{\omega }_3)}& {\omega }_3\end{array}\right],$$uid20

where $\mu ={\lambda }_1+{\lambda }_2-{\omega }_1;$ $s=\sqrt{({\lambda }_1-\mu )({\lambda }_1-{\omega }_1)}.$

For $t\ge 4$ we have only a sufficient condition:

Theorem 8 Fiedler [18] If ${\lambda }_1\ge \cdots \ge {\lambda }_t$ and ${\omega }_1\ge \cdots \ge {\omega }_t$ satisfy

$$\left.\begin{array}{c}i){}_{i=1}^s{\lambda }_i{\ge }_{i=1}^s{\omega }_i,s=1,...,t-1\\ ii){}_{i=1}^t{\lambda }_i{=}_{i=1}^t{\omega }_i\\ iii){\omega }_{k-1}\ge {\lambda }_k,k=2,...,t-1\end{array}\right\},$$uid22

then there exists a $t\times t$ symmetric nonnegative matrix with eigenvalues ${\lambda }_1,...,{\lambda }_t$ and diagonal entries ${\omega }_1,...,{\omega }_t.$

Observe that

$$B=\left[\begin{array}{cccc}5& 2& \frac{1}{2}& \frac{1}{2}\\ 2& 5& \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}& 5& 2\\ \frac{1}{2}& \frac{1}{2}& 2& 5\end{array}\right]$$

has eigenvalues $8,6,3,3,$ but ${\lambda }_2=6>5={\omega }_1.$

Example 3 Let us consider the list $\Lambda =\{7,5,1,-3,-4,-6\}$ with the partition

$$\begin{array}{ccc}\hfill {\Lambda }_1& =& \{7,-6\},{\Lambda }_2=\{5,-4\},{\Lambda }_3=\{1,-3\}\text{with}\hfill \\ \hfill {\Gamma }_1& =& \{6,-6\},{\Gamma }_2=\{4,-4\},{\Gamma }_3=\{3,-3\}.\hfill \end{array}$$

We look for a symmetric nonnegative matrix $B$ with eigenvalues $7,5,1$ and diagonal entries $6,4,3.$ Then conditions (▭) are satisfied and from (▭) we compute

$$B=\left[\begin{array}{ccc}6& \sqrt{\frac{3}{5}}& \sqrt{\frac{2}{5}}\\ \sqrt{\frac{3}{5}}& 4& \sqrt{6}\\ \sqrt{\frac{2}{5}}& \sqrt{6}& 3\end{array}\right]\text{and}C=B-\Omega ,$$

where $\Omega =diag\{6,4,3\}.$ The symmetric matrices

$$A_1=\left[\begin{array}{cc}0& 6\\ 6& 0\end{array}\right],A_2=\left[\begin{array}{cc}0& 4\\ 4& 0\end{array}\right],A_3=\left[\begin{array}{cc}0& 3\\ 3& 0\end{array}\right]$$

realize ${\Gamma }_1,{\Gamma }_2,{\Gamma }_3.$ Then

$$A=\left[\begin{array}{ccc}{A}_1& & \\ & A_2& \\ & & A_3\end{array}\right]+XC{X}^T,\text{where}X=\left[\begin{array}{ccc}\frac{\sqrt{2}}{2}& 0& 0\\ \frac{\sqrt{2}}{2}& 0& 0\\ 0& \frac{\sqrt{2}}{2}& 0\\ 0& \frac{\sqrt{2}}{2}& 0\\ 0& 0& \frac{\sqrt{2}}{2}\\ 0& 0& \frac{\sqrt{2}}{2}\end{array}\right],$$

is symmetric nonnegative with spectrum $\Lambda .$

In the same way as Theorem ▭ was extended to Theorem ▭ (in the real case), Theorem ▭ was also extended to the following result:

Theorem 9 [33] Let $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ be a list of real numbers and let the partition $\Lambda ={\Lambda }_1\cup \cdots \cup {\Lambda }_{p_1+1}$ be such that

$${\Lambda }_k=\{{\lambda }_{k1},{\lambda }_{k2},...{\lambda }_{k{p}_k}\},{\lambda }_{11}={\lambda }_1,{\lambda }_{k1}\ge {\lambda }_{k2}\ge \cdots \ge {\lambda }_{k{p}_k},$$

$k=1,...,p_1+1,$ where ${\Lambda }_1$ is symmetrically realizable, $p_1$ is the number of elements of ${\Lambda }_1$ and some lists ${\Lambda }_k$ can be empty. Let ${\omega }_2,...,{\omega }_{p_1+1}$ be real numbers satisfying $0\le {\omega }_k\le {\lambda }_1,$ $k=2,...,p_1+1.$ Suppose that the following conditions hold:

$i)$ For each $k=2,...,p_1+1,$ there exists a symmetric nonnegative matrix $A_k$ with spectrum ${\Gamma }_k=\{{\omega }_k,{\lambda }_{k1},...,{\lambda }_{k{p}_k}\},$

$ii)$ There exists a $p_1\times p_1$ symmetric nonnegative matrix $B$ with spectrum ${\Lambda }_1$ and with diagonal entries ${\omega }_2,...,{\omega }_{p_1+1}.$

Then $\Lambda$ is symmetrically realizable.

Example 4 Now, from Theorem ▭, we can see that there exists a symmetric nonnegative matrix with spectrum $\Lambda =\{5,4,0,-3,-3,-3\}$, which can not be seen from Theorem ▭. Moreover, we can compute a realizing matrix. In fact, let the partition

$$\begin{array}{ccc}\hfill {\Lambda }_1& =& \{5,4,0,-3\},{\Lambda }_2=\{-3\},{\Lambda }_3=\{-3\}\text{with}\hfill \\ \hfill {\Gamma }_2& =& \{3,-3\},{\Gamma }_3=\{3,-3\},{\Gamma }_4={\Gamma }_5=\left\{0\right\}.\hfill \end{array}$$

The symmetric nonnegative matrix

$$B=\left[\begin{array}{cccc}3& 0& \sqrt{6}& 0\\ 0& 3& 0& \sqrt{6}\\ \sqrt{6}& 0& 0& 2\\ 0& \sqrt{6}& 2& 0\end{array}\right]$$

has spectrum ${\Lambda }_1$ and diagonal entries $3,3,0,0.$ Let $\Omega =diag\{3,3,0,0\}$ and

$$X=\left[\begin{array}{cccc}\frac{\sqrt{2}}{2}& 0& 0& 0\\ \frac{\sqrt{2}}{2}& 0& 0& 0\\ 0& \frac{\sqrt{2}}{2}& 0& 0\\ 0& \frac{\sqrt{2}}{2}& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right],A_2=A_3=\left[\begin{array}{cc}0& 3\\ 3& 0\end{array}\right],C=B-\Omega .$$

Then, from Theorem ▭ we obtain

$$A=\left[\begin{array}{cccc}{A}_2& & & \\ & A_3& & \\ & & 0& \\ & & & 0\end{array}\right]+XC{X}^T,$$

which is symmetric nonnegative with spectrum $\Lambda .$

The following result, although is not written in the fashion of a sufficient condition, is indeed a very general and efficient sufficient condition for the SNIEP.

Theorem 10 [36] Let $A$ be an $n\times n$ irreducible symmetric nonnegative matrix with spectrum $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\},$ Perron eigenvalue ${\lambda }_1$ and a diagonal element $c.$ Let $B$ be an $m\times m$ symmetric nonnegative matrix with spectrum $\Gamma =\{{\mu }_1,{\mu }_2,...,{\mu }_m\}$ and Perron eigenvalue ${\mu }_1.$

$i)$ If ${\mu }_1\le c,$ then there exists a symmetric nonnegative matrix $C,$ of order $(n+m-1),$ with spectrum $\{{\lambda }_1,...,{\lambda }_n,{\mu }_2,...,{\mu }_m\}.$

$ii)$ If ${\mu }_1\ge c,$ then there exists a symmetric nonnegative matrix $C,$ of order $(n+m-1),$ with spectrum $\{{\lambda }_1+{\mu }_1-c,{\lambda }_2,...,{\lambda }_n,{\mu }_2,...,{\mu }_m\}.$

Example 5 The following example, given in [36], shows that

$\{7,5,0,-4,-4,-4\}$ with the partition

$$\Lambda =\{7,5,0,-4\},\Gamma =\{4,-4\},$$

satisfies conditions of Theorem ▭, where

$$A=\left[\begin{array}{cccc}4& 0& b& 0\\ 0& 4& 0& d\\ b& 0& 0& \sqrt{6}\\ 0& d& \sqrt{6}& 0\end{array}\right]\text{with}{b}^2+d^2=23,bd=4\sqrt{6},$$

is symmetric nonnegative with spectrum $\Lambda .$ Then there exists a symmetric nonnegative matrix $C$ with spectrum $\{7,5,0,-4,-4\}$ and a diagonal element $4.$ By applying again Theorem ▭ to the lists $\{7,5,0,-4,-4\}$ and $\{4,-4\},$ we obtain the desired symmetric nonnegative matrix.

It is not hard to show that both results, Theorem ▭ and Theorem ▭, are equivalent (see [37]). Thus, the list in the Example ▭ is also realizable from Theorem ▭, while the list in the example ▭ is also realizable from Theorem ▭.

5. List of complex numbers

In this section we consider lists of complex nonreal numbers. We start with a complex generalization of a well known result of Suleimanova, usually considered as one of the important results in the RNIEP (see [11]): The list ${\lambda }_1>0>{\lambda }_2\ge \cdots \ge {\lambda }_n$ is the spectrum of a nonnegative matrix if and only if ${\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n\ge 0.$

Theorem 11 [28] Let $\Lambda =\{{\lambda }_0,{\lambda }_1,...,{\lambda }_n\}$ be a list of complex numbers closed under complex conjugation, with

$${\Lambda }^{\text{'}}=\{{\lambda }_1,...,{\lambda }_n\}\subset \{z\in ℂ:Rez\le 0;\left|Rez\right|\ge \left|Imz\right|\}.$$

Then $\Lambda$ is realizable if and only if ${}_{i=0}^n{\lambda }_i\ge 0.$

Suppose that the elements of ${\Lambda }^{\text{'}}$ are ordered in such a way that ${\lambda }_{2p+1},...,{\lambda }_n$ are real and ${\lambda }_1,...,{\lambda }_{2p}$ are complex nonreal, with

$$x_k=Re{\lambda }_{2k-1}=Re{\lambda }_{2k}\text{and}{y}_k=Im{\lambda }_{2k-1}=Im{\lambda }_{2k}$$

for $k=1,...,p.$ Consider the matrix

$$B=\left[\begin{array}{ccccccccc}0& 0& 0& .& & & & & \\ -x_1+y_1& x_1& -y_1& .& & & & & \\ -x_1-y_1& y_1& x_1& .& & & & & \\ ⋮& ⋮& ⋮& \ddots & & & & & \\ -x_p+y_p& 0& 0& .& x_p& -y_p& & & \\ -x_p-y_p& 0& 0& .& y_p& x_p& & & \\ -{\lambda }_{2p+1}& 0& 0& .& & & {\lambda }_{2p+1}& & \\ ⋮& ⋮& ⋮& .& & & & \ddots & \\ -{\lambda }_n& 0& & .& & & & & {\lambda }_n\end{array}\right].$$

It is clear that $B\in {\mathrm{𝒞𝒮}}_0$ with spectrum $\{0,{\lambda }_1,...,{\lambda }_n\}$ and all the entries on its first column are nonnegative. Define $𝐪={(q_0,q_1,...,q_n)}^T$ with $q_0={\lambda }_0{+}_{i=1}^n{\lambda }_i$ and

$$q_k=-Re{\lambda }_k\text{for}k=1,...,2p\text{and}{q}_k=-{\lambda }_k\text{for}k=2p+1,...,n.$$

Then, from the Brauer Theorem ▭ $A=B+{\mathrm{𝐞𝐪}}^T$ is nonnegative with spectrum $\Lambda .$

In the case when all numbers in the given list, except one (the Perron eigenvalue), have real parts smaller than or equal to zero, remarkably simple necessary and sufficient conditions were obtained in [38].

Theorem 12 [38] Let ${\lambda }_2,{\lambda }_3,...,{\lambda }_n$ be nonzero complex numbers with real parts less than or equal to zero and let ${\lambda }_1$ be a positive real number. Then the list $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is the nonzero spectrum of a nonnegative matrix if the following conditions are satisfied:

$$\begin{array}{cc}i)& \overline{\Lambda }=\Lambda \\ ii)& s_1{=}_{i=1}^n{\lambda }_i\ge 0\\ iii)& s_2{=}_{i=1}^n{\lambda }_i^2\ge 0\end{array}$$uid30

The minimal number of zeros that need to be added to $\Lambda$ to make it realizable is the smallest nonnegative integer $N$ for which the following inequality is satisfied:

$$s_1^2\le (n+N)s_2.$$

Furthermore, the list $\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n,0,...,0\}$ can be realized by $C+\alpha I,$ where $C$ is a nonnegative companion matrix with trace zero, $\alpha$ is a nonnegative scalar and $I$ is the $n\times n$ identity matrix.

Corollary 1 [38] Let ${\lambda }_2,{\lambda }_3,...,{\lambda }_n$ be complex numbers with real parts less than or equal to zero and let ${\lambda }_1$ be a positive real number. Then the list $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is the spectrum of a nonnegative matrix if and only if the following conditions are satisfied:

$$\begin{array}{cc}i)& \overline{\Lambda }=\Lambda \\ ii)& s_1{=}_{i=1}^n{\lambda }_i\ge 0\\ iii)& s_2{=}_{i=1}^n{\lambda }_i^2\ge 0\\ iv)& s_1^2\le n{s}_2\end{array}$$uid32

Example 6 The list $\Lambda =\{8,-1+3i,-1-3i,-2+5i,-2-5i\}$ satisfies conditions (▭). Then $\Lambda$ is the spectrum of the nonnegative companion matrix

$$C=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 2320& 494& 278& 1& 2\end{array}\right].$$

Observe that Theorem ▭ gives no information about the realizability of $\Lambda .$

The list $\{19,-1+11i,-1-11i,-3+8i,-3-8i\}$ was given in [38]. It does not satisfy conditions (▭): $s_1=11,$ $s_2=11$ and $s_1^{2}n{s}_2.$ The inequality ${11}^2\le (5+N)11$ is satisfied for $N\ge 6.$ Then we need to add 6 zeros to the list to make it realizable.

Theorem ▭ (in section 3), can also be extended to the complex case:

Theorem 13 [8] Let $\Lambda =\{{\lambda }_2,{\lambda }_3,...,{\lambda }_n\}$ be a list of complex numbers such that $\overline{\Lambda }=\Lambda ,$ ${\lambda }_1\ge {max}_i\left|{\lambda }_i\right|,$ $i=2,...,n,$ and ${}_{i=1}^n{\lambda }_i\ge 0.$ Suppose that:

$i)$ there exists a partition $\Lambda ={\Lambda }_1\cup \cdots \cup {\Lambda }_t$ with

$${\Lambda }_k=\{{\lambda }_{k1},{\lambda }_{k2},...{\lambda }_{k{p}_k}\},{\lambda }_{11}={\lambda }_1,$$

$k=1,...,t,$ such that ${\Gamma }_k=\{{\omega }_k,{\lambda }_{k2},...,{\lambda }_{k{p}_k}\}$ is realizable by a nonnegative matrix $A_k\in {\mathrm{𝒞𝒮}}_{{\omega }_k},$ and

$ii)$ there exists a $t\times t$ nonnegative matrix $B\in {\mathrm{𝒞𝒮}}_{{\lambda }_1},$ with eigenvalues

${\lambda }_1,{\lambda }_{21},...,{\lambda }_{t1}$ (the first elements of the lists ${\Lambda }_k)$ and with diagonal entries ${\omega }_1,{\omega }_2,...,{\omega }_t$ (the Perron eigenvalues of the lists ${\Gamma }_k).$

Then $\Lambda$ is realizable.

Example 7 Let $\Lambda =\{7,1,-2,-2,-2+4i,-2-4i\}.$ Consider the partition

$$\begin{array}{ccc}\hfill {\Lambda }_1& =& \{7,1,-2,-2\},{\Lambda }_2=\{-2+4i\},{\Lambda }_3=\{-2-4i\}\text{with}\hfill \\ \hfill {\Gamma }_1& =& \{3,1,-2,-2\},{\Gamma }_2=\left\{0\right\},{\Gamma }_3=\left\{0\right\}.\hfill \end{array}$$

We look for a nonnegative matrix $B\in {\mathrm{𝒞𝒮}}_7$ with eigenvalues $7,-2+4i,-2-4i$ and diagonal entries $3,0,0,$ and a nonnegative matrix $A_1$ realizing ${\Gamma }_1.$ They are

$$B=\left[\begin{array}{ccc}3& 0& 4\\ \frac{41}{7}& 0& \frac{8}{7}\\ 0& 7& 0\end{array}\right]\text{and}{A}_1=\left[\begin{array}{cccc}0& 2& 0& 1\\ 2& 0& 0& 1\\ 0& 1& 0& 2\\ 0& 1& 2& 0\end{array}\right].$$

Then

$$\begin{array}{c}\hfill A=\left[\begin{array}{ccc}{A}_1& & \\ & 0& \\ & & 0\end{array}\right]+\left[\begin{array}{ccc}1& 0& 0\\ 1& 0& 0\\ 1& 0& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 4\\ \frac{41}{7}& 0& 0& 0& 0& \frac{8}{7}\\ 0& 0& 0& 0& 7& 0\end{array}\right]=\left[\begin{array}{cccccc}0& 2& 0& 1& 0& 4\\ 2& 0& 0& 1& 0& 4\\ 0& 1& 0& 2& 0& 4\\ 0& 1& 2& 0& 0& 4\\ \frac{41}{7}& 0& 0& 0& 0& \frac{8}{7}\\ 0& 0& 0& 0& 7& 0\end{array}\right]\end{array}$$

has the spectrum $\Lambda .$

6. Fiedler and Guo results

One of the most important works about the SNIEP is due to Fiedler [18]. In [18] Fiedler showed, as it was said before, that Kellogg sufficient conditions for the RNIEP are also sufficient for the SNIEP. Three important and very useful results of Fiedler are:

Lemma 2 [18] Let $A$ be a symmetric $m\times m$ matrix with eigenvalues ${\alpha }_1,...,{\alpha }_m,$ $A𝐮={\alpha }_1𝐮,$ $∥𝐮∥=1.$ Let $B$ be a symmetric $n\times n$ matrix with eigenvalues ${\beta }_1,...,{\beta }_n,$ $B𝐯={\beta }_1𝐯,$ $∥𝐯∥=1.$ Then for any $\rho ,$ the matrix

$$C=\left[\begin{array}{cc}A& \rho {\mathrm{𝐮𝐯}}^T\\ \rho {\mathrm{𝐯𝐮}}^T& B\end{array}\right]$$

has eigenvalues ${\alpha }_2,...,{\alpha }_m,{\beta }_2,...,{\beta }_n,{\gamma }_1,{\gamma }_2,$ where ${\gamma }_1,{\gamma }_2$ are eigenvalues of the matrix

$$\tilde{C}=\left[\begin{array}{cc}{\alpha }_1& \rho \\ \rho & {\beta }_1\end{array}\right].$$

Lemma 3 [18] If $\{{\alpha }_1,...,{\alpha }_m\}$ and $\{{\beta }_1,...,{\beta }_n\}$ are lists symmetrically realizable and ${\alpha }_1\ge {\beta }_1$, then for any $t\ge 0,$ the list

$$\{{\alpha }_1+t,{\beta }_1-t,{\alpha }_2,...,{\alpha }_m,{\beta }_2,...,{\beta }_n\}$$

is also symmetrically realizable.

Lemma 4 [18] If $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is symmetrically realizable by a nonnegative matrix and if $t>0,$ then

$${\Lambda }_t=\{{\lambda }_1+t,{\lambda }_2,...,{\lambda }_n\}$$

is symmetrically realizable by a positive matrix.

Remark 1 It is not hard to see that Lemma ▭ can be obtained from Theorem ▭. In fact, it is enough to consider

$$\begin{array}{ccc}\hfill C& =& \left[\begin{array}{cc}A& \\ & B\end{array}\right]+\left[\begin{array}{cc}𝐮& \mathbf{0}\\ \mathbf{0}& 𝐯\end{array}\right]\left[\begin{array}{cc}0& \rho \\ \rho & 0\end{array}\right]\left[\begin{array}{cc}{𝐮}^T& {\mathbf{0}}^T\\ {\mathbf{0}}^T& {𝐯}^T\end{array}\right]\hfill \\ & =& \left[\begin{array}{cc}A& \rho {\mathrm{𝐮𝐯}}^T\\ \rho {\mathrm{𝐯𝐮}}^T& B\end{array}\right],\hfill \end{array}$$

which is symmetric with eigenvalues ${\gamma }_1,{\gamma }_2,{\alpha }_2,...,{\alpha }_m,{\beta }_2,...,{\beta }_n,$ where ${\gamma }_1,{\gamma }_2$ are eigenvalues of

$$B=\left[\begin{array}{cc}{\alpha }_1& \rho \\ \rho & {\beta }_1\end{array}\right].$$

Now we consider a relevant result due to Guo [39]:

Theorem 14 [39] If the list of complex numbers $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is realizable, where ${\lambda }_1$ is the Perron eigenvalue and ${\lambda }_2\in ℝ,$ then for any $t\ge 0$ the list ${\Lambda }_t=\{{\lambda }_1+t,{\lambda }_2\pm t,{\lambda }_3,...,{\lambda }_n\}$ is also realizable.

Corollary 2 [39] If the list of real numbers $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is realizable and $t_1{=}_{i=2}^n\left|t_i\right|$ with $t_i\in ℝ,$ $i=2,...,n,$ then the list ${\Lambda }_t=\{{\lambda }_1+t_1,{\lambda }_2+t_2,...,{\lambda }_n+t_n\}$ is also realizable.

Example 8 Let $\Lambda =\{8,6,3,3,-5,-5,-5,-5\}$ be a given list. Since the lists ${\Lambda }_1={\Lambda }_2=\{7,3,-5,-5\}$ are both realizable (see [31] to apply a simple criterion, which shows the realizability of ${\Lambda }_1={\Lambda }_2$), then

$${\Lambda }_1\cup {\Lambda }_2=\{7,7,3,3,-5,-5,-5,-5\}$$

is also realizable. Now, from Theorem ▭, with $t=1,$ $\Lambda$ is realizable.

Guo also sets the following two questions:

Question 1: Do complex eigenvalues of nonnegative matrices have a property similar to Theorem ▭?

Question 2: If the list $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is symmetrically realizable, and $t>0,$ is the list ${\Lambda }_t=\{{\lambda }_1+t,{\lambda }_2\pm t,{\lambda }_3,...,{\lambda }_n\}$ symmetrically realizable?.

It was shown in [40] and also in [41] that Question 1 has an affirmative answer.

Theorem 15 [40] Let $\Lambda =\{{\lambda }_1,a+bi,a-bi,{\lambda }_4,...,{\lambda }_n\}$ be a realizable list of complex numbers. Then for all $t\ge 0,$ the perturbed list

$${\Lambda }_t=\{{\lambda }_1+2t,a-t+bi,a-t-bi,{\lambda }_4,...,{\lambda }_n\}$$

is also realizable.

Question 2, however, remains open. An affirmative answer to Question 2, in the case that the symmetric realizing matrix is a nonnegative circulant matrix or it is a nonnegative left circulant matrix, it was given in [42]. The use of circulant matrices has been shown to be very useful for the NIEP [27], [32]. In [32] it was given a necessary and sufficient condition for a list of 5 real numbers, which corresponds to a even-conjugate vector, to be the spectrum of $5\times 5$ symmetric nonnegative circulant matrix:

Lemma 5 [32] Let $\lambda ={({\lambda }_1,{\lambda }_2,{\lambda }_3,{\lambda }_3,{\lambda }_2)}^T$ be a vector of real numbers (even-conjugate) such that

$$\begin{array}{ccc}\hfill {\lambda }_1& \ge & \left|{\lambda }_j\right|,j=2,3\hfill \\ \hfill {\lambda }_1& \ge & {\lambda }_2\ge {\lambda }_3\hfill \\ \hfill {\lambda }_1+2{\lambda }_2+2{\lambda }_3& \ge & 0\hfill \end{array}$$uid45

A necessary and sufficient condition for $\{{\lambda }_1,{\lambda }_2,{\lambda }_3,{\lambda }_3,{\lambda }_2\}$ to be the spectrum of a symmetric nonnegative circulant matrix is

$${\lambda }_1+({\lambda }_3-{\lambda }_2)\frac{\sqrt{5}-1}{2}-{\lambda }_2\ge 0.$$uid46

Example 9 From Lemma ▭ we may know, for instance, that the list

$\{6,1,1,-4,-4\}$ is the spectrum of a symmetric nonnegative circulant matrix.

7. Some open questions

We finish this chapter by setting two open questions:

Question 1: If the list of real numbers $\Lambda =\{{\lambda }_1,{\lambda }_2,...,{\lambda }_n\}$ is symmetrically realizable, and $t>0,$ is the list ${\Lambda }_t=\{{\lambda }_1+t,{\lambda }_2\pm t,{\lambda }_3,...,{\lambda }_n\}$ also symmetrically realizable?

Some progress has been done about this question. In [42], it was given an affirmative answer to Question 1, in the case that the realizing matrix is symmetric nonnegative circulant matrix or it is nonnegative left circulant matrix. In [43] it was shown that if $1>{\lambda }_2\ge \cdots \ge {\lambda }_n\ge 0,$ then Theorem ▭ holds for positive stochastic, positive doubly stochastic and positive symmetric matrices.

Question 2: How adding one or more zeros to a list can lead to its symmetric realizability by different symmetric patterned matrices?

The famous Boyle-Handelman Theorem [44] gives a nonconstructive proof of the fact that if $s_k={\lambda }_1^k+{\lambda }_2^k+\cdots +{\lambda }_n^k>0,$ for $k=1,2,...,$ then there exists a nonnegative number $N$ for which the list $\{{\lambda }_1,...,{\lambda }_n,0,...,0\},$ with $N$ zeros added, is realizable. In [38] Laffey and Šmigoc completely solve the NIEP for lists of complex numbers $\Lambda =\{{\lambda }_1,...,{\lambda }_n\},$ closed under conjugation, with ${\lambda }_2,...,{\lambda }_n$ having real parts smaller than or equal to zero. They show the existence of $N\ge 0$ for which $\Lambda$ with $N$ zeros added is realizable and show how to compute the least such $N.$ The situation for symmetrically realizable spectra is different and even less is known.

8. Conclusion

The nonnegative inverse eigenvalue problem is an open and difficult problem. A full solution is unlikely in the near future. A number of partial results are known in the literature about the problem, most of them in terms of sufficient conditions. Some matrix results, like Brauer Theorem (Theorem ▭), Rado Theorem (Theorem ▭), and its symmetric version (Theorem ▭) have been shown to be very useful to derive good sufficient conditions. This way, however, seems to be quite narrow and may be other techniques should be explored and applied.