Improved rank bounds for design matrices and a new proof of Kelly's theorem

DOI10.1017/FMS.2014.2zbMATH Open1317.52020arXiv1211.0330OpenAlexW2132463883MaRDI QIDQ2879417FDOQ2879417

Authors: Zeev Dvir, A. Wigderson, Shubhangi Saraf 

Publication date: 1 September 2014

Published in: Forum of Mathematics, Sigma (Search for Journal in Brave)

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. (BDWY11) 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.

Full work available at URL: https://arxiv.org/abs/1211.0330

Recommendations

• Rank bounds for design matrices with block entries and geometric applications
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Fractional Sylvester–Gallai theorems
• On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs
• Sylvester-Gallai for arrangements of subspaces

Mathematics Subject Classification ID

Other designs, configurations (05B30) Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Theory of computing (68Q99)

Cites Work

• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• On the p-rank of the incidence matrix of a balanced or partially balanced incomplete block design and its applications to error correcting codes
• Polarities, quasi-symmetric designs, and Hamada's conjecture
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Complexity Lower Bounds using Linear Algebra
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Blackbox Polynomial Identity Testing for Depth 3 Circuits
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• The minimum rank of symmetric matrices described by a graph: a survey
• A survey of Sylvester's problem and its generalizations
• Incidence theorems and their applications
• On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
• On Double Diagonal and Cross Latin Squares
• From sylvester-gallai configurations to rank bounds
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• A Generalization of a Theorem of Sylvester on the Lines Determined by a Finite Point Set.
• A resolution of the Sylvester-Gallai problem of J.-P. Serre
• Scalings of matrices which have prespecified row sums and column sums via optimization
• Sylvester-Gallai theorems for complex numbers and quaternions
• Title not available (Why is that?)
• Tight Lower Bounds for 2-query LCCs over Finite Fields

Cited In (15)

• Sylvester-Gallai type theorems for approximate collinearity
• Lower bounds for 2-query LCCs over large alphabet
• On the p-rank of the design matrix of a difference set
• Rank bounds for design matrices with block entries and geometric applications
• On a conjecture of Kelly on (1, 3)-representation of Sylvester-Gallai designs
• Sylvester-Gallai for arrangements of subspaces
• Sylvester-Gallai for arrangements of subspaces
• A quantitative variant of the multi-colored Motzkin-Rabin theorem
• A generalized Sylvester–Gallai-type theorem for quadratic polynomials
• A generalized sylvester-gallai type theorem for quadratic polynomials
• A Sylvester-Gallai-type theorem for complex-representable matroids
• On the number of ordinary lines determined by sets in complex space
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Equiangular lines and spherical codes in Euclidean space
• Arithmetic circuits: a chasm at depth 3

This page was built for publication: Improved rank bounds for design matrices and a new proof of Kelly's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879417)