Skip to main content

# Improved Rank Bounds for Design Matrices and a New Proof of Kelly's Theorem

## Author(s): Dvir, Zeev; Saraf, Shubhangi; Wigderson, Avi

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1j24n
 Abstract: We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus of a recent work by Barak et al. [Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC 11, (ACM, NY 2011), 519–528] in which they were used to answer questions regarding point configurations. In this work, we derive near-optimal rank bounds for these matrices and use them to obtain asymptotically tight bounds in many of the geometric applications. As a consequence of our improved analysis, we also obtain a new, linear algebraic, proof of Kelly’s theorem, which is the complex analog of the Sylvester–Gallai theorem. Publication Date: 2014 Citation: Dvir, Zeev, Shubhangi Saraf, and Avi Wigderson. "Improved Rank Bounds for Design Matrices and a New Proof of Kelly's Theorem." Forum of Mathematics, Sigma 2 (2014): pp. e4:1-e4:24. doi:10.1017/fms.2014.2 DOI: 10.1017/fms.2014.2 ISSN: 2050-5094 Pages: e4:1 - e4:24 Type of Material: Journal Article Journal/Proceeding Title: Forum of Mathematics, Sigma Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.