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

  • 1
    $\begingroup$ Wouldn't Hadamard products give that c is near 1? Gerhard "Knows Nothing About Spectral Radius" Paseman, 2017.04.23. $\endgroup$ – Gerhard Paseman Apr 23 '17 at 18:36
  • 1
    $\begingroup$ It looks like I am talking "exists" whereas the post is talking "for all". Gerhard "What A Difference Quantifiers Make" Paseman, 2017.04.23. $\endgroup$ – Gerhard Paseman Apr 23 '17 at 19:50

Perron-Frobenius theory 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.