Minimum negative eigenvalue of zero-one matrices

For $n$ fixed, what is the most negative eigenvalue among all trace zero zero-one matrices (that is, all entries are either zero or one, and all diagonal entries are zero) of size $n$?

By most negative eigenvalue, I mean the least (that is, biggest absolute value) among the negative eigenvalues (if any).

There is an obvious candidate. Let $A_n$ be the $n\times n$ matrix whose entries are $1$ in the $(i,j)$ position whenever $i+j$ is odd, and zero otherwise. This is rank two, trace zero, and it is easy to see that its two nonzero eigenvalues are $\{ \pm n/2\}$ if $n$ is even, and $\{ \pm\sqrt{n^2-1}/2\}$ if $n$ is odd.

Not only do I expect that the most negative value is $-n/2$ if $n$ is even and $-\sqrt{n^2-1}/2$ if $n$ is odd, but I also expect that if $B$ is a trace zero zero-one $n \times n$ matrix whose most negative eigenvalue achieves this bound, then $B$ is permutation conjugate to $A_n$.

This is trivial for $n=2$, easy for $n=3$, and requires a Cayley-like$^*$ argument for $n=4$, which I actually didn't complete (except in the symmetric case).

When $n$ is even, $A_n$ is the adjacency matrix of the complete bipartite graph with $n$ vertices, so I expect this type of question (most negative eigenvalue of a symmetric zero-one matrix) has been answered for symmetric matrices (which of course correspond to undirected graphs).

Anyway, I am looking for a reference for this problem (and if my expectations are false, I'd like to know that too).

$*$ Cayley-like means substituting for each variable, and in this case, finding the smallest root—but not directly, but by finding the smallest $\alpha >0$ to arrange that the determinant of $I + \alpha B$ is zero. For $n=4$, this means minimizing a fairly simple polynomial in twelve variables, many of which turn out to be zero. This refers to Cayley's delightfully naive proof of what we call the Cayley-Hamilton theorem.

Edit To summarize—after hectic soul-searching—the conjectured result (complete with the identification of the optimal choices) is true (even without the trace zero hypothesis), with an elegant argument given in Christian's answer, based on Brendan's now-deleted answer. A rather surprising consequence (at least to me) is given near the bottom of my answer.

• By "most negative" do you mean "most negative real part", or do you mean "most negative real"? If you're not assuming the matrix is symmetric, there can be complex eigenvalues. – Robert Israel May 18 '16 at 1:07
• I mean the least among the negative eigenvalues; I will edit accordingly. – David Handelman May 18 '16 at 1:26
• Although it's probably true that most negative real part would yield exactly the same matrix. – David Handelman May 18 '16 at 1:29
• @BrendanMcKay: What happened to your answer? I thought it was convincing, or am I missing something. – Christian Remling May 19 '16 at 1:21
• @Christian, Brendan deleted his answer, noting, " I am deleting this because there is currently too much nonsense and I don't see a simple way to fix it. This is ok for symmetric matrices, but those are too easy." – Gerry Myerson May 19 '16 at 2:44

I wish to repost Brendan's answer temporarily, which I believe clarified matters completely and in an easy and elegant way, until Brendan undeletes his own version or someone explains to me what I'm missing here.

Let $A$ be an arbitrary $01$ matrix, with smallest (real) eigenvalue $\lambda_-(A)$ and associated normalized eigenvector $v\in\mathbb R^n$. Let's also assume that $v_j\le 0$ for $j=1,\ldots , k$ and $v_j>0$ for $j>k$.

Now to minimize $\langle v, Bv\rangle$ for this $v$ over all $01$ matrices $B$, we must make $(Bv)_j$ as large as possible for $1\le j\le k$ and as small as possible for $j>k$. Clearly, this happens for $$B= \begin{pmatrix} 0_{kk} & 1\\1& 0_{n-k,n-k}\end{pmatrix} \quad\quad\quad\quad (1)$$ Luckily for us, $B$ happens to be symmetric, so $$\lambda_-(A) = \langle v, Av\rangle \ge \langle v, Bv\rangle \ge \lambda_-(B) .$$

In other words, it suffices to restrict our search to matrices of the form (1). We observe that $(1,0)^t$, $(0,1)^t$ are both eigenvectors of $B^2$ with eigenvalue $k(n-k)$. Since $B$ has rank $2$ and trace zero, this implies that the eigenvalues of $B$ are $\pm \sqrt{k(n-k)}$. Finally, we maximize this over $k$ to obtain the claim.

• This looks pretty good (shorter than the arguments in my answer). And the same method works if zero-one is replaced by nonnegative with entries bounded by $1$ (a compactness argument would work, but it can be done without one). It is an explanation of Brendan's answer, rather than a repost. – David Handelman May 19 '16 at 23:33
• @David and Christian, thanks for this. I since moved countries (temporarily) and didn't have time to look carefully. My concern about my answer is that it seems to be that a pair of complex eigenvalues with large negative real part might mimic a real negative eigenvalue that doesn't actually exist. How do you know that being able to make $\langle B, Bv\rangle$ smaller indicates the presence of a smaller real eigenvalue? To suggest the answer, maybe it is because the matrix turns out to be symmetric and so all is well in retrospect (but how to write that formally?). – Brendan McKay May 20 '16 at 11:44
• @BrendanMcKay: Yes, exactly, $B$ is symmetric, so all eigenvalues are real. – Christian Remling May 20 '16 at 16:24

I think the key idea in Brendan's argument is contained in the following.

Lemma. Let $\begin{pmatrix} A & B \\ C & D \end{pmatrix}$ be a block partition of a nonnegative-entried matrix $M$ (where $A$ is $k \times k$, $B$ is $k \times l$, $C$ is $l \times k$, and $D$ is $l \times l$), and let $\lambda$ be a negative eigenvalue of $M$ with an eigenvector of the form $z = (-x,y)^T$ corresponding to the matrix partition, where $x$ is strictly positive and $y$ is nonnegative. Then the matrix $\begin{pmatrix} 0 & B \\ C & 0 \end{pmatrix}$ has an eigenvalue $-\sqrt{\rho(BC)}$ and this is at least as negative as $\lambda$.

Proof $Mz = \lambda z$ yields the equations $-Ax + By = -\lambda x$ and $-Cx + Dy = \lambda y$. Thus $By = Ax + |\lambda| x$ and $Cx = Dy + |\lambda | y$; multiplying the latter by $B$ from the left, we obtain \eqalign{ BCx & = BDy + |\lambda |By \cr & = BDy + |\lambda| Ax + |\lambda|^2 x\cr &\geq \lambda^2 x. } Since $x$ is not zero and nonnegative and $BC$ is nonnegative, we have that $\rho(BC) \geq \lambda^2$ (otherwise powers of $BC/\lambda^2$ will simultaneously converge to zero, and not converge to zero; $\rho$ denotes the spectral radius).

Now $\begin{pmatrix} 0 & B \\ C & 0 \end{pmatrix}$ has $\pm\sqrt {\rho(BC)}$ among its eigenvalues, in particular, the negative one is at least as negative as $\lambda$.\qed

When $M$ is zero-one, the biggest possible spectral radius for $BC$ (or what amounts to the same thing, $CB$) occurs when all the entries of each of $B$ and $C$ are one and the partition is as equal as possible (exactly as in Brendan's proof), and this is strict (in the sense that if at least one entry of $B$ or $C$ is less than one, the spectral radius is strictly less than the maximum). The resulting off-diagonal block matrix is permutation-equivalent to $A_n$.

{\bf Edit.} Now it is easy to get the full result, that is, $A$ and $D$ must be zero; from the proof above, $BC x \geq |\lambda|^2x + |\lambda|Ax$; but now $BC$ is primitive and its spectral radius is $\lambda^2$. This forces $x$ to be the right Perron eigenvector of $BC$, so $Ax$ is zero. But $x$ is strictly positive and $A$ is nonnegative, so $A$ is zero. A similar argument with $CB$ shows that $y$ is its right Perron eigenvector (it must be nonzero, since both signs must occur in $z$), so is strictly positive, and then the corresponding equations yield $Dy$ is zero, so $D$ is zero.

There is an interesting consequence, since the lemma applies to nonnegative matrices, not just zero-one. Let $r(n)$ denote $n/2$ if $n$ is even, and $\sqrt{n^2-1}/2$ if $n$ is odd.

Theorem Let $N$ vary over all nonnegative-entried $n\times n$ matrices with maximal entry at most $1/r(n)$ (that is, $2/n$ if $n$ is even, slightly bigger if $n$ is odd). Then ${\rm det}(I+N) > 0$, except if $N\cdot r(n)$ is permutation-conjugate to $A_n$.

The argument for this just uses the preceding result, the mean value theorem, and convexity of the domain.

In particular, $I +N$ is invertible, except for $n \choose {[n/2]}$ choices of $N$ (I think that's how many permutation conjugates of $A_n$ there are). Using the usual operator norm techniques, we would only get the result if $1/r(n)$ is shrunk to less than $1/n$, roughly one half of $1/r(n)$.

Obviously, the lemma is based on Brendan's idea of looking at the block matrix form.

But I still suspect that all of these results are in the (old) literature.

If $\lambda$ is the smallest real eigenvalue of $A$ and $v$ is an associated normalized eigenvector, then $$\lambda = \langle v, Av\rangle = \frac{1}{2}\left( \langle v, Av\rangle + \langle A^* v, v\rangle \right) = \langle v, Bv \rangle, \quad\quad B=\frac{1}{2}(A+A^*) ,$$ so we can restrict our attention to symmetric matrices.

For symmetric matrices with even $n$, there's a simple argument: Let $N$ be the number of $1$'s in our matrix. Then the largest eigenvalue satisfies $\lambda_+\ge \langle v, Av\rangle = N/n$, if we take the normalized version of the vector with all $1$'s. Also, the smallest eigenvalue $\lambda_-$ clearly satisfies $|\lambda_-|\le \lambda_+$ (take absolute values in the eigenvector for $\lambda_-$ and test $A$ on this vector).

Now $\lambda^2_-+\lambda_+^2\le \|A\|_2^2 = N$ (the Hilbert-Schmidt norm), so $\lambda_-^2 \le N-N^2/n^2$, and this becomes maximal at $N=n^2/2$, so $\lambda_-=-n/2$ is best possible, as suspected.

Here we never use that $\textrm{tr } A=0$, so in this situation at least, the claim holds without this assumption.

• Just a comment: $|\lambda_-| \leq \lambda_+$ by Perron. Doesn't your argument work somewhat more generally, when all the eigenvalues are real (or a bit more generally, when all the nonreal eigenvalues have nonnegative real parts)? This will guarantee that ${\rm tr } A^2 \geq \lambda_-^2 + \lambda_+^2$ ... – David Handelman May 18 '16 at 2:46
• Perhaps, but I'm not sure (I do use min-max for the lower bound on $\lambda_+$), and in any event, "symmetric" is a natural assumption. By the way, if $n$ is odd, then the same argument gives your conjectured optimal value $\times (1+1/n^2)^{1/2}$, so at least it's close. – Christian Remling May 18 '16 at 2:52

I wish to discuss or clarify here the answers given previously.

Christian's answer fails to work for non-symmetric matrices, because then the inequality $\lambda_+\ge\frac Nn$ is deadly false. Take for instance a strictly triangular matrix, where all the spectrum is made of zeroes!

Brendan's argument becomes more natural if we think to perron-Frobenius Theorem. Because $A$ is non-negative, we know that every eigenvalue $\lambda$ satisfies $|\lambda|\le\rho(A)=\lambda_+$. If we are looking for the most possibly negative eigenvalue, it is therefore natural to investigate the case where $\lambda_-=-\rho(A)$ (but this is a meta-argument). By restricting to a diagonal block of smaller size, and up to a permutational conjugation, we may always assume that $A$ is irreducible. Then the property $\lambda_-=-\rho(A)$ implies (see for instance my book Matrices, GTM 216, Springer-Verlag) that $A$ is permutationally similar to a bloc-circulant matrix. Let us consider the case of a $2\times2$-blockwise matrix $$\begin{pmatrix} 0_p & B \\ C & 0_q \end{pmatrix},$$ where we have $-\lambda_-=\lambda_+=\sqrt{\rho(BC)}$. Involving again the PFT, the spectral radius of a non-negative matrix is entrywise monotone non-decreacreasing (actually strictly increasing because of irreducibility). Hence $\rho(BC)$ is maximal when $B={\bf1}_p\otimes{\bf1}_q$ and $C={\bf1}_q\otimes{\bf1}_p$. This choice gives $\rho(BC)=pq$. Because of $p+q=n$, the maximal value of $pq$ is either $\frac{n^2}4$ or $\frac{n^2-1}4$, giving the expected values $$\lambda_-=-\frac n2\quad\hbox{or }-\frac{\sqrt{n^2-1}}2\,,$$ depending on the parity of $n$.

If $A$ is $m\times m$ blockwise, then $m$ must be even, for $\lambda_-$ to be real negative, and we have $\lambda_-=-\rho(B_1\cdots B_m)^{1/m}$ where the size of teh blocks are $p_j\times p_{j+1}$ with $p_{m+1}=p_1$ and $p_1+\cdots+p_m=n$. The modulus is maximal when the $B_j$'s entries are one's, in which case we obtain $|\lambda_-|=(p_1\cdots p_m)^{1/m}$.

For the answer to be complete, there remains to prove that $\lambda_-$ must equal $-\lambda_+$ for optimality. Using the AGI, we find easily that we cannot improve the modulus by taking $m>2$.

• The final comment refers to the presumed permutation-conjugacy of any optimal example? It probably follows from the inequality $(BC -\lambda^2)x \geq BDy + |\lambda|Ax$ (but I confess I don't see how to show $A$ is zero from this; irreducibility would help, but Idon't see the reduction to a smaller case, and $A$ can have rows entirely zero). – David Handelman May 19 '16 at 8:25
• I'm getting more and more confused: What was wrong with Brendan's argument? Let me repeat my summary from above please: let $A$ be a $0-1$ matrix, and let $\lambda_-$ be its smallest (real) eigenvalue, with normalized ev $x$. Then, trivially, $\lambda_-=\langle x, Ax\rangle$. However, $\langle x, Bx\rangle\le\langle x, Ax \rangle$ for the (block) matrix $B$ that Brendan constructs by simply minimizing this quadratic form over the matrix, given $x$. Now since $B$ happens to be symmetric, $\lambda_-(B)\le \langle x, Bx\rangle$, and a computation shows that $B$ has the conjectured optimal ev. QED – Christian Remling May 19 '16 at 22:51