A Note on Matrix Rigidity
• Postscript version.
• Dvi version.
In this paper we give an explicit construction of $n\times n$ matrices over finite fields which are somewhat rigid, in that if we change at most $k$ entries in each row, its rank remains at least $C n (\log_q k) /k,$ where $q$ is the size of the field and $C$ is an absolute constant. Our matrices satify a somewhat stronger property, we which 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.