<p>The following additional references on Matrix Rigidity may be helpful:</p>

<ol>
<li><p>Complexity Lower Bounds using Linear Algebra, S. V. Lokam,
in Foundations and Trends in Theoretical Computer Science, Volume 4, 1-2, 2009.
<a href="http://dx.doi.org/10.1561/0400000011">http://dx.doi.org/10.1561/0400000011</a> </p></li>
<li><p>Using Elimination Theory to construct Rigid Matrices, A. Kumar, S.V. Lokam,. V. Patankar, J. Sarma, 
ECCC TR09-106, <a href="http://eccc.hpi-web.de/report/2009/106/">http://eccc.hpi-web.de/report/2009/106/</a></p></li>
</ol>

CC BY-SA 3.0
2013-02-24T07:14:19.353Z
2013-02-24T07:14:19.353Z
user13909
<p>Matrix rigidity was introduced by Valiant in 1977:</p>
<blockquote>
<p>The rigidity <span class="math-container">$Rig_M(r)$</span> of boolean matrix <span class="math-container">$M$</span> over GF(2) is the
smallest number of entries of <span class="math-container">$M$</span> that must be changed in order to
reduce its rank over GF(2) down to <span class="math-container">$r$</span>.</p>
</blockquote>
<p><span class="math-container">$Rig_M(r)$</span> has a deep connection to boolean function complexity &amp; circuit lower bounds by a result of Razborov 1989 see eg [1]. It also has a connection to finding locally correctable codes eg see [2]</p>
<p>It appears to me there is little to no published empirical analysis of <span class="math-container">$Rig_M(r)$</span> &amp; that it could give some useful insight into its properties (thinking for example of the transition point research with SAT).</p>
<p>As a start I was interested in analyzing <span class="math-container">$Rig_M(r)$</span> using a simple greedy algorithm. The idea is as follows.</p>
<ul>
<li><p>generate random matrixes <span class="math-container">$M$</span>.</p>
</li>
<li><p>Compute Delta_row(i,j) where i,j are row (vectors) of <span class="math-container">$M$</span> and Delta_row(i,j) is the Hamming distance between the two rows</p>
</li>
<li><p>likewise calculate the Delta_col(i,j) where i,j are column vectors of <span class="math-container">$M$</span> (equivalent to calculating Delta_row(i,j) of the transpose of M).</p>
</li>
<li><p>next sort Delta_row(i,j) and Delta_col(i,j) and remove the column or row from <span class="math-container">$M$</span> with the &quot;lowest value&quot;. (the lowest value is associated with a row or column pair, remove either row or column of the pair).</p>
</li>
</ul>
<p>This greedy algorithm can be used to estimate <span class="math-container">$Rig_M(r)$</span> by giving a (fairly tight?) upper bound. One repeatedly reapplies the greedy algorithm until the matrix <span class="math-container">$M$</span> has been reduced to size <span class="math-container">$r$</span> and counts the sum of the Delta_row/col values of removed rows. and note that upon removing rows or columns, the new Delta_row and Delta_col arrays can be computed efficiently without recalculating the whole arrays.</p>
<blockquote>
<ol>
<li><p>how far off can the greedy algorithm be from the optimal value <span class="math-container">$Rig_M(r)$</span>?</p>
</li>
<li><p>what kind of matrices maximize the difference between the greedy algorithm and the optimal rigidity measure?</p>
</li>
<li><p>can a modified local greedy algorithm find the optimal value <span class="math-container">$Rig_M(r)$</span></p>
</li>
</ol>
</blockquote>
<p>[1] <a href="https://rads.stackoverflow.com/amzn/click/com/3642245072" rel="nofollow noreferrer" rel="nofollow noreferrer">Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 &quot;rigid matrices require large circuits&quot;</a></p>
<p>[2] <a href="http://www.cs.princeton.edu/%7Ezdvir/papers/Dvir10.pdf" rel="nofollow noreferrer">On matrix rigidity and locally self-correctable codes by Zeev Dvir</a></p>
<p>[3] <a href="http://eccc.hpi-web.de/keyword/14464/" rel="nofollow noreferrer">ECCC reports tagged matrix rigidity</a></p>
<p>[4] <a href="http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf" rel="nofollow noreferrer">Matrix rigidity talk/overview by Mahdi Cheraghchi</a></p>
<p>[5] <a href="http://research.microsoft.com/en-us/um/people/nvishno/webpapers/ltvrigidity.pdf" rel="nofollow noreferrer">The geometry of matrix rigidity by Landsberg et al</a></p>
<p>[6] <a href="http://blog.computationalcomplexity.org/2005/07/matrix-rigidity.html" rel="nofollow noreferrer">Blog note on Midrijanis paper on Matrix rigidity by Lance Fortnow</a></p>
<p>[7] <a href="https://cstheory.stackexchange.com/questions/5080/empirical-results-in-cs-papers">Empirical results in CS papers</a></p>

CC BY-SA 3.0
2012-03-08T19:35:28.327Z
How do you sample your random matrices?
Mahdi Cheraghchi
CC BY-SA 3.0
2012-03-08T20:20:04.913Z
entries 1 vs 0 with constant probability eg 50%. can estimate Rig_M using technique for matrices size in the 100s height/width with PC & ruby code.
vzn
CC BY-SA 3.0
2012-03-08T22:12:32.467Z
But in that case the matrix is maximally rigid with probability close to 1, by a counting argument. So estimating rigidity up to a constant factor becomes trivial.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-03-09T16:06:10.370Z
i don't understand the fourth bullet point of your algorithm. the definition of rigidity does not deal with removing rows or columns, but changing entries. i assume you mean changing Delta_row(i, j) entries of one of the two rows i, j that minimize the quantity, so that they become two identical copies of the same row, thereby reducing the rank (same with cols). however at a next step you may need to change both copies of this row to become equal to another row. so you would need to modify 2Delta_row(i, k) entries at that point, and so on. so what actually is your upper bound on rigidity?
Sasho Nikolov
CC BY-SA 3.0
2012-03-09T18:44:54.030Z
MCH-- the pt is that the algorithm can estimate Rig_M for any matrix generated in any way. the Rig_M value for many types of matrices is poorly understood & there are not even theoretical estimates in many cases. examples of matrices that would be interesting to probe are eg those generated from NP complete problems, or those from coding theory eg Hadamard/Sylvester matrices etc
vzn
CC BY-SA 3.0
2012-03-09T18:50:47.800Z
SN excellent point/nice catch, thx, [full disclosure] that did not occur to me so far & guess the summation step has to be modified to take into account what you point out by multiplying by a factor of "n" to each step where "n" is the number of iterations so far. need to work out how to express that exactly
vzn
CC BY-SA 3.0
2012-03-09T19:03:13.477Z
MCH-- suppose I generate a matrix using an NP language/problem. and suppose it has similar empirically measured/estimated rigidity or a near trend to random matrices for matrices of "moderate" size. that seems like a useful/meaningful result, true? that is an old conjecture of mine that NP languages "look" random in some sense that has yet to be quantified...
vzn
CC BY-SA 3.0
2012-03-09T19:24:35.743Z
SN further thought on this. it seems all the rows/columns that have been "merged" can be thought of as a single row/column in the future. there are merged columns and unmerged columns. one can in the future change entries on the unmerged columns instead of the merged rows/columns to match the merged-so-far rows/columns, true?
vzn
CC BY-SA 3.0
2012-03-09T20:58:35.280Z
what if two pairs of merged rows become the two closest rows?
Sasho Nikolov
CC BY-SA 3.0
2012-03-10T00:12:23.487Z
the idea behind the algorithm was that its greedy & not too complicated. heres another idea-- modify the above algorithm so that it marks/flags cols/rows as merged & only considers merges between either unmerged rows or a merged/unmerged row pair, but never a merged/merged pair. there can be other variations. wonder if anyone has even computed matrix rigidity at all for arbitrary matrices-- have never seen it actually calculated in a paper or seen an algorithm for it in general
vzn
CC BY-SA 3.0
2012-03-11T23:59:18.283Z
Of course it makes sense to look at rigidity of specific matrices, like Sylvester. My point is that once you generate a matrix randomly and uniformly, with overwhelming probability you already know its rigidity and there's not much reason to proceed.
Mahdi Cheraghchi
CC BY-SA 3.0
2012-03-12T02:32:15.043Z
actually you dont know the rigidity in the sense that the known trends for random matrices are asymptotic & "probably" do not fit the same calculated curve exactly for low values (similar to the bias problem in statistics for small samples). but that comparison cant be done without some algorithm for the computation. apparently nothing other than brute force is known which takes n^t where t is the matrix size. which reminds me of another question on here for worst case P-time algorithms that I might answer now with that.
vzn
<reference-request><approximation-algorithms><circuit-complexity><lower-bounds><open-problem>
Questions about computing matrix rigidity
vzn
# Questions about computing matrix rigidity

(Asked by: username_0 on 2012-03-07)

Matrix rigidity was introduced by Valiant in 1977:

> The rigidity $Rig\_M(r)$ of boolean matrix $M$ over GF(2) is the
> smallest number of entries of $M$ that must be changed in order to
> reduce its rank over GF(2) down to $r$.

$Rig\_M(r)$ has a deep connection to boolean function complexity & circuit lower bounds by a result of Razborov 1989 see eg [1]. It also has a connection to finding locally correctable codes eg see [2]

It appears to me there is little to no published empirical analysis of $Rig\_M(r)$ & that it could give some useful insight into its properties (thinking for example of the transition point research with SAT).

As a start I was interested in analyzing $Rig\_M(r)$ using a simple greedy algorithm. The idea is as follows.

* generate random matrixes $M$.
* Compute Delta\_row(i,j) where i,j are row (vectors) of $M$ and Delta\_row(i,j) is the Hamming distance between the two rows
* likewise calculate the Delta\_col(i,j) where i,j are column vectors of $M$ (equivalent to calculating Delta\_row(i,j) of the transpose of M).
* next sort Delta\_row(i,j) and Delta\_col(i,j) and remove the column or row from $M$ with the "lowest value". (the lowest value is associated with a row or column pair, remove either row or column of the pair).

This greedy algorithm can be used to estimate $Rig\_M(r)$ by giving a (fairly tight?) upper bound. One repeatedly reapplies the greedy algorithm until the matrix $M$ has been reduced to size $r$ and counts the sum of the Delta\_row/col values of removed rows. and note that upon removing rows or columns, the new Delta\_row and Delta\_col arrays can be computed efficiently without recalculating the whole arrays.

> 1. how far off can the greedy algorithm be from the optimal value $Rig\_M(r)$?
> 2. what kind of matrices maximize the difference between the greedy algorithm and the optimal rigidity measure?
> 3. can a modified local greedy algorithm find the optimal value $Rig\_M(r)$

[1] [Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"](https://rads.stackoverflow.com/amzn/click/com/3642245072)

[2] [On matrix rigidity and locally self-correctable codes by Zeev Dvir](http://www.cs.princeton.edu/%7Ezdvir/papers/Dvir10.pdf)

[3] [ECCC reports tagged matrix rigidity](http://eccc.hpi-web.de/keyword/14464/)

[4] [Matrix rigidity talk/overview by Mahdi Cheraghchi](http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf)

[5] [The geometry of matrix rigidity by Landsberg et al](http://research.microsoft.com/en-us/um/people/nvishno/webpapers/ltvrigidity.pdf)

[6] [Blog note on Midrijanis paper on Matrix rigidity by Lance Fortnow](http://blog.computationalcomplexity.org/2005/07/matrix-rigidity.html)

[7] [Empirical results in CS papers](https://cstheory.stackexchange.com/questions/5080/empirical-results-in-cs-papers)

**Tags:** reference-request, approximation-algorithms, circuit-complexity, lower-bounds, open-problem
> **Comments:**
> **username_1**: How do you sample your random matrices?  
> **username_0**: entries 1 vs 0 with constant probability eg 50%. can estimate Rig_M using technique for matrices size in the 100s height/width with PC & ruby code.  
> **username_1**: But in that case the matrix is maximally rigid with probability close to 1, by a counting argument. So estimating rigidity up to a constant factor becomes trivial.  
> **username_2**: i don't understand the fourth bullet point of your algorithm. the definition of rigidity does not deal with removing rows or columns, but changing entries. i assume you mean changing Delta_row(i, j) entries of one of the two rows i, j that minimize the quantity, so that they become two identical copies of the same row, thereby reducing the rank (same with cols). however at a next step you may need to change both copies of this row to become equal to another row. so you would need to modify 2Delta_row(i, k) entries at that point, and so on. so what actually is your upper bound on rigidity?  
> **username_0**: MCH-- the pt is that the algorithm can estimate Rig_M for any matrix generated in any way. the Rig_M value for many types of matrices is poorly understood & there are not even theoretical estimates in many cases. examples of matrices that would be interesting to probe are eg those generated from NP complete problems, or those from coding theory eg Hadamard/Sylvester matrices etc  
> **username_0**: SN excellent point/nice catch, thx, [full disclosure] that did not occur to me so far & guess the summation step has to be modified to take into account what you point out by multiplying by a factor of "n" to each step where "n" is the number of iterations so far. need to work out how to express that exactly  
> **username_0**: MCH-- suppose I generate a matrix using an NP language/problem. and suppose it has similar empirically measured/estimated rigidity or a near trend to random matrices for matrices of "moderate" size. that seems like a useful/meaningful result, true? that is an old conjecture of mine that NP languages "look" random in some sense that has yet to be quantified...  
> **username_0**: SN further thought on this. it seems all the rows/columns that have been "merged" can be thought of as a single row/column in the future. there are merged columns and unmerged columns. one can in the future change entries on the unmerged columns instead of the merged rows/columns to match the merged-so-far rows/columns, true?  
> **username_2**: what if two pairs of merged rows become the two closest rows?  
> **username_0**: the idea behind the algorithm was that its greedy & not too complicated. heres another idea-- modify the above algorithm so that it marks/flags cols/rows as merged & only considers merges between either unmerged rows or a merged/unmerged row pair, but never a merged/merged pair. there can be other variations. wonder if anyone has even computed matrix rigidity at all for arbitrary matrices-- have never seen it actually calculated in a paper or seen an algorithm for it in general  
> **username_1**: Of course it makes sense to look at rigidity of specific matrices, like Sylvester. My point is that once you generate a matrix randomly and uniformly, with overwhelming probability you already know its rigidity and there's not much reason to proceed.  
> **username_0**: actually you dont know the rigidity in the sense that the known trends for random matrices are asymptotic & "probably" do not fit the same calculated curve exactly for low values (similar to the bias problem in statistics for small samples). but that comparison cant be done without some algorithm for the computation. apparently nothing other than brute force is known which takes n^t where t is the matrix size. which reminds me of another question on here for worst case P-time algorithms that I might answer now with that.  

---

## 1 answers

### Answer by username_3 on 2013-02-24. Score: 6

The following additional references on Matrix Rigidity may be helpful:

1. Complexity Lower Bounds using Linear Algebra, S. V. Lokam,
   in Foundations and Trends in Theoretical Computer Science, Volume 4, 1-2, 2009.
   <http://dx.doi.org/10.1561/0400000011>
2. Using Elimination Theory to construct Rigid Matrices, A. Kumar, S.V. Lokam,. V. Patankar, J. Sarma,
   ECCC TR09-106, <http://eccc.hpi-web.de/report/2009/106/>


---

