Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$.

If an $n \times n$ matrix $A$ is rigid, then the smallest straight line program computing $Ax$ ($x$ is a vector of size $n$) is either super-linear size, or has super logarithmic depth.

Is there a converse to the above statement?

In other words are there uses to non-trivial and non-obvious low rigidity matrices of full rank in TCS?

Is there a notion of rigidity for matrices with lower ranks (say $\frac{n}{c}$ for some constant $c$)?

  • $\begingroup$ +1, nice to see question on rigidity here, advanced topic, but its not so clear. converse of statement would be something like if the smallest straight line program computing $A x$ is either superlinear size or superlogarithmic depth, then the $n \times n$ matrix is rigid. right? but this seems to be different than the last question about nontrivial/nonobvious low rigidity matrices. it would seem the rigidity of most matrices either low or high is not so trivial or obvious... there are many useful matrices that have low rigidity... no nonrandom matrices of high rigidity have been constructed! $\endgroup$
    – vzn
    Apr 3 '13 at 16:47
  • 7
    $\begingroup$ If a matrix $A$ is not rigid, you can decompose it as $A=B+C$ where $B$ is a low-rank matrix and $C$ is a sparse matrix. Linear programs defined by $B$ and $C$ can be computed efficiently (i.e., better than trivial) by relying on the low rank and sparsity properties. This means, for example, that if $A$ requires a quadratic sized circuit, then it has to be rigid (with an appropriate choice of the parameters). $\endgroup$ Apr 3 '13 at 17:10
  • $\begingroup$ maybe first it's good to ask for examples of matrices with non-obviously low rigidity $\endgroup$ Apr 4 '13 at 1:52
  • $\begingroup$ @vzn another way to state the converse is "do low rigidity matrices have linear small circuits". your answer is exactly in the opposite direction (not a word about applications of the sort less rigid -> more efficient), so -1 $\endgroup$ Apr 4 '13 at 1:55
  • $\begingroup$ @MCH Good point. What could the better than trivial be? You are making an interesting point I will change the question a bit. $\endgroup$
    – Mr.
    Apr 4 '13 at 6:19

lacking further clarification of the question, heres a try/sketch of an answer. matrix rigidity has deep connections to fundamental questions in TCS/complexity theory including circuit lower bounds,[1] and thereby complexity class separations, and coding theory[2] as well as other areas. [5] is a nice slide survey.

the terms "low" and "high" in reference to rigidty of matrices are used informally and not in a precisely defined technical sense. [although Friedman did define "strong" rigidity. [6]] random matrices are known to have high rigidity but basically, its ~a 3.5 decades old open problem in this area to explicitly construct any matrix with "significantly high" rigidity.

the question doesnt further define/clarify the subjective terms "nontrivial" or "nonobvious" & will take some freedom there.

in this area there is a line of research looking at the rigidity of Hadamard matrices which have misc uses/applications in coding theory & elsewhere.

it seems fair to say a provably high rigidity result would surpass the threshhold of leading at least to "new nontrivial corollaries in complexity theory" but the best known bounds on Hadamard matrices do not suffice.[3] but neither does this conclusively prove they have limited "low" rigidity. its basically the same story with Vandermonde matrices [also applications in coding theory] considered by Lokam.[4]

so to summarize about all that can be said is that "weak lower rigidity bounds" have been proven on some matrices including Hadamard/Vandermonde matrices.

there also do not appear to be any published numerical experiments, estimates, or algorithms in the area.

[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 Zeev Dvir

[3] Improved lower bounds on the ridigity of Hadamard matrices Kashin/Razborov

[4] On the Rigidity of Vandermonde Matrices Lokam

[5] Mahdi Cheraghchi matrix rigidity talk

[6] J. Friedman. A note on matrix rigidity. Combinatorica, 13(2);235-239, 1993


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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