Abstract
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.
Original language | English (US) |
---|---|
Article number | 13340 |
Pages (from-to) | 409-418 |
Number of pages | 10 |
Journal | Linear Algebra and Its Applications |
Volume | 486 |
DOIs | |
State | Published - Dec 1 2015 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Numerical Analysis
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- MSC 15A60