A remark on matrix rigidity
β
M.A. Shokrollahi; D.A. Spielman; V. Stemann
π
Article
π
1997
π
Elsevier Science
π
English
β 244 KB
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