A personal research question led me to the following problem. Suppose a randomly-chosen $n\times n$ matrix over $\mathbb{F}_2$ such that:
- The main diagonal is all 1's.
- The weight of each row (i.e. number of 1's) is exactly $d\ll n$ (e.g. $d=O(\sqrt{n})$).
I believe (haven't proven) that this matrix has expected rank $r\approx n$.
The question: suppose we can freely remove 1's from the matrix, excepting the main diagonal, which must remain constant. How likely are we to be able to reduce the rank of the matrix significantly (i.e. so that $r = o(n)$)? I would appreciate any directions.
Further information and some basic intuitions:
- On the Rank of a Random Binary Matrix discusses the expected rank of random binary matrices (without the extra requirements), and it appears to be $O(n)$. But here we are discussing a very sparse matrix.
- The requirement not to touch the main diagonal is crucial, as otherwise we can easily reduce the rank however we want.
- This bears similarity to matrix rigidity which was described for example in Valiant '70, and is defined as the minimum number of entries which one has to alter in a matrix in order to reduce the rank to $r$. IIRC, for random binary matrices the expected rigidity would be $(n-r)^2$, but here the matrix is sparse so the rigidity can be no more than linear in $n-r$. Furthermore, rigidity does not take into account the constraint on the main diagonal, so it's not clear to me if discussing rigidity is helpful at all.
- Just for intuition, there is obviously non-zero probability of being able to reduce the rank to the minimum possible $\frac{n}{d}$, in the case where we pick a matrix such that the 1's are all arranged in blocks of size $d\times d$.
- I conjecture that it is very unlikely that the rank can be reduced significantly, and I suspect that there might be a simple way of getting at least a loose bound for it, but I'm not sure how to go about it.
Thanks!