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 ce
rtain 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 x n)-Cauchy matrix
to reduce its rank below r, for some constant c. We apply our combinat
orial lemma to matrices obtained from asymptotically good algebraic ge
ometric codes to obtain a similar result for r satisfying 2n/(root q -
1) < r less than or equal to n/4. (C) 1997 Elsevier Science B.V.