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

This is a linear equation in x_1,\ldots,x_d  , and thus defines a hyperplane. We denote the set of these \binom{n}{d-1}  hyperplanes as {\cal H}  . Notice that a minor of M  equals 1 if and only if the point that corresponds to the last row of the minor is incident to the hyperplane that corresponds to the other d-1  rows. That is, it suffices to upper bound the number of point-hyperplane incidences. For the incidence problem to make sense, we first require the following property.

Lemma 1. Let R_1,R_2  be two distinct sets of d-1  rows of M  . Then the two corresponding hyperplanes are not identical.

Proof.     Consider a row r  which is in the set R_1  but not in the set R_2  . Let D  denote the value of the determinant of the matrix formed by the rows of R_2  together with r  , and let r'=r/D  . Notice that the determinant of R_1  and r'  is zero, while the determinant of R_2  and r'  is 1. That is, the hyperplane that corresponds to R_2  is incident to the point r'\in{\mathbb R}^d  and the hyperplane that corresponds to R_1  is not.     \Box

This property is not enough to obtain an interesting incidence problem. Theoretically, we can have all of the points of \cal P  on a common line, and all of the hyperplanes of \cal H  fully containing this line. This would lead to \Theta(n^d)  incidences, and to the trivial bound on the number of 1 minors. That is why we also require the following observation.

Lemma 2. Any pair of hyperplanes of \cal H  intersect in at most d-1  points of \cal P  .

Proof.     Since no d  rows of M  are allowed to be linearly independent, no d  points of \cal P  are on a common hyperplane that contains the origin. Any two non-parallel hyperplanes of \cal H  intersect in a (d-2)  -dimensional flat. By definition, any such flat is fully contained in a hyperplane that contains the origin. Thus, the intersection of any two hyperplanes of \cal H  can contain at most d-1  points of \cal P  .     \Box

With this extra observation, the incidence problem is no longer trivial. The case d=2  is a planar incidence problem between n  lines and n  points. By using the Szemerédi–Trotter theorem, we obtain a bound of O(n^{4/3})  on the number of 1 minors. Somewhat surprisingly, this bound is also tight. The basic idea behind the lower bound is to consider a set of n/2  points and a set of n/2  lines that determine \Theta(n^{4/3})  point-line incidences, and to build a matrix that corresponds to this configuration. See the paper for more details.

For d\ge 3  , Farber, Ray, and Smorodinsky apply the following incidence bound by Apfelbaum and Sharir (which is a minor improvement over a previous bound of Brass and Knauer).

Theorem 3 (Apfelbaum and Sharir; Brass and Knauer). Consider a set of m  points and a set n  hyperplanes, both in {\mathbb R}^d  , such that the intersection of any r  hyperplanes contains at most s  of the points, for some constants r,s  (i.e., the incidence graph does not contain a K_{r,s}  ). Then the number of point-hyperplane incidences is O\left((mn)^{d/(d+1)}+m+n\right)  .

In our case there are n  points and \Theta(n^{d-1})  hyperplanes. Therefore, we obtain an upper bound of O\left(n^{d^2/(d+1)}\right) = O\left(n^{d-d/(d+1)}\right)  . This is the bound that is presented in the paper, though a slightly improved bound can be obtained by using a different incidence bound. The following incidences result is a variant of Theorem 8 from this paper by Elekes and Szabo.

Theorem 4 (Elekes and Szabo). Consider a set of m  points and a set n  hyperplanes, both in {\mathbb R}^d  , such that the corresponding incidence graph does not contain a copy of K_{r,s}  . Then for any \varepsilon>0  , the number of point-hyperplane incidences is O\left(m^{2(d-1)/(2d-1)+2\varepsilon}n^{d/(2d-1))-\varepsilon}+m+n\right)  .

Applying Theorem 4 to our scenario immediately implies a bound of O(n^{d-1})  on the number of 1 minors (recall that now we consider only the case d\ge 3). Notice that the main term in the bound of Theorem 4 is significantly smaller, and that the bound O(n^{d-1})  is just the number of hyperplanes. That is, to obtain an improved bound for the number of incidences, one has to somehow decrease the number of hyperplanes.

Advertisements

One thought on “Incidences and Repeated Minors of Matrices

  1. Pingback: Incidences and the Sum-Product Problem | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s