Proving that a certain non-symmetric matrix has an eigenvalue with positive real part

Question

Suppose that

• $X$ is the $n \times n$ matrix of all ones
• $Y$ is an arbitrary $n \times n$ matrix with zeroes on the diagonal and all other entries equal to $0$ or $1$
• $0 < \delta < 1$

Let $Z = -X - \delta Y$. If $Y$ has any ones, then does $Z$ have an eigenvalue with positive real part?

This question is based on the observations that:

1. if $Y$ is the matrix of all zeroes, then $Z$ has eigenvalues $0$ (with multiplicity $n-1$) and $-n$

2. if $Y$ is the matrix of all ones (besides the diagonal entries, which are all zero), then $Z$ has eigenvalues $\delta$ (with multiplicity $n-1$) and $(-1-\delta)n+\delta$.

3. If $Y$ is symmetric, then $Z$ has a positive eigenvalue if and only if $Z$ is not negative semidefinite. So $Z$ has a positive eigenvalue if $Y$ has any ones and is symmetric.

Is there a way to answer the question above when $Y$ is not symmetric?

Update 2017/02/24: I solved this problem using the Collatz-Weilandt formula. My proof is posted as an answer below.

Update 2017/02/14: The approach below is based on the suggestions about Lyapunov inequalities in Rodrigo de Azevedo's answer. This problem is still open, unless the answer to the question below is yes.

Suppose that the matrix $Y$ has some entry equal to $1$. Then $Z+Z^{T}$ has an eigenvalue with positive real part. In order to prove that $Z$ has an eigenvalue with positive real part, suppose for contradiction that all eigenvalues of $Z$ have nonpositive real parts.

By symmetry, all eigenvalues of $Z^{T}$ have nonpositive real parts, so both $Q = Z-\epsilon I$ and $Q^{T} = Z^{T}-\epsilon I$ have eigenvalues with strictly negative real parts. Thus there exist sets $A$ (resp. $B$) of symmetric positive definite matrices $X$ (resp. $Y$) such that $Q^{T} X + X Q < 0$ and $Q Y + Y Q^{T} < 0$.

Is it true that $A \cap B \neq \emptyset$?

If this is true, then it would imply that there exists $X \in A \cap B$ such that $(Q+Q^{T}) X + X (Q+Q^{T}) < 0$, i.e., $(Z+Z^{T}-2\epsilon I) X + X (Z+Z^{T}-2\epsilon I) < 0$. So all eigenvalues of $Z+Z^{T}-2\epsilon I$ would have negative real parts, which contradicts the original assumption that $Z+Z^{T}$ has an eigenvalue with positive real part if we choose $\epsilon$ sufficiently small.

Answer 1

In the case $n=3$, try $Y = \pmatrix{0 & 0 & 0\cr 0 & 0 & 1\cr 1 & 0 & 0\cr}$. The characteristic polynomial of $Z$ is $\lambda^3+3 \lambda^2-2 \delta \lambda+\delta^2= \lambda^3 + 2 \lambda^2 + (\lambda - \delta)^2$, which has no positive real roots for any real $\delta$.

Answer 2

Suppose we are given $\mathrm M \in \mathbb R^{n \times n}$. Stating that all the eigenvalues of $\mathrm M$ have strictly negative real parts is equivalent to stating that there is a symmetric positive definite $\mathrm X$ such that the Lyapunov linear matrix inequality (LMI)

$$\mathrm M^{\top} \mathrm X + \mathrm X \, \mathrm M \prec \mathrm O_n$$

holds. In other words, the open spectrahedron defined by the Lyapunov LMI above is non-empty if and only if all the eigenvalues of $\mathrm M$ have strictly negative real parts.

Thus, if the following semidefinite program (SDP) is infeasible

$$\begin{array}{ll} \text{minimize} & \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & \begin{bmatrix} \mathrm X & \mathrm O_n\\ \mathrm O_n & -\mathrm M^{\top} \mathrm X - \mathrm X \, \mathrm M\end{bmatrix} \succeq \mathrm O_{2n}\end{array}$$

then $\mathrm M$ has at least one eigenvalue with nonnegative real part.

Answer 3

Suppose that $Y_{ij} = 1$ for some $i, j$. Construct a vector $x$ with $n$ coordinates such that $x_t = 1+\frac{\delta}{n}$ if $t = i$ and $x_t = 1$ otherwise.

Note that $\frac{(-Zx)_t}{x_t} > n$ for each $1 \leq t \leq n$. By the Collatz-Weilandt formula, the Perron-Frobenius eigenvalue of $-Z$ exceeds $n$.

Since the trace of $-Z$ is $n$, the sum of the eigenvalues of $-Z$ is $n$. Thus $-Z$ has an eigenvalue with negative real part, so $Z$ has an eigenvalue with positive real part.