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 . Already before the break I had a couple of posts about bounding incidences in by applying a second polynomial partitioning. The current post describes a recent application of incidences in , concerning minors of matrices. It is taken from a recent paper by Miriam Farber, Saurabh Ray, and Shakhar Smorodinsky.
Miriam Farber, Saurabh Ray, and Shakhar Smorodinsky.
Recall that a minor of a matrix is the determinant of some square submatrix of . For example, the following figure depicts a matrix with a minor of -6 and a minor of -4.
(Unlike in the figure, the rows and columns of the submatrix are not required to be consecutive.) Let be an matrix where is a constant that does not depend on . What can be said about the number of equal minors of ? There are such minors, and if we take all of the rows of to be identical, all of these minors become zero. This is of course cheating, since a zero minor means that the corresponding rows of are not linearly independent. Can we get a large number of minors whose value is, say, 1?
Indeed we can! Consider a matrix whose determinant is 1. Now replicate each of the rows in this matrix times, to obtain an matrix. One can easily verify that this matrix consists of exactly 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 minors in an totally positive matrix.
Let be an matrix with no zero minors, and consider the maximum number of 1 minors. The main idea is to reduce the problem to an incidence problem in , as follows. Each row of is a -dimensional vector, and can thus also be considered as a point in . Denote the set of these points as . For every set of rows of , we consider the zero set of
This is a linear equation in , and thus defines a hyperplane. We denote the set of these hyperplanes as . Notice that a minor of 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 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 be two distinct sets of rows of . Then the two corresponding hyperplanes are not identical.
Proof. Consider a row which is in the set but not in the set . Let denote the value of the determinant of the matrix formed by the rows of together with , and let . Notice that the determinant of and is zero, while the determinant of and is 1. That is, the hyperplane that corresponds to is incident to the point and the hyperplane that corresponds to is not.
This property is not enough to obtain an interesting incidence problem. Theoretically, we can have all of the points of on a common line, and all of the hyperplanes of fully containing this line. This would lead to 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 intersect in at most points of .
Proof. Since no rows of are allowed to be linearly independent, no points of are on a common hyperplane that contains the origin. Any two non-parallel hyperplanes of intersect in a -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 can contain at most points of .
With this extra observation, the incidence problem is no longer trivial. The case is a planar incidence problem between lines and points. By using the Szemerédi–Trotter theorem, we obtain a bound of 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 points and a set of lines that determine point-line incidences, and to build a matrix that corresponds to this configuration. See the paper for more details.
For , 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 points and a set hyperplanes, both in , such that the intersection of any hyperplanes contains at most of the points, for some constants (i.e., the incidence graph does not contain a ). Then the number of point-hyperplane incidences is .
In our case there are points and hyperplanes. Therefore, we obtain an upper bound of . 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 points and a set hyperplanes, both in , such that the corresponding incidence graph does not contain a copy of . Then for any , the number of point-hyperplane incidences is .
Applying Theorem 4 to our scenario immediately implies a bound of on the number of 1 minors (recall that now we consider only the case ). Notice that the main term in the bound of Theorem 4 is significantly smaller, and that the bound 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.