The cut-norm ||A||C of a real matrix A=(aij)i∈R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity |Σi∈I,j∈Jaij|. We show that there is an absolute positive constant c so that if A is the n by n identity matrix and B is a real n by n matrix satisfying ||A-B||-C≤(formula presented.)||A||C, then rank(B)≥cn. Extensions to denser binary matrices are considered as well.
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- MSC 15A60