Skip to main content

Rank bounds for design matrices with block entries and geometric applications

Author(s): Dvir, Zeev; Garg, Ankit; Oliveira, Rafael; Solymosi, József

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.contributor.authorGarg, Ankit-
dc.contributor.authorOliveira, Rafael-
dc.contributor.authorSolymosi, József-
dc.identifier.citationDvir, Zeev, Ankit Garg, Rafael Oliveira, and József Solymosi. "Rank bounds for design matrices with block entries and geometric applications." Discrete Analysis (2018): pp. 1 - 24. doi:10.19086/da.3118en_US
dc.description.abstractDesign matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point sets with many collinear triples. In this work we consider design matrices with block (or matrix) entries. Our main result is a lower bound on the rank of such matrices, extending the bounds proven in [BDWY12, DSW14] for the scalar case. As a result we obtain several applications in combinatorial geometry. The first application involves extending the notion of structural rigidity (or graph rigidity) to the setting where we wish to bound the number of ‘degrees of freedom’ in perturbing a set of points under collinearity constraints (keeping some family of triples collinear). Other applications are an asymptotically tight Sylvester-Gallai type result for arrangements of subspaces (improving [DH16]) and a new incidence bound for high dimensional line/curve arrangements. The main technical tool in the proof of the rank bound is an extension of the technique of matrix scaling to the setting of block matrices. We generalize the definition of doubly stochastic matrices to matrices with block entries and derive sufficient conditions for a doubly stochastic scaling to exist.en_US
dc.format.extent1 - 24en_US
dc.relation.ispartofDiscrete Analysisen_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleRank bounds for design matrices with block entries and geometric applicationsen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
RankBoundsDesignMatricesBlockEntries.pdf384.37 kBAdobe PDFView/Download

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