# 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 & circuit lower bounds by a result of Razborov 1989 see eg . It also has a connection to finding locally correctable codes eg see 

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)$$

• How do you sample your random matrices? Mar 8 '12 at 19:35
• 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
Mar 8 '12 at 20:20
• 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. Mar 8 '12 at 22:12
• 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? Mar 9 '12 at 16:06
• what if two pairs of merged rows become the two closest rows? Mar 9 '12 at 20:58