5
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\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$
    – Christian Remling
    Commented Apr 25, 2017 at 19:45

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .