Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes
Zeev Dvir
Institute for Advanced Study
October 19, 2010
A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for $m\geq n$, the rank of any $(q,k,t)$-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least $n - (qtn/2k)^2$ .
Using this result we derive the following applications:
The early work of Condorcet in the eighteenth century, and that of Arrow and others in the twentieth century, revealed the complex and interesting mathematical problems that arise in the theory of social choice. In this lecture, Noga Alon, Visiting Professor in the School of Mathematics, explains how the simple process of voting leads to strikingly counter-intuitive paradoxes, focusing on several recent intriguing examples.