Wednesday, July 06, 2005

Matrix Rigidity

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.

4 comments:

  1. Why was this very simple proof missed before? Is it because people focused on so-called generalized Hadamard matrices and were thus determined to use spectral techniques? This isn't the proof Nisan used for "totally non-singular" matrices?

    ReplyDelete
  2. I believe this is a well-known proof for showing that the Hadamard matrix has rigidity function n^2/r, and it is due (in unpublished form) independently to Grigoriev and Nisan (over ten years ago).

    There are more sophisticated counting techniques based on the same principle (i.e. the non-singularity of sub-matrices). See, for instance,
    http://www-math.mit.edu/~spielman/Research/rigid.html.

    ReplyDelete
  3. It's a very good point to write up simple results (because you never know if it's as simple for the others or not), but of course this simple proof hasn't been missed before. In fact, it's so trivial that no one ever thinks about explicitly mentioning it in a publication! I guess every sensible person who has just tried to (rather seriously) think about matrix rigidity comes up with a similar result after a short time. So this is more or less a "warm-up exercise," but of course, as I said, is still worth putting on arXiv. Unfortunately, the proof doesn't give much to us, as it doesn't deeply go down into the specific combinatorial structure of the matrix. Moreover, the result of Shokrollahi et al. (1997) shows a stronger lower bound of $\Omega(n^2/r log(n/r))$ for the same problem based on a similar principle (minors with high ranks), still far from implying nontrivial complexity results. Their proof is already simple enough.

    Finally, one can as easily show a lower bound $\Omega(n^2/r)$ for the rigidity any matrix whose $t \times t$ submatrices have rank $\Omega(t)$ "on average." (apologies for using TeX macros here!!)

    Precisely, let $A+B=C$, where $rk(C) <= r$, and the "expected rank" of a random $t \times t$ minor be at least $t/c$, for some constant $c$. Now, let $t=2rc$ and A0 be a $t \times t$ minor of A. Let B0 and C0 be the corresponding minors in B and C (minors chosen with the same pattern). We have:

    $2r = t/c <= E[rk(A0)] <= E[rk(C0)]+E[rk(B0)] <= E[rk(C)]+E[rk(B0)] <= r+E[rk(B0)] <= r+E[wt(B0)] <= r+(t/n)^2 wt(B)$

    Hence, $r <= (4c^2r^2/n^2) Rig_A(r)$ and we're done.

    One example of such matrices is the generalized (complex) Hadamard matrix. So we've just proved the best known lower bound for rigidity of the general case of Hadamard matrices (modulo showing that the expected ranks are high which is a bit messy but straightforward spectral analysis for the case of Hadamard matrices). In fact, the proof of Kashin and Razborov (1998) goes along similar lines.

    In any case, it's very nice to see new works being done on rigid matrices. They hopefully draw researchers' attention to put more efforts on this long-standing but nowadays less-cared-about problem.

    ReplyDelete
  4. ----------------------------------------
    Why was this very simple proof missed before? Is it because people focused on so-called generalized Hadamard matrices and were thus determined to use spectral techniques?
    ----------------------------------------
    Well, as I understand the applications for this problem: a lower bound for ANY EXPLICIT matrix is welcomed from the point of view of circuits complexity. For communication complexity, any explicit (0,1)-matrix is interesting.

    ----------------------------------------
    This isn't the proof Nisan used for "totally non-singular" matrices?
    ----------------------------------------
    I have not read Nisan's proof (and how I could?), but I guess I didn't prove that Sylvester matrix is totally non-singular.

    ----------------------------------------
    In fact, it's so trivial that no one ever thinks about explicitly mentioning it in a publication!
    ----------------------------------------
    Hmm, I didn't found this so trivial fact even mentioned at many papers I went through, despite more trivial facts were mentioned. Even in a low-level survey paper by B. Codenotti (Matrix Rigidity, Linear Algebra and its Applications, 304(1-3):181�192. 2000.)

    ----------------------------------------
    I guess every sensible person who has just tried to (rather seriously) think about matrix rigidity comes up with a similar result after a short time.
    ----------------------------------------
    I know at least one researcher on this field that didn't know this fact before.



    The moral of this story: those who write serious publications and survey papers should sometimes mention trivial facts as well for new ones in the field. Anyway, I agree, this paper is not much more than a curiosity.

    --Gatis

    ReplyDelete