A Note on Matrix Rigidity
  • Postscript version.
  • Dvi version.
  • PDF version.

  • Abstract:

    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.