Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

In this paper we give an explicit construction of,<i n × n i> matrices

over finite fields which are somewhat rigid, in that if we change at

most <i k i> entries in each row, its rank remains at least <i Cn (log sub

q^k)/k$, where $q$ is the size of the field and $C$ is an absolute

constant. Our matrices satisify a somewhat stronger property, which we

explain and call "strong rigidity." We introduce and briefly discuss

strong rigidity, because it is in a sense a simpler property and may be

easier to use in giving explicit constructions.