A Note on Matrix Rigidity
Report ID: TR-308-91Author: Friedman, Joel
Date: 1990-06-00
Pages: 7
Download Formats: |PDF|
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.