Matrix rigidity and uses of matrices with low rigidity 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$.

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$)?
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" &amp; 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 &amp; 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