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