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

<p>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 <em>any</em> matrix with "significantly high" rigidity.</p>

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

<p>in this area there is a line of research looking at the rigidity of <a href="http://en.wikipedia.org/wiki/Hadamard_matrix" rel="nofollow">Hadamard matrices</a> which have misc uses/applications in coding theory &amp; elsewhere.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Vandermonde_matrix" rel="nofollow">Vandermonde matrices</a> [also applications in coding theory] considered by Lokam.[4]</p>

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

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

<p>[1] <a href="http://rads.stackoverflow.com/amzn/click/3642245072" rel="nofollow">Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"</a></p>

<p>[2] <a href="http://www.cs.princeton.edu/~zdvir/papers/Dvir10.pdf" rel="nofollow">On matrix rigidity and locally self-correctable codes</a> Zeev Dvir</p>

<p>[3] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7746" rel="nofollow">Improved lower bounds on the ridigity of Hadamard matrices</a> Kashin/Razborov</p>

<p>[4] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9483" rel="nofollow">On the Rigidity of Vandermonde Matrices</a> Lokam</p>

<p>[5] <a href="http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf" rel="nofollow">Mahdi Cheraghchi matrix rigidity talk</a></p>

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

CC BY-SA 3.0
2013-04-04T01:18:08.297Z
2013-04-04T01:27:01.023Z
2013-04-04T01:27:01.023Z
vzn
<p>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 &gt; 0$.</p>

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

<p>Is there a converse to the above statement?</p>

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

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

CC BY-SA 3.0
2013-04-03T16:47:13.203Z
+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!
vzn
CC BY-SA 3.0
2013-04-03T17:10:35.130Z
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).
Mahdi Cheraghchi
CC BY-SA 3.0
2013-04-04T01:52:58.313Z
maybe first it's good to ask for *examples* of matrices with non-obviously low rigidity
Sasho Nikolov
CC BY-SA 3.0
2013-04-04T01:55:52.577Z
@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
Sasho Nikolov
CC BY-SA 3.0
2013-04-04T06:19:41.407Z
@MCH Good point. What could the better than trivial be? You are making an interesting point I will change the question a bit.
Turbo
CC BY-SA 3.0
2013-04-04T10:18:51.003Z
@SashoNikolov Haar wavelet based DWT matrices seem to satisfy the criteria.
Turbo
CC BY-SA 3.0
2013-04-04T15:00:04.560Z
ok then from SNs comments it sounds like the question is then basically intending to ask for tight upper bounds on low-rigidity matrices. have not heard of such results, has anyone else? the literature seems more focused on attempting to prove tight lower bounds on possibly high-rigidity matrices (and so far not succeeding at all).
vzn
CC BY-SA 3.0
2013-04-05T15:13:02.543Z
@vzn: no, the question is focused on showing that upper bounds on rigidity lead to small size circuits or other algorithmic upper bounds
Sasho Nikolov
<cc.complexity-theory>
Matrix rigidity and uses of matrices with low rigidity
Turbo
# Matrix rigidity and uses of matrices with low rigidity

(Asked by: username_0 on 2013-04-03)

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

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: +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!  
> **username_2**: 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).  
> **username_3**: maybe first it's good to ask for *examples* of matrices with non-obviously low rigidity  
> **username_3**: @username_1 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  
> **username_0**: @MCH Good point. What could the better than trivial be? You are making an interesting point I will change the question a bit.  
> **username_0**: @SashoNikolov Haar wavelet based DWT matrices seem to satisfy the criteria.  
> **username_1**: ok then from SNs comments it sounds like the question is then basically intending to ask for tight upper bounds on low-rigidity matrices. have not heard of such results, has anyone else? the literature seems more focused on attempting to prove tight lower bounds on possibly high-rigidity matrices (and so far not succeeding at all).  
> **username_3**: @username_1: no, the question is focused on showing that upper bounds on rigidity lead to small size circuits or other algorithmic upper bounds  

---

## 1 answers

### Answer by username_1 on 2013-04-04. Score: -3

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](http://en.wikipedia.org/wiki/Hadamard_matrix) 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](http://en.wikipedia.org/wiki/Vandermonde_matrix) [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"](http://rads.stackoverflow.com/amzn/click/3642245072)

[2] [On matrix rigidity and locally self-correctable codes](http://www.cs.princeton.edu/~zdvir/papers/Dvir10.pdf) Zeev Dvir

[3] [Improved lower bounds on the ridigity of Hadamard matrices](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7746) Kashin/Razborov

[4] [On the Rigidity of Vandermonde Matrices](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9483) Lokam

[5] [username_2 matrix rigidity talk](http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf)

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


---

