The Setting
The problem is to count approximately the common bases of two matroids and on elements, both given by one independence oracle. Most of the analysis works over a finite set with a list of disjoint pairs of its elements and a positive weight on the subsets of , and the matroids enter only through one spectral hypothesis on , the slot signature property.
The weight in question here is the rank weight of a matroid on with rank function , for , and the question is whether it meets that hypothesis.
Derivatives and Face Hessians
A real function on the subsets of stands for the multiaffine polynomial in the variables , , (1)
The derivative of along a vector is the real function on the subsets of given by (2)✦ the coefficient function of the derivative of (1) in the direction . The derivative along a list of vectors is , which is for the empty list.✦
The slot direction of a set is its indicator vector , with entries on and elsewhere.✦ The pair direction of a pair of elements of is .✦ The slot total of along a list of pairs of elements of is the real function (3)✦ on the subsets of . When the pairs are disjoint and avoid a set , the value is the sum of over the sets obtained from by adding one element of each pair.
The face Hessian of at a set is the real symmetric matrix indexed by with zero diagonal and off-diagonal entries (4)✦ the Hessian at the origin of the derivative of (1) in the variables of , restricted to the remaining variables.
A bilinear form on a real vector space has one positive direction when, for all , (5)✦ For a symmetric form this says that has at most one positive eigenvalue. A real square matrix has one positive direction when the form does.
A real function on the subsets of is fully positive of order when (6)✦
The slot signature property of a real function on the subsets of is the condition that the face Hessian has one positive direction for every list of pairs of elements of and every set .✦
The Rank Weight
Let be a matroid with ground set and rank function , and let be a real number. The rank weight of at is the real function on the subsets of given by (7)✦ The pair matrix of at is the real symmetric matrix indexed by with zero diagonal and off-diagonal entries (8)✦
The Claim
Theorem 1. (a) Let be a matroid with ground set and rank function , let , and let and be the rank weight and the pair matrix of at . Then each of the following matrices has one positive direction: the pair matrix (9)✦ for every set , the face Hessian (10)✦ for every list of vectors in with nonnegative entries and every set , the face Hessian (11)✦ for every list of subsets of , every set , every finite set and every real matrix with rows indexed by and columns indexed by , the matrix (12)✦ The rank weight (13)✦ has the slot signature property.
(b) Let be a real function on the subsets of that is fully positive of order and whose face Hessians , , all have one positive direction, and let have positive entries. Then for every set the face Hessian (14)✦ has one positive direction.
In the paper, the result reads: for a matroid on and , the polynomial is Lorentzian, Lorentzian polynomials are closed under partial derivatives and nonnegative linear substitutions, and quadratic ones have at most one positive eigenvalue, so has the quadratic signature property. Here is the coefficient of in .
What Is Checked
The claim is stated over a matroid with ground set and , its rank weight (7) and pair matrix (8), a real function on the subsets of fully positive of order (6), derivatives (2) along vectors and along slot directions, slot totals (3), face Hessians (4), one positive direction (5) and the slot signature property.