Let $\mathcal B\_n$ denote the set of $n\times n$ matrices with entries in $\{0,1\}$. It follows from the spectral radius formula that if $M\in\mathcal B\_n$ is not nilpotent, then $\rho(M)$, the spectral radius of $M$, is $\ge1$.


I need a condition for $\rho(M)>1$ in terms of the proportion of 1s. 


**QUESTION.** Is there a $c\in(0,1)$ such that for any $n\ge1$ and any $M\in\mathcal B\_n$ with the number of 0s less than $cn^2$ we have $\rho(M)>1$?


If so, what's the best known value of $c$?



The spectral radius of a binary matrix
[Perron-Frobenius theory](https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem) clarifies this quickly. Observe first of all that if $M$ is irreducible in the sense that it cannot be made a block upper triangular matrix by a permutation of the standard basis vectors, then $\rho(M)>1$. This follows because the Perron-Frobenius eigenvector $x$ has positive entries, and if, say, $x\_1>x\_2> \ldots >x\_n$, then $\lambda=1$ would force $M\_{1j}=0$ for $j\ge 2$, so $M$ was reducible. A similar argument works if $x\_1 = \ldots = x\_m>x\_{m+1} \ge \ldots$.


So $\rho(M)\le 1$ forces $M$ to be block upper triangular after a permutation of basis vectors and moreover the diagonal blocks must be zero or $1\times 1$ matrices (the argument in the preceding paragraph implicitly used that the matrix has size $n\ge 2$). Clearly such a matrix has $\ge (n^2-n)/2$ zeros, so any $c<1/2$ works. Moreover, we have also obtained an example with $(n^2-n)/2$ zeros and $\rho(M)=1$, so this is optimal.


