Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Matrix Rigidity

Expand Messages
  • Lance
    Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices. The
    Message 1 of 1 , Jul 6, 2005
    • 0 Attachment
      Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices.

      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.

      --
      Posted by Lance to Computational Complexity at 7/06/2005 09:15:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.