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

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.

• $\rm Y$ is an adjacency matrix. Do you have information on the underlying graph? Feb 13, 2017 at 21:28
• If $G$ is the directed graph corresponding to $Y$, then the question is to determine whether $Z$ has an eigenvalue with a positive real part if $G$ has any edges. This is the only information about the corresponding graph.
– jtg
Feb 13, 2017 at 21:33
• Why not use Lyapunov equations? Feb 13, 2017 at 21:36
• If you see a way to answer this with Lyapunov equations, I'd be very grateful to know some more details.
– jtg
Feb 13, 2017 at 21:39

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$.

• Sorry that my question was not clear enough before. By "positive eigenvalue" I meant an eigenvalue with a positive real part, not a positive real eigenvalue. This is corrected now.
– jtg
Feb 13, 2017 at 19:46

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.

• Thanks very much for explaining these details. If no such $X$ exists, then $M$ would have at least one eigenvalue with nonnegative real part. Is there a way to see that $M$ has an eigenvalue with a positive real part?
– jtg
Feb 13, 2017 at 23:16
• @jtg Use $\tilde{\mathrm M} := \mathrm M - \epsilon \mathrm I_n$ instead of $\mathrm M$, where $\epsilon > 0$ is small. If the Lyapunov LMI holds, then all the eigenvalues of $\tilde{\mathrm M}$ have negative real parts, i.e., all the eigenvalues of $\mathrm M$ have real parts strictly less than $\epsilon$. If the SDP is infeasible, then all the eigenvalues of $\mathrm M$ have real parts equal to or greater than $\epsilon$. Feb 13, 2017 at 23:29
• That's a great idea, thanks for explaining this. I'll accept this as the answer as soon as I work out the rest of the details for the matrices in my original post.
– jtg
Feb 13, 2017 at 23:40
• @jtg The LMI then becomes $$\begin{bmatrix} \mathrm X & \mathrm O_n\\ \mathrm O_n & 2 \epsilon \mathrm X -\mathrm M^{\top} \mathrm X - \mathrm X \, \mathrm M\end{bmatrix} \succeq \mathrm O_{2n}$$ Feb 13, 2017 at 23:48

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.