A Remark on Matrix Rigidity

. 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 2 r log n r entries of an n \Theta 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=( p q \Gamma 1) ! r n=4: Key words. Matrix rigidity, circuit complexity, communication complexity 1. Introduction Valiant [11] defined the rigidity R K M (r) of a matrix M over a field K to be the number of entries of M that have to be changed to reduce its rank below r: R K M (r) := minfwt(P ) j rk(M + P ) rg: Here wt(P ) denotes the number of nonzero entries of P . He proposed the fundamental problem of finding matrices with high rigidity. If " and ffi are consta..