A Note on Matrix Rigidity
作者： Joel Friedman
DOI: 10.1007/BF01303207
关键词: Matrix (mathematics) 、 Mathematics 、 Combinatorics 、 Rigidity (electromagnetism) 、 Finite field 、 Absolute constant 、 Square matrix
摘要: In this paper we give an explicit construction ofn×n matrices over finite fields which are somewhat rigid, in that if change at mostk entries each row, its rank remains leastCn(log q k)/k, whereq is the size of field andC absolute constant. Our satisfy a stronger property, will explain and call “strong rigidity”. We introduce briefly discuss strong rigidity, because it sense simpler property may be easier to use giving construction.
springer.com
sci-hub.se 参考文章(3)
Leslie G. Valiant, Graph-theoretic arguments in low-level complexity mathematical foundations of computer science. pp. 162- 176 ,(1977) , 10.1007/3-540-08353-7_135
Gerard Van der Geer, J. H. Van Lint, Introduction to Coding Theory and Algebraic Geometry ,(1988)
J. H. van Lint, Introduction to Coding Theory Graduate texts in mathematics : readings in mathematics. ,vol. 86, ,(1982) , 10.1007/978-3-642-58575-3