(This is a follow-up to The spectral radius of a binary matrix)

Let $\mathcal B_n$ denote the set of $n\times n$ matrices with entries in $\{0,1\}$.

QUESTION. Is there a $\delta\in\bigl(0,\frac12\bigr), \alpha\in(0,1)$ and $b>0$ such that for any $n\ge1$ and any $M\in\mathcal B_n$ with the number of 0s less than $\delta n^2$ we have $\rho(M)\ge bn^\alpha$?

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

The motivation for this question comes from symbolic dynamics (hence the tags). Namely, is it true that for any topological Markov chain given by a matrix with "sufficiently many" 1s its topological entropy is positive?

  • $\begingroup$ I think a similar analysis works and should give something along these lines: (1) an irreducible matrix with sufficiently many ones has a large PF eigenvalue (because again if the eigenvector $x$ satisfies $x_1\le x_2\le\ldots$ and you want an eigenvalue $\le k$, then the first row can have at most $k$ ones, the second one has at most $k+1$ ones etc.); (2) write the matrix as a block upper triangular matrix with irreducible (or zero) diagonal blocks: this matrix has many zeros unless some blocks are large in size, but in that case (1) strikes. $\endgroup$ Apr 25, 2017 at 19:45

1 Answer 1


A paper that seems to directly address your question is the 1987 paper of Brualdi and Solheid, *On the minimal spectral radius of matrices of zeros and ones". That paper shows that if the number of 1's is $(\frac12+\delta)n^2$, then the spectral radius is essentially $2\delta n$. The paper also allows you to answer the question of how many 1's you do need if you want sublinear spectral radius. The extremal examples are the 0--1 matrices that are all 1's below the diagonal and have square blocks of 1's centred around the diagonal. That is, you have a number of completely connected components, all of the same size (with one remainder component), and each component had edges only to later components.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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