The Recursive Inverse Eigenvalue Problem.
The recursive inverse eigenvalue problem for matrices is studied, where for each leading principal submatrix an eigenvalue and associated left and right eigenvectors are assigned. Existence and uniqueness results as well as explicit formulas are proven, and applications to nonnegative matrices, Z-matrices, M-matrices, symmetric matrices, Stieltjes matrices, and inverse M-matrices are considered.
Introduction
Inverse eigenvalue problems are a very important subclass of inverse problems
that arise in the context of mathematical modeling and parameter identification.
They have been studied extensively in the last 20 years, see e.g. [3, 5, 7, 11, 12, 14]
and the references therein. In particular, the inverse eigenvalue problem for non-negative
matrices is still a topic of very active research, since a necessary and
sufficient condition for the existence of a nonnegative matrix with a prescribed
spectrum is still an open problem, see [4, 11]. In this paper we study inverse
eigenvalue problems in a recursive matter, that allows to extend already constructed
solutions if further data become available, as is frequently the case in
inverse eigenvalue problems, e.g. [3].
We investigate the following recursive inverse eigenvalue problem of order n:
Let F be a field, let s
l 1;1
l 2;1
l 2;2
l n;1
r 1;1
r 1;2
r 2;2
r 1;n
be vectors with elements in F . Construct a matrix A 2 F n;n such
l T
where Ahii denotes the i-th leading principal submatrix of A.
In the sequel we shall use the notation RIEP(n) for "the recursive inverse eigenvalue
problem of order n".
In Section 2 we study the existence and uniqueness of solutions for RIEP(n) in the
general case. Our main result gives a recursive characterization of the solution
for RIEP(n). We also obtain a nonrecursive necessary and sufficient condition
for unique solvability as well as an explicit formula for the solution in case of
uniqueness.
The results of Section 2 are applied in the subsequent sections to special cases.
In Section 3 we discuss nonnegative solutions for RIEP(n) over the field IR of real
numbers. We also introduce a nonrecursive sufficient condition for the existence
of a nonnegative solution for RIEP(n). Uniqueness of nonnegative solutions for
RIEP(n) is discussed in Section 4. In Section 5 we study Z-matrix and M-matrix
solutions for RIEP(n) over IR. In Section 6 we consider real symmetric solutions
for RIEP(n) over IR. In Section 7 we consider positive semidefinite real symmetric
solutions for RIEP(n) over IR. In Section 8 we combine the results of the previous
two sections to obtain analogous results for Stieltjes matrices. Finally, in Section
9 we investigate inverse M-matrix solutions for RIEP(n).
Existence and uniqueness results
In this section we study the existence and uniqueness of solutions for RIEP(n) in
the general case. For this purpose we introduce some further notation. For the
vectors l
~
l
l i;1
r 1;i
The case is easy to verify.
Proposition 1 If l solves RIEP(1). If
either l 1;1 6= 0 or r 1;1 6= 0 then is the unique solution for RIEP(1).
For we have the following recursive characterization of the solution for
RIEP(n).
Theorem 2 Let n - 2. There exists a solution for RIEP(n) if and only if there
exists a solution B for RIEP(n-1) such that
l
and
There exists a unique solution for RIEP(n) if and only if there exists a unique
solution for RIEP(n-1) and l n;n r n;n 6= 0.
Proof. Let A be an n \Theta n matrix. Partition A as
where B is an (n-1) \Theta (n-1) matrix. Clearly, A solves RIEP(n) if and only if B
solves RIEP(n-1) and
It thus follows that there exists a solution for RIEP(n) if and only if there exists
a solution B for RIEP(n-1) such that the equations (4)-(7) (with unknown x, y
and z) are solvable. We now show that these equations are solvable if and only
if (1) and (2) hold. Distinguish between four cases:
1. r Here (4) is equivalent to (2), (5) is equivalent to
l n;n
and (6) then follows from (4). For every y 2 F n\Gamma1 we can find z 2 F such
that (7) holds.
2. l Here (5) is equivalent to (1), (4) is equivalent to
r n;n
and (7) then follows from (5). For every x 2 F n\Gamma1 we can find z 2 F such
that (6) holds.
3. l Here (4) is equivalent to (2) and (5) is equivalent to (1).
For any x 2 F n\Gamma1 with x T ~ r we have (6), and for any y 2 F n\Gamma1 with
we have (7), where z can be chosen arbitrarily.
4. l n;n 6= 0; r n;n 6= 0. Here (4)-(7) have a unique solution, given by (8),
and
l n;n r n;n
It follows that (4)-(7) are solvable if and only if (1) and (2) hold.
To prove the uniqueness assertion, note that it follows from our proof that if
either l a solution is not unique, since at least one of the
vectors x, y and z can be chosen arbitrarily. If both l n;n 6= 0 and r n;n 6= 0 then
every solution B for RIEP(n-1) defines a unique solution A for RIEP(n). The
uniqueness claim follows.
This result is recursive and allows to derive a recursive algorithm to compute
the solution, but we do not get explicit nonrecursive conditions that characterize
the existence of solutions. In order to get a necessary and sufficient condition
for unique solvability as well as an explicit formula for the solution in case of
uniqueness, we define the n \Theta n matrix R n to be the matrix whose columns are
appended at the bottom to obtain n-vectors. Similarly, we
define the n \Theta n matrix L n to be the matrix whose rows are l
appended at the right to obtain n-vectors. That is, we have
l 2;1 l 2;2
r 2;2
. r n\Gamma1;n
We denote
Also, we denote by ffi the Hadamard (or elementwise) product of matrices.
Proposition 3 A solution A for RIEP(n) satisfies
Proof. We prove our claim by induction on n. For the claim follows easily.
Assume that the assertion holds for Partition A as in (3).
We have
l n;n
R
By the inductive assumption we have L Also, by
(4) we have B~r by (5) we have ~ l T
n , and by (7)
we have ~ l T
n;n . It thus follows that
In general, the converse of Proposition 3 does not hold, that is, a matrix A satisfying
does not necessarily form a solution for RIEP(n), as is demonstrated
by Example 5 below.
Theorem 4 There is a unique solution for RIEP(n) if and only if
l 1;1 6= 0 or r 1;1 6= 0
and
l i;i r i;i 6= 0;
Furthermore, the unique solution is given by
Proof. The uniqueness claim follows from Proposition 1 and Theorem 2. The
fact that the unique solution for RIEP(n) is given by (14) follows immediately
from Proposition 3.
In the case that the solution is not unique, that is, whenever l
or whenever l i;i or r i;i vanish for some i ? 1, the matrices L n and R n defined
in (11) are not invertible. Therefore, in this case (14) is invalid. We conclude
this section by an example showing that, in general, a revised form of (14), with
inverses replaced by generalized inverses, does not provide a solution for RIEP(n).
Example 5 Let
and let
hi
"0
We have
be the Moore-Penrose inverses of L and R respectively, see [1].
We have
Since Ah2i does not have an eigenvalue 2, A is not a solution for RIEP(3). Note
that we still have L n AR
In this section we have characterized solvability of RIEP(n) over a general field
F in terms of recursive conditions. We have also given a necessary and sufficient
condition for unique solvability and an explicit formula for the unique solution. In
the following sections we shall discuss the special cases of nonnegative matrices,
Z-matrices, M-matrices, real symmetric matrices, positive semidefinite matrices,
Stieltjes matrices and inverse M-matrices.
3 Existence of nonnegative solutions
In this section we apply the results of Section 2 to nonnegative solutions for
RIEP(n) over the field IR of real numbers. A matrix A 2 IR n;n is said to be
nonnegative [positive] if all elements of A are nonnegative [positive]. In this case
we
In order to state our results we define a vector over IR to be unisign if its nonzero
components have the same sign.
Theorem 6 Let n - 2. There exists a nonnegative solution for RIEP(n) if and
only if we have
l i or r i is a unisign nonzero vector =) s
and there exists a nonnegative solution B for RIEP(n-1)
sn ~ rn
rn;n
rn;n
l n;n
l n;n
and
l n;n r n;n 6= 0 =) s n (
l n;n r n;n
l n;n r n;n
There exists a positive solution for RIEP(n) if and only if there exists a positive
solution B for RIEP(n-1) such that (15)-(18) hold with strict inequalities and
every nonzero unisign vector l i or r i has no zero components.
Proof. Let A 2 IR n;n . As in the proof of Theorem 2, partition A as in (3), and so
A solves RIEP(n) if and only if B solves RIEP(n-1) and (4)-(7) hold. Therefore,
if A is a nonnegative solution for RIEP(n) then we have (16)-(18). Also, it follows
from the nonnegativity of A that (15) holds. Conversely, assume that (15) holds
and that B forms a nonnegative solution for RIEP(n-1) satisfying (16)-(18). We
show that in this case we can find nonnegative solutions x, y and z for (4)-(7).
Distinguish between four cases:
1. r Here x is given by (8), y can be chosen arbitrarily,
and z should be chosen such that (7) holds. It follows from (17) that x is
nonnegative. If s n - 0 then we choose so we
have a nonnegative solution for (4)-(7). If s n ! 0 then, by (15), l n is not
unisign and hence ~ l T
l n;n
has at least one negative component. It follows that
we can find a positive vector y such that ~ l T
l n;n
by (7) we have
l n;n
, it follows that z ? 0, and so again we have a nonnegative
solution for (4)-(7).
2. l Here y is given by (9), x can be chosen arbitrarily, and z
should be chosen such that (6) holds. The proof follows as in the previous
case.
3. l should be chosen such that x T ~
and z can be chosen arbitrarily. In order to obtain a nonnegative solution
we can choose x, y and z to be zero.
4. l n;n 6= 0; r n;n 6= 0. Here x is given by (8), y is given by (9), and z is given
by (10). It follows from (17), (16) and (18) that x, y and z are nonnegative.
Assume now that A is a positive solution for RIEP(n). It is easy to verify that in
this case (15)-(18) should hold with strict inequalities. Also, for every nonzero
unisign vector l i [r i ], the vector l T
has no zero components, implying
that l i , [r i ] has no zero components. Conversely, assume that (15) holds with a
strict inequality, that every nonzero unisign vector l i or r i has no zero components,
and that B forms a positive solution for RIEP(n-1) satisfying (16)-(18) with strict
inequalities. We show that in this case we can find positive solutions x, y and z
for (4)-(7). Note that in Case 1 above, the vector x now becomes positive. Also,
since the inequality in (15) is now strict, we have either s n ? 0, in which case
we can choose positive y sufficiently small such that z is positive, or s n - 0, in
which case y can be chosen positive as before and the resulting z is positive. The
same arguments hold for Case 2. In Case 4, it follows from the strict inequalities
(17)-(18) that x, y and z are positive. Finally, in Case 3, since l n and r n both
have at least one zero component, it follows that both vectors are not unisign.
Hence, we can find positive x and y such that x T ~ r
We assign any
positive number to z to find a positive solution A for RIEP(n).
By the Perron-Frobenius theory, see e.g. [8, 2], the largest absolute value ae(A)
of an eigenvalue of a nonnegative n \Theta n matrix A is itself an eigenvalue of A,
the so called Perron root of A, and it has an associated nonnegative eigenvector.
Furthermore, if A is irreducible, that is, if either there
exists no permutation matrix P such that P T
where B and D
are square, then ae(A) is a simple eigenvalue of A with an associated positive
eigenvector. If A is not necessarily irreducible then we have the following, see
e.g. [2].
Theorem 7 If B is a principal submatrix of a nonnegative square matrix A
then ae(B) - ae(A). Furthermore, ae(A) is an eigenvalue of some proper principal
submatrix of A if and only if A is reducible.
Note that if we require that the s i are the Perron roots of the principal submatrices
Theorem 7, we have
If, furthermore, all the leading principal submatrices of A are required to be
irreducible, then
Condition (19) is not sufficient to guarantee that a nonnegative solution A for
RIEP(n) necessarily has s Perron roots of Ahii,
demonstrated by the following example.
Example 8 Let
and let
hi
"0
The nonnegative matrix 24
In order to see cases in which s are the Perron roots of Ahii,
respectively, we prove
Proposition 9 If the vector l n or r n is positive then for a nonnegative solution
A for RIEP(n) we have
Proof. The claim follows immediately from the known fact that a positive eigenvector
of a nonnegative matrix corresponds to the spectral radius, see e.g. Theorem
2.1.11 in [2, p. 128].
ng we have either l i ? 0 or r i ? 0 then for
every nonnegative solution A for RIEP(n) we have
Lemma 11 Assume that there exists a nonnegative solution A for RIEP(n) such
that ae(Ahn-1i) ! s n . If r n 6= 0 or l n 6= 0 then
Proof. Since r n 6= 0 or l n 6= 0 it follows that s n is an eigenvalue of A. Assume that
ae(A). It follows that the nonnegative matrix A has at least two eigenvalues
larger than or equal to s n . By [6, p. 473], see also [10, Corollary 1], it follows
that ae(Ahn-1i) - s n , which is a contradiction. Therefore, we have s
Corollary 12 If for every ng we have either r i 6= 0 or l i 6= 0, and if
holds then for every nonnegative solution A for RIEP(n) we have
Proof. Note that Our result follows using
Lemma 11 repeatedly.
Lemma 13 Assume that r n - 0 and r n;n 6= 0 or that l n - 0 and l n;n 6=
0. Then for every nonnegative solution A for RIEP(n) we have
g.
Proof. Without loss of generality, we consider the case where r n - 0 and r n;n 6= 0.
If r n is positive then, by Proposition 9, we have since by the
Perron-Frobenius theory we have ae(Ahn-1i) - ae(A), the result follows. Other-
wise, r n has some zero components. Let ff be the set of indices i such that r i;n ? 0
and let ff c be the complement of ff in ng. Note that since r n is a nonnegative
eigenvector of the nonnegative matrix A it follows that the submatrix A[ff c jff]
of A, with rows indexed by ff c and columns indexed by ff, is a zero matrix. It follows
that A is a reducible matrix and ae(A[ffjff])g. Note
that the subvector r n [ff] of r n indexed by ff is a positive eigenvector of A[ffjff]
associated with the eigenvalue s n . It thus follows that
it follows that A[ff c jff c ] is a submatrix of Ahn-1i. Thus, by the Perron-Frobenius
theory we have ae(A[ff c jff c ]) - ae(Ahn-1i) - ae(A). Hence, it follows that
g.
Corollary 14 Assume that for every ng we have either r i - 0 and
r i;i 6= 0 or l i - 0 and l i;i 6= 0. Then for every nonnegative solution A for RIEP(n)
we have g.
Proof. Note that Our result follows using
repeatedly.
Corollary 15 Assume that for every
r i;i 6= 0 or l i - 0 and l i;i 6= 0. If (19) holds then for every nonnegative solution A
we have
Another interesting consequence of Theorem 4 is the following relationship between
the matrix elements and the eigenvectors associated with the Perron roots
of the leading principal submatrices of a nonnegative matrix.
Corollary 2. Let A 2 IR n;n be a nonnegative matrix, let s
be the Perron roots and associated left and right eigenvectors of Ahii,
respectively, and assume that (20) holds. Let S defined as in (11) and
(12). Then
Proof. Since (20) holds, it follows that s i is not an eigenvalue of Ahi-1i,
Therefore, it follows from (1) and (2) that l i;i r i;i 6= 0. Also, since l 1 and
r 1 are eigenvectors of Ah1i, we have l 1;1 r 1;1 6= 0. It now follows from Theorem 4
that Ahii is the unique solution for RIEP(i), and is given by (21).
While Theorem 6 provides a recursive characterization for nonnegative solvability
of RIEP(n), in general nonrecursive necessary and sufficient conditions for the
existence of nonnegative solution are not known. We now present a nonrecursive
sufficient condition.
Corollary 17 Assume that the vectors l are all positive and
that the numbers s are all positive. Let
r j;i
r
r j;i
r
l
l i;j
l i\Gamma1;j
l i;j
l i\Gamma1;j
If we have
and
then there exists a (unique) nonnegative solution A for RIEP(n).
Furthermore, if all the inequalities (22)-(24) hold with strict inequality then there
exists a (unique) positive solution A for RIEP(n).
Proof. We prove our assertion by induction on n. The case
the inductive assumption we can find a nonnegative solution B for RIEP(n-1).
Note that
Therefore, it follows from (22) that
and so (16) holds. Similarly we prove that (17) holds. To prove that
holds note that by (25) we have B~r n - Bm r
Similarly, we have ~ l T
. Hence, it follows that ~ l T
. By (24) applied to
Theorem 6, there exists a nonnegative solution for RIEP(n). The proof of the
positive case is similar.
The conditions in Corollary 17 are not necessary as is demonstrated by the following
example.
Example
hi
"1
We have m r
2. Note that both (22) and
(23) do not hold for 3. Nevertheless, the unique solution for RIEP(3) is the
nonnegative matrix 2
4 Uniqueness of nonnegative solutions
When considering uniqueness of nonnegative solutions for RIEP(n), observe that
it is possible that RIEP(n) does not have a unique solution but does have a unique
nonnegative solution, as is demonstrated by the following example.
Example 19 Let
and let
hi
"0
"1
By Theorem 2, there is no unique solution for RIEP(2). Indeed, the solutions for
RIEP(2) are all matrices of the form
a \Gammaa
Clearly, the zero matrix is the only nonnegative solution for RIEP(2).
Observe that, unlike in Theorem 2, the existence of a unique nonnegative solution
for RIEP(n) does not necessarily imply the existence of a unique nonnegative
solution for RIEP(n-1), as is demonstrated by the following example.
Example 20 Let
and let
hi
"0
Observe that all matrices of the form
a a
solve RIEP(2), and hence there is no unique nonnegative solution for RIEP(2).
However, the only nonnegative solution for RIEP(3) is the matrix6 4
We remark that one can easily produce a similar example with nonnegative vectors
In order to introduce necessary conditions and sufficient conditions for uniqueness
of nonnegative solutions for RIEP(n) we prove
Lemma and assume that B forms a nonnegative solution for
satisfying (15)-(18). Then there exist unique nonnegative vectors x,
y and z such that the matrix
solves RIEP(n) if and only if either
l n;n r n;n 6= 0, or s l n is a unisign vector with no zero components, or
is a unisign vector with no zero components.
Proof. We follow the proof of Theorem 6. Consider the four cases in that proof.
In Case 1, the vector x is uniquely determined and any nonnegative assignment
for y is valid as long as
l n;n
nonnegative vector
sufficiently small will do. If s as is shown in the proof of Theorem 6,
we can find a positive y such that z ? 0, and by continuity arguments there exist
infinitely many such vectors y. If s a unique such y exists if and only
if there exists a unique nonnegative vector y such that ~ l T
l n;n
l n has
a nonpositive component then every vector y whose corresponding component
is positive and all other components are zero solves the problem. On the other
hand, if ~ l n ? 0, which is equivalent to saying that l n is a unisign vector with no
zero components, then the only nonnegative vector y that solves the problem is
Similarly, we prove that, in case 2, a unique nonnegative solution exists
if and only if s is a unisign vector with no zero components. We
do not have uniqueness in Case 3 since then z can be chosen arbitrarily. Finally,
there is always uniqueness in Case 4.
Lemma 21 yields sufficient conditions and necessary conditions for uniqueness
of nonnegative solutions for RIEP(n). First, observe that if s l n is a
unisign vector with no zero components, or if s is a unisign vector
with no zero components, then the zero matrix is the only nonnegative solution
of the problem. A less trivial sufficient condition is the following.
Corollary 22 Let n - 2, and let A be a nonnegative solution for RIEP(n). If
Ahn-1i forms a unique nonnegative solution for RIEP(n-1) and if l n;n r n;n 6= 0,
then A is the unique nonnegative solution for RIEP(n).
Necessary conditions are given by the following
Corollary 23 Let n - 2. If there exists a unique nonnegative solution for
RIEP(n) then either l n;n r n;n 6= 0, or s l n is a unisign vector with no
zero components, or s is a unisign vector with no zero components.
The condition l n;n r n;n 6= 0 is not sufficient for the uniqueness of a nonnegative
solution for RIEP(n), as is shown in the following example.
Example
and let
hi
"0
Although we have l n;n r n;n 6= 0, all matrices of the
a a 0
a a 07solve RIEP(3), and hence there is no unique nonnegative solution for RIEP(3).
5 The Z-matrix and M-matrix case
A real square matrix A is said to be a Z-matrix if it has nonpositive off-diagonal
elements. Note that A can be written as ff is a real number
and B is a nonnegative matrix. If we further have that ff - ae(B) then we say
that A is an M-matrix.
In this section we discuss Z-matrix and M-matrix solutions for RIEP(n) over the
field IR of real numbers. The proofs of the results are very similar to the proofs
of the corresponding results in Sections 3 and 4 and, thus, are omitted in most
cases.
Theorem 25 Let n - 2. There exists a Z-matrix solution for RIEP(n) if and
only if there exists a Z-matrix solution B for RIEP(n-1)
sn ~ rn
rn;n
rn;n
and 8
l n;n
l n;n
Furthermore, if l n or r n is positive then a Z-matrix solution for RIEP(n) is an
M-matrix if and only if s n - 0.
Proof. The proof of the first part of the theorem is similar to the proof of Theorem
6, observing that here the vectors x and y are required to be nonnegative and that
the sign of z is immaterial. The proof of the second part of the Theorem follows,
similarly to Proposition 9, from the known fact that a positive eigenvector of a
Z-matrix corresponds to the least real eigenvalue.
Theorem 26 Let n - 2. Let A 2 IR n;n be a Z-matrix, let s be the
least real eigenvalues and the corresponding left and right eigenvectors of Ahii,
respectively, and assume that
defined as in (11) and (12). Then
For the numbers M r
and m l
, defined in Corollary 17, we have
Theorem 27 Assume that the vectors l are all positive and
that the numbers s are all positive. If we have
and
then there exists a (unique) M-matrix solution A for RIEP(n).
Theorem 28 Let n - 2, let A be a Z-matrix solution for RIEP(n) and assume
that Ahn-1i forms a unique Z-matrix solution for RIEP(n-1). Then A is the
unique Z-matrix solution for RIEP(n) if and only if l n;n r n;n 6= 0.
Here too, unlike in Theorem 2, the existence of a unique Z-matrix solution for
RIEP(n) does not necessarily imply the existence of a unique Z-matrix solution
for RIEP(n-1), as is demonstrated by the following example.
Example 29 Let s
hi
"0
"1
Observe that all matrices of the form
a \Gammaa
solve RIEP(2), and hence there is no unique Z-matrix solution for RIEP(2).
However, it is easy to verify that the zero matrix is the only Z-matrix solution
for RIEP(3).
6 The real symmetric case
The inverse eigenvalue problem for real symmetric matrices is well studied, see
e.g. [3]. In this section we consider symmetric solutions for RIEP(n) over the
field IR of real numbers. We obtain the following consequence of Theorem 2,
characterizing the real symmetric case.
Theorem 2. There exists a symmetric solution for RIEP(n) if
and only if there exists a symmetric solution B for RIEP(n-1) such that the
implications (1) and (2) hold, and
l n;n r n;n 6= 0 =) (s n I
~ l n
l n;n
~
r n;n
Furthermore, if there exists a unique symmetric solution for RIEP(n) then l n;n 6=
or r n;n 6= 0.
Proof. Let A 2 IR n;n . Partition A as in (3), and so A solves RIEP(n) if and only
solves RIEP(n-1) and (4)-(7) hold. It was shown in the proof of Theorem 2
that (4)-(7) are solvable if and only if (1) and (2) hold. Therefore, all we have
to show that if B is symmetric then we can find solutions x, y and z for (4)-(7)
such that only if (26) holds. We go along the four cases discussed in
Theorem 2. In Case 1, the vector x is uniquely determined and the vector y can
be chosen arbitrarily. Therefore, in this case we set y = x, and z is then uniquely
determined. In Case 2, the vector y is uniquely determined and the vector x can
be chosen arbitrarily. Thus, in this case we set y, and z is then uniquely
determined. In Case 3, we can choose any x and y as long as x T ~ r
In particular, we can choose Furthermore, z can be chosen
arbitrarily. Finally, in Case 4, we have only if (26) holds. Note that
this is the only case in which, under the requirement that the vectors x,
y and z are uniquely determined.
We remark that, unlike in Theorem 2, the existence of a unique symmetric solution
for RIEP(n) does not necessarily imply the existence of a unique symmetric
solution for RIEP(n-1), as is demonstrated by the following example.
Example
and let
hi
"1
l 4 =6 6 610
\Gamma17 7 7:
It is easy to verify that all symmetric matrices of the form61 1 a
a a b7
solve RIEP(3), while the unique solution for
This example also shows that there may exist a unique solution for RIEP(n) even
if l
Naturally, although not necessarily, one may expect in the symmetric case to
have the condition
Indeed, in this case we have the following corollary of Theorems 2 and 30.
Corollary assume that (27) holds. The following are equivalent

(i) There exists a symmetric solution for RIEP(n).
(ii) There exists a solution for RIEP(n).
(iii) There exists a symmetric solution B for RIEP(n-1) such that (1) holds.
(iv) There exists a solution B for RIEP(n-1) such that (1) holds.
Proof. Note that since (27) holds, we always have (26). We now prove the
equivalence between the four statements of the theorem.
(i) =) (ii) is trivial.
(ii) =) (iv) by Theorem 2.
(iv) =) (iii). Since (27) holds, it follows that B+B Talso solves RIEP(n-1).
(iii) =) (i). Since B is symmetric and since we have (27), the implications (1)
and (2) are identical. Our claim now follows by Theorem 30.
For uniqueness we have
Theorem 33 Let n - 2 and assume that (27) holds. The following are equivalent

(i) There exists a unique symmetric solution for RIEP(n).
(ii) There exists a unique solution for RIEP(n).
(iii) We have l i;i 6= 0;
Proof. In view of (27), the equivalence of (ii) and (iii) follows from Theorem 4.
To see that (i) and (iii) are equivalent note that, by the construction in Theorem
30, for every symmetric solution B for RIEP(n-1) there exists a solution A for
RIEP(n) such that Furthermore, A is uniquely determined if and
only if l n;n 6= 0. Therefore, it follows that there exists a unique symmetric solution
for RIEP(n) if and only if there exists a unique symmetric solution for
and l n;n 6= 0. Our assertion now follows by induction on n.
We conclude this section remarking that a similar discussion can be carried over
for complex Hermitian matrices.
7 The positive semidefinite case
In view of the discussion of the previous section, it would be interesting to find
conditions for the existence of a positive (semi)definite real symmetric solution
for RIEP(n). Clearly, a necessary condition is nonnegativity of the numbers s i
n. Nevertheless, this condition is not
sufficient even if a real symmetric solution exists, as is demonstrated by the
following example.
Example 34 Let
and let
hi
"1
The unique solution for RIEP(3) is the symmetric matrix6 4
which is not positive semidefinite.
The following necessary and sufficient condition follows immediately from Theorem
4.
Theorem assume that (27) holds. Assume, further, that r i;i 6=
n. Then the unique solution for RIEP(n) is positive semidefinite
[positive definite] if and only if S n ffi (R T
positive semidefinite [positive
definite].
Remark 36 By Theorem 33, in the case that r we do not have
uniqueness of symmetric solutions for RIEP(n). Hence, if there exists a symmetric
solution for RIEP(n) then there exist at least two different such solutions A and
B. Note that A a symmetric solution for RIEP(n) for
every real number c. It thus follows that in this a case it is impossible to have
all solutions for RIEP(n) positive semidefinite. Therefore, in this case we are
looking for conditions for the existence of some positive semidefinite solution for
RIEP(n).
The following necessary condition follows immediately from Proposition 3.
Theorem 37 Let n - 2 and assume that (27) holds. If there exists a positive
semidefinite real symmetric solution for RIEP(n) then S n ffi (R T
positive
semidefinite.
In order to find sufficient conditions for the existence of a positive semidefinite
solution for RIEP(n), we denote by oe(A) the least eigenvalue of a real symmetric
matrix A.
Lemma 38 Let n - 2 and assume that (27) holds. Assume that there exists a
symmetric solution A for RIEP(n) such that oe(Ahn-1i) ? s n . If r n 6= 0 then
Proof. Since r n 6= 0 it follows that s n is an eigenvalue of A. Assume that
It follows that A has at least two eigenvalues smaller than or equal to
s n . By the Cauchy Interlacing Theorem for Hermitian matrices, e.g. [8, Theorem
4.3.8, p. 185], it follows that oe(Ahn-1i) - s n , which is a contradiction. Therefore,
we have
Corollary assume that (27) holds. If r i 6= 0 for all i,
then every real symmetric solution A for
RIEP(n) is positive semidefinite. If s n ? 0 then every real symmetric solution
for RIEP(n) is positive definite.
Proof. Note that Using Lemma 38 repeatedly
we finally obtain implying our claim.
Remark 40 In view of Remark 36, it follows from Corollary 39 that if r i 6= 0
for all i and if
has a unique (positive semidefinite) solution.
The converse of Corollary 39 is, in general, not true. That is, even if every real
symmetric solution for RIEP(n) is positive semidefinite we do not necessarily
have as is demonstrated by the following example.
Example
and let
hi
"1
The unique solution for RIEP(3) is the positive definite matrix
Nevertheless, we do not have s 1 - s 2 .
We conclude this section with a conjecture motivated by Theorems 35 and 37.
One direction of the conjecture is proven in Theorem 37.
Conjecture 42 Let n - 2 and assume that (27) holds. Then there exists a
positive semidefinite [positive definite] real symmetric solution for RIEP(n) if
and only if S n ffi (R T
positive semidefinite [positive definite].
8 The Stieltjes matrix case
In this section we combine the results of the previous two sections to obtain
analogous results for Stieltjes matrices, that is, symmetric M-matrices.
The following theorem follows immediately from Theorems 30 and 25.
Theorem 43 Let n - 2. There exists a symmetric Z-matrix solution for
RIEP(n) if and only if there exists a symmetric Z-matrix solution B for
satisfying 8
sn ~ rn
rn;n
rn;n
l n;n
l n;n
and
l n;n r n;n 6= 0 =) (s n I
~ l n
l n;n
~
r n;n
Furthermore, if l n or r n is positive then a symmetric Z-matrix solution for
RIEP(n) is a Stieltjes matrix if and only if s n - 0.
Corollary 44 Let n - 2, and assume that the vectors l i , are all
positive and that (27) holds. There exists a symmetric Z-matrix solution A
for RIEP(n) if and only if there exists a symmetric Z-matrix solution B for
satisfying s n ~
. The solution A is a Stieltjes matrix if and
only if s n - 0.
The following nonrecursive sufficient condition from Theorem 27.
Theorem assume that the vectors l i , are all
positive, that (27) holds, and that the numbers s are all positive. If we
have
then there exists a (unique) Stieltjes matrix solution A for RIEP(n).
Proof. By Theorem 27 there exists a unique M-matrix solution A for RIEP(n).
Since A T also solves the problem, it follows that A = A T and the result follows.
9 The inverse M-matrix case
It is well known that for a nonsingular M-matrix A we have A
ingly, a nonnegative matrix A is called inverse M-matrix if it is invertible and
A \Gamma1 is an M-matrix. An overview of characterizations of nonnegative matrices
that are inverse M-matrices can be found in [9].In this section we discuss, as a
final special case, inverse M-matrix solutions for RIEP(n).
The following theorem follows immediately from two results of [9].
Theorem 46 Let A 2 IR n;n be partitioned as in (3). Then A is an inverse M-matrix
if and only if B is an inverse M-matrix and
and
for the diagonal entries: (31)
Proof. By Corollary 3 in [9], if A is an inverse M-matrix then B is an inverse
M-matrix. By Theorem 8 in [9], if B is an inverse M-matrix then A is an inverse
M-matrix if and only if (28)-(31) hold. Our claim follows.
The next result gives necessary and sufficient recursive conditions for the existence
of an inverse M-matrix solution for RIEP(n).
Theorem 2. There exists an inverse M-matrix solution for RIEP(n)
if and only if s n ? 0 and there exists an inverse M-matrix solution B for
satisfying 8
N~rn
rn;n
l n;n
l n;n r n;n 6= 0 =)
l n;n r n;n
and, except for the diagonal entries,
l n;n r n;n 6= 0 =) s n
l n;n r n;n
l n;n r n;n
Proof. As in the proof of Theorem 2, partition A as in (3). If A is an inverse M -
matrix solution for RIEP(n) then, as is well known, its eigenvalues lie in the open
right half plane, and so the real eigenvalue s n must be positive. Furthermore,
by Theorem 46, B is an inverse M-matrix and (28)-(31) hold. Finally, we have
(4)-(7). Distinguish between four cases:
1. r Here x is given by (8), and so it follows from (29) that
l n;n
Theorem 2 we have B~r implying that N ~
2. l Here y is given by (9), and so it follows from (28) that
N~rn
rn;n
Theorem 2 we have ~ l T
3. l Similarly to the previous cases prove that N ~
4. l n;n 6= 0; r n;n 6= 0. Here x is given by (8), y is given by (9), and z is given
by (10). It follows from (28) that N~rn
rn;n
- 0, and from (29) that ~ l T
l n;n
- 0. It
follows from (30) that
l n;n r n;n
l n;n
r n;n
l n;n r n;n
0:
now follows that ~ l T
l n;nrn;n
! 1. Finally, it follows from (31)
that, except for the diagonal entries,
l n;n r n;n
r n;n
l n;n
l n;n r n;n
We have thus proven that if A is an inverse M-matrix solution for RIEP(n)
then is an inverse M-matrix solution B for RIEP(n-1) satisfying
(32)-(35).
Conversely, assume that s n ? 0 and B is an inverse M-matrix solution B for
satisfying (32)-(35). We show that x, y and z can be chosen such
that (28)-(31) hold, and so by Theorem 46, A is an inverse M-matrix. Here too
we distinguish between four cases:
1. r Here x is given by (8), and by (33) we obtain (29). Note
that y can be chosen arbitrarily, and and z should be chosen such that (7)
holds. If we choose It follows that
so we also have (30). Finally, since
is an M-matrix, it follows that (31) holds (except for
the diagonal entries).
2. l Here y is given by (9), and by (32) we obtain (28). The
vector x can be chosen arbitrarily, so we choose The proof follows
as in the previous case.
3. l should be chosen such that x T ~
and z can be chosen arbitrarily. We choose and the proof follows.
4. l n;n 6= 0; r n;n 6= 0. Here x is given by (8), y is given by (9), and z is given
by (10). By (32) and (33) we obtain (28) and (29) respectively. Finally,
similarly to the corresponding case in the proof of the other direction, (34)
implies (30) and (35) implies (31).
Note that Conditions (32)-(33) imply immediately Conditions (16)-(17) by multiplying
the inequality by the nonnegative matrix B. This is not surprising, since
an inverse M-matrix is a nonnegative matrix. The converse, however, does not
hold in general. The following example shows that although (16)-(17) is satisfied,
(32)-(33) do not hold.
Example 48 Let
and let
hi
0:5257
0:8507
0:3859
0:91267
The unique solution for RIEP(3) is the nonnegative matrix
A =6 4
which is not an inverse M-matrix since
A
1:6429 \Gamma1:5714 0:4286
\Gamma1:5714 2:2857 \Gamma0:7143
0:4286 \Gamma0:7143 0:2857
Indeed, the unique nonnegative solution
for RIEP(2) satisfies (16),
as
2:8673
8:2024
However, B does not satisfy (32), since the vector
\Gamma1:3688
2:2816
is not nonnegative.



--R

Generalized Matrix Inverses: Theory and Applications
Nonnegative Matrices in Mathematical Sci- ences
A survey of matrix inverse eigenvalue problems
The spectra of non-negative matrices via symbolic dynamics
On an inverse problem for nonnegative and eventually nonnegative matrices

On some inverse problems in matrix theory
Matrix Analysis


Inverse eigenvalue problems for matrices
A note on an inverse problem for nonnegative matrices
Nonnegative matrices whose inverses are M-matrices
Note on an inverse characteristic value problem
--TR

--CTR
Fan-Liang Li , Xi-Yan Hu , Lei Zhang, Left and right inverse eigenpairs problem of skew-centrosymmetric matrices, Applied Mathematics and Computation, v.177 n.1, p.105-110, 1 June 2006
m-matrices;recursive solution;stieltjes matrices;inverse eigenvalue problem;inverse M-matrices;hermitian matrices;nonnegative matrices;z-matrices