# Most Matrices are Rigid

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

• 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.
– Community Bot
Jun 12 at 14:08
• 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.
– Stef
Jun 14 at 16:05

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, 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.
• 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 Jul 19 at 17:20
• You're absolutely right that this should be $\binom{n^2}{\leq s}$, I've fixed this, and explained the combinatorial bound. Jul 26 at 16:08