### Abstract

The cut-norm ||A||_{C} of a real matrix A=(a_{ij})_{i}∈R,_{j}∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity |Σ_{i}∈I,_{j}∈J^{a}_{ij}|. 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 |

### All Science Journal Classification (ASJC) codes

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

### Keywords

- MSC 15A60

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

## Cite this

Alon, N. (2015). Approximating sparse binary matrices in the cut-norm.

*Linear Algebra and Its Applications*,*486*, 409-418. [13340]. https://doi.org/10.1016/j.laa.2015.08.024