Prove this matrix has a noreal eigenvalue.

Question

$A_{n\times n}$ is a 0-1 entries matrix with constant row sum $k>0$, its principal minor of order $2$ can't be $$\left|\begin{matrix} 0 & 1\\1&0\end{matrix}\right|$$and $A_{ii}=0$ for $1\leq i\leq n$. Prove that $A$ has a noreal eigenvalue.

Answer 1

The basic ideas are contained in the thread "Prove that a polynomial has at least one nonreal complex root". In the current question, the condition about principal minors merely adds another layer of obscurity.

Let $p(x)=x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0$ be the characteristic polynomial of $A$. Then:

• Some $c_j$ is nonzero as $k>0$ is an eigenvalue of $A$ (with $A\mathbf1=k\mathbf1$).
• $c_{n-1}=-\operatorname{tr}(A)$ is zero as $A$ has a zero diagonal.
• $c_{n-2}$ must also be zero. As $A$ is a $0$-$1$ matrix with a zero diagonal, each of its $2\times2$ principal minor is either $\left|\begin{matrix}0&1\\ 1&0\end{matrix}\right|$ or $0$. However, the former is impossible by assumption. Therefore all $2\times2$ principal minors of $A$ are zero. Since $c_{n-2}$ is their sum, we obtain $c_{n-2}=0$.

It follows that $p(x)=x^n+\sum_{j=0}^mc_jx^j$ for some $m\le n-3$ with $c_m\ne0$. Therefore $$ p^{(m)}(x)=\frac{n!}{(n-m)!}x^{n-m}+m!c_m $$ has at most $2$ real roots. In turn, $p^{(m-1)}(x)$ has at most $3$ real roots, $p^{(m-2)}(x)$ has at most $4$ real roots,... and $p(x)$ has at most $m+2$ real roots. Yet, $m+2<n$. So, $p$ must possess a non-real root.