A NOTE ON MATRIX RIGIDITY

被引：46

作者：

FRIEDMAN, J ^{[1
]}

机构：

[1] HEBREW UNIV JERUSALEM,JERUSALEM,ISRAEL

来源：

COMBINATORICA | 1993年 / 13卷 / 02期

关键词：

AMS subject classification code (1991): 05 B; 05; C; 68; Q; 94; B;

D O I：

10.1007/BF01303207

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we give an explicit construction of n x 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 Cn(log(q) k)/k, where q is the size of the field and C is an absolute constant. Our matrices satisfy a somewhat stronger property, we will 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 construction.

引用

页码：235 / 239

页数：5