A Note on Matrix Rigidity
- Postscript version.
- Dvi version.
- PDF 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.