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}.$

  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Jun 12 at 14:08
  • $\begingroup$ If I had to prove this I would proceed in this very boring way: (1) Determine the expectation of R_M^F(r); (2) Determine the variance of R_M^F(r); (3) Pick up a book titled "Concentration inequalities" and look for an inequality in the book that seems applicable. $\endgroup$
    – Stef
    Jun 14 at 16:05

1 Answer 1


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.

  • $\begingroup$ why is the number of sparse matrices not $\binom{n^2}{\leq s}$, also where do you get the upper bound on this combinatorial quantity $\endgroup$
    – atul ganju
    Jul 19 at 17:20
  • $\begingroup$ You're absolutely right that this should be $\binom{n^2}{\leq s}$, I've fixed this, and explained the combinatorial bound. $\endgroup$ Jul 26 at 16:08

Your Answer

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

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