4
$\begingroup$

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

$\endgroup$
2
  • $\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
    Commented Jun 12, 2023 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
    Commented Jun 14, 2023 at 16:05

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Commented Jul 19, 2023 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$ Commented Jul 26, 2023 at 16:08

Your Answer

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

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