Perturbed identity matrices have high rank: Proof and applications

Noga Alon

doi:10.1017/S0963548307008917

Perturbed identity matrices have high rank: Proof and applications

Noga Alon

Research output: Contribution to journal › Article › peer-review

70 Scopus citations

Abstract

We describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries, and discuss several applications of this result to the study of problems in Geometry, Coding Theory, Extremal Finite Set Theory and Probability. This is partly a survey, containing a unified approach for proving various known results, but it contains several new results as well.

Original language	English (US)
Pages (from-to)	3-15
Number of pages	13
Journal	Combinatorics Probability and Computing
Volume	18
Issue number	1-2
DOIs	https://doi.org/10.1017/S0963548307008917
State	Published - Mar 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548307008917

Cite this

@article{1d3e434200cc41c5a63929e4a99cf056,

title = "Perturbed identity matrices have high rank: Proof and applications",

abstract = "We describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries, and discuss several applications of this result to the study of problems in Geometry, Coding Theory, Extremal Finite Set Theory and Probability. This is partly a survey, containing a unified approach for proving various known results, but it contains several new results as well.",

author = "Noga Alon",

year = "2009",

month = mar,

doi = "10.1017/S0963548307008917",

language = "English (US)",

volume = "18",

pages = "3--15",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "1-2",

}

TY - JOUR

T1 - Perturbed identity matrices have high rank

T2 - Proof and applications

AU - Alon, Noga

PY - 2009/3

Y1 - 2009/3

N2 - We describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries, and discuss several applications of this result to the study of problems in Geometry, Coding Theory, Extremal Finite Set Theory and Probability. This is partly a survey, containing a unified approach for proving various known results, but it contains several new results as well.

AB - We describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries, and discuss several applications of this result to the study of problems in Geometry, Coding Theory, Extremal Finite Set Theory and Probability. This is partly a survey, containing a unified approach for proving various known results, but it contains several new results as well.

UR - http://www.scopus.com/inward/record.url?scp=67649235151&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67649235151&partnerID=8YFLogxK

U2 - 10.1017/S0963548307008917

DO - 10.1017/S0963548307008917

M3 - Article

AN - SCOPUS:67649235151

SN - 0963-5483

VL - 18

SP - 3

EP - 15

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 1-2

ER -

Perturbed identity matrices have high rank: Proof and applications

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this