The rigidity of a matrix M is a function RM(r) equal to the minimum number of entries of M that you need to change in order to reduce the rank to r. Strong rigidity bounds would have applications for circuit and communication complexity.
Let N=2n. We define the N×N Sylvester S by labeling the rows and columns by n-bit vectors and let si,j=(-1)i·j.
Theorem: If r ≤ N/2 is a power of 2 then RS(r) ≥ N2/4r.
Proof: Divide S uniformly into (N/2r)2 submatrices of size 2r×2r. One can easily verify these submatrices each have full rank. So we need to change at least r elements of each submatrix to reduce each of their ranks to r, a necessary condition to reducing the rank of S to r. QED
This proof works for any matrix whose submatrices have full rank. Consider the N×N matrix B where bi,j=1 if i ≡ j (mod 2r) and 0 otherwise. By the same proof RB(r)=N2/4r even though the rank of B is only 2r.
The moral of this story: We conjecture that the Sylvester matrices have very high rigidity but we still lack the tools that make full use of the structure of these matrices.