5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\rm Y$ is an adjacency matrix. Do you have information on the underlying graph? $\endgroup$ – Rodrigo de Azevedo Feb 13 '17 at 21:28
  • $\begingroup$ 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. $\endgroup$ – jtg Feb 13 '17 at 21:33
  • 1
    $\begingroup$ Why not use Lyapunov equations? $\endgroup$ – Rodrigo de Azevedo Feb 13 '17 at 21:36
  • $\begingroup$ If you see a way to answer this with Lyapunov equations, I'd be very grateful to know some more details. $\endgroup$ – jtg Feb 13 '17 at 21:39
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jtg Feb 13 '17 at 19:46
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – jtg Feb 13 '17 at 23:16
  • 1
    $\begingroup$ @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$. $\endgroup$ – Rodrigo de Azevedo Feb 13 '17 at 23:29
  • $\begingroup$ 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. $\endgroup$ – jtg Feb 13 '17 at 23:40
  • 1
    $\begingroup$ @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}$$ $\endgroup$ – Rodrigo de Azevedo Feb 13 '17 at 23:48
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.