1
$\begingroup$

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"

[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

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ How do you sample your random matrices? $\endgroup$
    – Mahdi Cheraghchi
    Commented Mar 8, 2012 at 19:35
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Mar 8, 2012 at 20:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mahdi Cheraghchi
    Commented Mar 8, 2012 at 22:12
  • 2
    $\begingroup$ 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? $\endgroup$
    – Sasho Nikolov
    Commented Mar 9, 2012 at 16:06
  • 1
    $\begingroup$ what if two pairs of merged rows become the two closest rows? $\endgroup$
    – Sasho Nikolov
    Commented Mar 9, 2012 at 20:58

1 Answer 1

Reset to default
6
$\begingroup$

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/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.