A Remark on Matrix Rigidity

Authors: M. Amin Shokrollahi, Daniel Spielman, and Voelker Stemann.

Bibliographic Information: Information Processing Letters, 64(6), pp. 283--285, December 1997.

Abstract

The rigidity of a matrix is defined to be the number of entries in the matrix that have to be changed in order to reduce its rank below a certain value. Using a simple combinatorial lemma, we show that one must alter at least $c\frac{n^2}{r}\log\frac{n}{r}$ entries of an $n\times n$-Cauchy matrix to reduce its rank below $r$, for some constant $c$. In the second part of the paper we apply our combinatorial lemma to matrices obtained from asymptotically good algebraic geometric codes to obtain a similar result for $r$ satisfying $2n/(\sqrt{q}-1)

You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.