A remark on matrix rigidity

✍ Scribed by M.A. Shokrollahi; D.A. Spielman; V. Stemann

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 244 KB
• Volume: 64
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00190-7

✦ Synopsis

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( n*/r) log( n/r) entries of an (n x n)-Cauchy matrix to reduce its rank below r, for some constant c. We apply our combinatorial lemma to matrices obtained from asymptotically good algebraic geometric codes to obtain a similar result for r satisfying 2n/( fi -1) < r < n/4. @ 1997 Elsevier Science B.V.