The Setting
Let be a relation on a finite set , and let and be families of pairs in . Pairs and conflict when and , and is the point of their conflict. Real coefficients and on the arcs fill a matrix from to the points of conflicts, with entries , a matrix from those points to , with entries , and for every arc a local matrix with entries . In each of these matrices the arcs fix which entries can be nonzero. Can one choice of the coefficients give all of them at once the largest rank this pattern allows?
Matchings and Supports
A matching of a bipartite graph is a set of edges of no two of which share an endβ¦; a matching of is maximum when no matching of has more edges.β¦
A matrix over a field, with rows indexed by a finite set and columns by a finite set , is supported on a set of positions in when at every position outside that set, and supported on a bipartite graph with sides and when it is supported on the edge set of that graph.β¦
For a matrix with rows indexed by and columns by , and a matching of a bipartite graph with sides and , the minor of on is , where is the square submatrix that carries the entries of the matching on its diagonal: (1)
Coefficients and Matrices
The coefficient variables are real variables and , one of each for every ordered pair ; a choice of their values gives coefficients and .β¦ A real function on vanishes off the arcs when for every pair with .β¦
The set of the families and is the set of the points of their conflicts: (2)β¦
The matrix of coefficients is the real matrix with rows indexed by and columns by whose entries are (3)β¦ The matrix of coefficients is the real matrix with rows indexed by and columns by whose entries are (4)β¦
The support of is the bipartite graph with sides and in which is joined to whenever β¦; the support of is the bipartite graph with sides and in which is joined to whenever β¦.
For a point of , the fiber of over is the set of points with ; the fiber of over a point is the set of points with .β¦ For points and of , the local matrix of coefficients is the real matrix with rows indexed by the fiber of over and columns by the fiber of over whose entries are (5)β¦ The local support of is the set of its positions with .β¦
A real function on gives locally maximal ranks when, for every arc , every real matrix with the rows and columns of that is supported on the local support of satisfies (6)β¦
The Claim
Theorem 1. Let be a matrix over a field, with rows indexed by a finite set and columns by a finite set . If and are such that every nonzero entry of lies in a row of or in a column of , then (7)β¦ If is supported on a bipartite graph with sides and and is a maximum matching of , then (8)β¦ and if moreover the minor of on is nonzero, then (9)β¦
Theorem 2. Let be an infinite field and a nonzero polynomial with coefficients in in variables indexed by a set . Then there is a point with (10)β¦
Theorem 3. Let be a relation on a finite set and let and be families of pairs in . Let be a maximum matching of the support of and a maximum matching of the support of . Then there are real values of the variables and for which and vanish off the arcs, gives locally maximal ranks (6), and (11)β¦
What Is Checked
The claim (11) is stated over a relation on a finite set , two families and of pairs with the set of the points of their conflicts, the coefficient variables, the matrices , and , maximum matchings of the supports of and , and the local supports with locally maximal ranks; (7), (8) and (9) are stated over matrices with entries in a field, sets of rows and columns covering their nonzero entries, and maximum matchings of a bipartite graph that supports them, and (10) over nonzero polynomials over an infinite field.