Questions about computing matrix rigidity 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 &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]
It appears to me there is little to no published empirical analysis of $Rig_M(r)$ &amp; 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 &quot;lowest value&quot;. (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.


how far off can the greedy algorithm be from the optimal value $Rig_M(r)$?

what kind of matrices maximize the difference between the greedy algorithm and the optimal rigidity measure?

can a modified local greedy algorithm find the optimal value $Rig_M(r)$



[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 &quot;rigid matrices require large circuits&quot;
[2] On matrix rigidity and locally self-correctable codes by Zeev Dvir
[3] ECCC reports tagged matrix rigidity
[4] Matrix rigidity talk/overview by Mahdi Cheraghchi
[5] The geometry of matrix rigidity by Landsberg et al
[6] Blog note on Midrijanis paper on Matrix rigidity by Lance Fortnow
[7] Empirical results in CS papers
The following additional references on Matrix Rigidity may be helpful:


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 
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/