Approximating sparse binary matrices in the cut-norm

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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 languageEnglish (US)
Article number13340
Pages (from-to)409-418
Number of pages10
JournalLinear Algebra and Its Applications
StatePublished - Dec 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


  • MSC 15A60


Dive into the research topics of 'Approximating sparse binary matrices in the cut-norm'. Together they form a unique fingerprint.

Cite this