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

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