<p>For simplicity, let us first consider the case <span class="math-container">$\mathbb{F}=\mathbb{F}_2$</span>. Every non-rigid matrix can be specified by a rank-<span class="math-container">$r$</span> matrix <span class="math-container">$L$</span> and a matrix <span class="math-container">$S$</span> of total sparsity <span class="math-container">$s$</span>. Since every low-rank matrix <span class="math-container">$R$</span> can be written as a product of <span class="math-container">$n\times r$</span> and <span class="math-container">$r\times n$</span> matrices, the number of matrices of rank <span class="math-container">$\leq r$</span> is at most <span class="math-container">$2^{2nr}$</span>. Every sparse matrix <span class="math-container">$S$</span> is specified by a list of at most <span class="math-container">$s$</span> ones in the matrix, and, thus, assuming <span class="math-container">$s\leq n^2/2$</span>, the number of matrices <span class="math-container">$S$</span> is at most <span class="math-container">$\binom{n^2}{\leq s}\leq n^2 \binom{n^2}{s} \leq 2^{O(s\log{n})}$</span>. This implies that the total number of non-rigid matrices is at most <span class="math-container">$2^{O(nr+s\log{n})}$</span>. Therefore, for <span class="math-container">$s&lt;O(n(n-2r)/\log{n})$</span>, we have that a random matrix is rigid.</p>
<p>This argument extends to all finite fields. The bound can be improved to <span class="math-container">$(n-r)^2/\log{n}$</span>. Moreover, for many settings of the parameters, the factor of <span class="math-container">$\log{n}$</span> can be shaved off, too.
Finally, a slight modification of this argument gives a tight bound of <span class="math-container">$(n-r)^2$</span> for the case when <span class="math-container">$\mathbb{F}$</span> is infinite. All of these extensions can be found, for example, in Theorem 1.10 <a href="https://golovnev.org/rigidity/notes23.pdf" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2023-07-19T17:20:39.053Z
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
atul ganju
CC BY-SA 4.0
2023-07-26T16:08:12.173Z
You're absolutely right that this should be $\binom{n^2}{\leq s}$, I've fixed this, and explained the combinatorial bound.
Alex Golovnev
CC BY-SA 4.0
2023-06-15T21:36:46.793Z
2023-07-26T16:06:46.907Z
2023-07-26T16:06:46.907Z
Alex Golovnev
<p>The rigidity of a matrix <span class="math-container">$M\in \mathbb{F}^{n\times n}$</span> is the minimum number of entries that need to be changed in <span class="math-container">$M$</span> to reduce its rank to <span class="math-container">$r$</span>. Formally, it is defined as:</p>
<p><span class="math-container">$$R_{M}^{\mathbb{F}}(r) = \min_{A} \{sparsity(A) | A\in \mathbb{F}^{n\times n}, rank(M+A)\leq r\}.$$</span></p>
<p>I was wondering is someone could point me to a proof of the fact that for a random matrix <span class="math-container">$M\in \mathbb{F}^{n\times n},$</span>, with high probability, <span class="math-container">$ R_{M}^{\mathbb{F}}(r) \geq \frac{(n-r)^2}{\log n}.$</span></p>

CC BY-SA 4.0
2023-06-12T14:08:14.457Z
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
CC BY-SA 4.0
2023-06-14T16:05:03.110Z
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
<complexity><boolean-matrix>
Most Matrices are Rigid
atul ganju
# Most Matrices are Rigid

(Asked by: username_0 on 2023-06-11)

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

**Tags:** complexity, boolean-matrix
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2023-06-15. Score: 7 | Accepted answer

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](https://golovnev.org/rigidity/notes23.pdf).

> **Comments:**
> **username_0**: 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  
> **username_3**: You're absolutely right that this should be $\binom{n^2}{\leq s}$, I've fixed this, and explained the combinatorial bound.  

---

