Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The rigidity of a matrix $M\in \mathbb{F}^{n\times n}$ is the minimum number of entries that need to be changed in $M$ to reduce its rank to $r$. Formally, it is defined as:
$$R_{M}^{\mathbb{F}}(r) = \min_{A} \{sparsity(A) | A\in \mathbb{F}^{n\times n}, rank(M+A)\leq r\}.$$
I was wondering is someone could point me to a proof of the fact that for a random matrix $M\in \mathbb{F}^{n\times n},$, with high probability, $ R_{M}^{\mathbb{F}}(r) \geq \frac{(n-r)^2}{\log n}.$
For simplicity, let us first consider the case $\mathbb{F}=\mathbb{F}_2$. Every non-rigid matrix can be specified by a rank-$r$ matrix $L$ and a matrix $S$ of total sparsity $s$. Since every low-rank matrix $R$ can be written as a product of $n\times r$ and $r\times n$ matrices, the number of matrices of rank $\leq r$ is at most $2^{2nr}$. Every sparse matrix $S$ is specified by a list of at most $s$ ones in the matrix, and, thus, assuming $s\leq n^2/2$, the number of matrices $S$ is at most $\binom{n^2}{\leq s}\leq n^2 \binom{n^2}{s} \leq 2^{O(s\log{n})}$. This implies that the total number of non-rigid matrices is at most $2^{O(nr+s\log{n})}$. Therefore, for $s<O(n(n-2r)/\log{n})$, we have that a random matrix is rigid.
This argument extends to all finite fields. The bound can be improved to $(n-r)^2/\log{n}$. Moreover, for many settings of the parameters, the factor of $\log{n}$ can be shaved off, too. Finally, a slight modification of this argument gives a tight bound of $(n-r)^2$ for the case when $\mathbb{F}$ is infinite. All of these extensions can be found, for example, in Theorem 1.10 here.
