The Structure of Low Rank Matrices
summary
Problem: characterize N×N matrices with rank r and a constant fraction of zeros and find how large a zero rectangle must exist. Concrete conjecture: every such matrix has a zero rectangle of size ≳ N^2 / 2^{Θ(√r)}; an explicit product construction using all 0–1 vectors of Hamming weight ~√r shows that bound is tight. Motivations and implications include log-rank conjecture, matrix rigidity, and two-source extractors. Tools and partial results: discrepancy amplification, geometric/zero–one arguments over R give N^2 / 2^{O(√r·log n)}, and over F2 only weaker or conditional bounds (PFR-based) are known.
AI-written summary · about