Perturbed Identity Matrices have High Rank: Proof and some Applications

Kishor Barman School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road
Friday, 14 May 2010 (all day)
A-212 (STCS Seminar Room)
We will discuss a lower bound (due to Noga Alon) on the rank of any real matrix in which all the diagonal entries are significantly larger (in absolute value) than all the other entries. The fact that such matrices have high rank, has helped in proving various results in combinatorics. In this talk, we would see some applications to - Geometry (we would see that the bound obtained by the Johnson-Lindenstrauss lemma is almost tight), and - Coding theory (we would see an upper bound on the size of an Epsilon-balanced code).

(See Perturbed identity matrices have high rank: proof and application by Noga Alon for more details).