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.



Proving that a certain non-symmetric matrix has an eigenvalue with positive real part
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.


