Rank bounds for design matrices with block entries and geometric applications

Rank bounds for design matrices with block entries and geometric applications, Discrete Analysis 2018:5, 24 pp.

It is not hard to prove, when the statement is suitably formulated, that if $A$ is a random matrix, then it is not possible to reduce the rank of $A$ by changing only a few entries. However, it is remarkably hard to find an explicit example of such a matrix. It turns out that explicit examples would have major applications in theoretical computer science, and therefore the matrix-rigidity problem is a central question in the area.

In order to make progress on this problem, one can ask a more basic question: are there any combinatorial conditions on a matrix that guarantee that it has a high rank? An interesting condition has recently been identified that does not solve the matrix-rigidity problem but that does have several applications, in particular to combinatorial geometry. Roughly speaking, the condition is that there should not be many non-zero entries in any row or too few non-zero entries in any column, and for any two rows the number of columns for which the entries in both rows are non-zero is small. Such matrices are known as design matrices, since the conditions resemble those for a design, though they are significantly looser.

The proof that such matrices have high rank uses a beautiful technique called matrix scaling. The rough idea is to multiply rows and columns by non-zero scalars until the entries are of broadly the same magnitude, and then to show that the matrix $A^*A$ is dominated by its diagonal. From this it follows fairly easily that $A^*A$ has high rank, and therefore that $A$ does as well. The argument can be found in a paper of Barak, Dvir, Wigderson and Yehudayoff that this paper generalizes.

Such rank bounds are useful, because there are several problems in combinatorial geometry that lead naturally to design matrices. For example, the Sylvester-Gallai theorem and its generalizations concern families of points and collinearity relations between them. If the points are $v_1,\dots,v_n$, then one can write them as column vectors and put them together to form a matrix $M$. Three of the points will be collinear if there is a linear dependence amongst the columns of this matrix with three non-zero coefficients, or equivalently a vector $w$ with three non-zero entries such that $Mw=0$. Under suitable hypotheses, one can use such vectors $w$ to create a design matrix and apply rank bounds on the design matrix to deduce combinatorial consequences about the set of points $v_1,\dots,v_n$.

The generalization in this paper concerns design matrices whose entries are themselves matrices, or “blocks”. Rank bounds are proved for such matrices, which lead to new applications in combinatorial geometry. One of these applications is to the following question. Let $T$ be a set of triples of elements of $\{1,2,\dots,n\}$ and let $V(T)$ be the variety of all sequences $(v_1,\dots,v_n)$ of points in $\mathbb C^d$ such that for every triple $\{i,j,k\}\in T$ the three points $v_i, v_j$ and $v_k$ are collinear. Given a (non-singular) sequence $V\in V(T)$, how many degrees of freedom does it have? A trivial lower bound is 8, resulting from the fact that projective transformations preserve collinearity. The authors prove a general result that has as a consequence that if every pair $\{i,j\}$ belongs to exactly one triple in $T$ and no line contains more than half the points of $V$, then the number of degrees of freedom of $V$ is at most 15. A more precise statement, as well as other interesting applications, can be found in the paper.