Incidences and Repeated Minors of Matrices

Finally, my blogging break is over, and I plan to return to blogging regularly.

One of the topics that I wish to focus on now is incidences in {\mathbb R}^d  . Already before the break I had a couple of posts about bounding incidences in {\mathbb R}^3  by applying a second polynomial partitioning. The current post describes a recent application of incidences in {\mathbb R}^d  , concerning minors of matrices. It is taken from a recent paper by Miriam Farber, Saurabh Ray, and Shakhar Smorodinsky.

FarbersaurabhrayShakharSmorodinsky-m

Miriam Farber, Saurabh Ray, and Shakhar Smorodinsky.

Recall that a minor of a matrix M  is the determinant of some square submatrix of M  . For example, the following figure depicts a matrix with a minor of -6 and a minor of -4.

minor

(Unlike in the figure, the rows and columns of the submatrix are not required to be consecutive.) Let M  be an n \times d  matrix where d  is a constant that does not depend on n  . What can be said about the number of equal d\times d  minors of M  ? There are \binom{n}{d} =   \Theta(n^d)  such minors, and if we take all of the rows of M  to be identical, all of these minors become zero. This is of course cheating, since a zero minor means that the d  corresponding rows of M  are not linearly independent. Can we get a large number of minors whose value is, say, 1?

Indeed we can! Consider a d\times d  matrix whose determinant is 1. Now replicate each of the rows in this matrix n/d  times, to obtain an n\times d  matrix. One can easily verify that this matrix consists of exactly (n/d)^d  one minors. However, notice that the majority of the minors in this matrix are still zero. The question becomes more interesting when we do not allow our matrix to contain zero minors.

The analysis of Farber, Ray, and Smorodinsky works for the case when there are no zero minors, though they only mention it for the significantly more constrained case of totally positive matrices. My guess is that they specifically focus on such matrices since they are more well known and have many applications. Moreover, this seems to be a special case of a more general question concerning repeated d  \times d  minors in an n\times n  totally positive matrix.

Let M  be an n \times d  matrix with no zero d\times d  minors, and consider the maximum number of 1 minors. The main idea is to reduce the problem to an incidence problem in {\mathbb R}^d  , as follows. Each row of M  is a d  -dimensional vector, and can thus also be considered as a point in {\mathbb R}^d  . Denote the set of these n  points as {\cal P}  . For every set of d-1  rows v^{(1)},\ldots,v^{(d-1)}  of M  , we consider the zero set of

hyperMatrix

Continue reading