Minimum negative eigenvalue of zero-one matrices

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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