A Note on Matrix Rigidity

Abstract:

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.