The following question *must* have been answered decades ago.

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.

negative real partwould yield exactly the same matrix. $\endgroup$ – David Handelman May 18 '16 at 1:29