OctoInformBeta

OpenAI preprint, September 2026 Β· Β§3. Pruning two families of pairs

The simultaneous choice of coefficients: Ranks of LL and N𝖳N^{\mathsf T} equal maximum matching sizes of their supports, and each Dp,iD^{p,i} has the largest rank on its local support

Coefficients on the arcs maximizing several ranks at once.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let β†’\to be a relation on a finite set XX, and let β„›\mathcal R and π’ž\mathcal C be families of pairs in XΓ—XX \times X. Pairs (p,j)βˆˆβ„›(p, j) \in \mathcal R and (i,s)βˆˆπ’ž(i, s) \in \mathcal C conflict when pβ†’ip \to i and sβ†’js \to j, and (i,j)(i, j) is the point of their conflict. Real coefficients axya_{xy} and bxyb_{xy} on the arcs xβ†’yx \to y fill a matrix LL from β„›\mathcal R to the points of conflicts, with entries apia_{pi}, a matrix NN from those points to π’ž\mathcal C, with entries bsjb_{sj}, and for every arc pβ†’ip \to i a local matrix Dp,iD^{p,i} with entries bsjb_{sj}. 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 GG is a set of edges of GG no two of which share an end✦; a matching of GG is maximum when no matching of GG has more edges.✦

A matrix DD over a field, with rows indexed by a finite set II and columns by a finite set JJ, is supported on a set of positions in IΓ—JI \times J when Dij=0D_{ij} = 0 at every position (i,j)(i, j) outside that set, and supported on a bipartite graph with sides II and JJ when it is supported on the edge set of that graph.✦

For a matrix DD with rows indexed by II and columns by JJ, and a matching M={(i1,j1),…,(im,jm)}M = \{(i_1, j_1), \dots, (i_m, j_m)\} of a bipartite graph with sides II and JJ, the minor of DD on MM is det⁡DM\det D_M, where DMD_M is the square submatrix that carries the entries DikjkD_{i_k j_k} of the matching on its diagonal: DM=(Dikjl)k,l=1m.D_M = \bigl(D_{i_k j_l}\bigr)_{k, l = 1}^{m}.(1)

Coefficients and Matrices

The coefficient variables are real variables axya_{xy} and bxyb_{xy}, one of each for every ordered pair (x,y)∈XΓ—X(x, y) \in X \times X; a choice of their values gives coefficients aa and bb.✦ A real function aa on XΓ—XX \times X vanishes off the arcs when axy=0a_{xy} = 0 for every pair with xβ†’ΜΈyx \not\to y.✦

The set ZZ of the families β„›\mathcal R and π’ž\mathcal C is the set of the points of their conflicts: Z={(i,j):(p,j)βˆˆβ„›,(i,s)βˆˆπ’ž,pβ†’i and sβ†’j for some p,s∈X}.Z = \{(i, j) : (p, j) \in \mathcal R,\ (i, s) \in \mathcal C,\ p \to i \text{ and } s \to j \text{ for some } p, s \in X\}.(2)✦

The matrix LL of coefficients aa is the real matrix with rows indexed by ZZ and columns by β„›\mathcal R whose entries are L(i,j),(p,jβ€²)={apiif j=jβ€²,0otherwise.L_{(i,j),(p,j')} = \begin{cases} a_{pi} & \text{if } j = j', \\ 0 & \text{otherwise}. \end{cases}(3)✦ The matrix NN of coefficients bb is the real matrix with rows indexed by π’ž\mathcal C and columns by ZZ whose entries are N(iβ€²,s),(i,j)={bsjif iβ€²=i,0otherwise.N_{(i',s),(i,j)} = \begin{cases} b_{sj} & \text{if } i' = i, \\ 0 & \text{otherwise}. \end{cases}(4)✦

The support of LL is the bipartite graph with sides ZZ and β„›\mathcal R in which (i,j)(i, j) is joined to (p,j)(p, j) whenever pβ†’ip \to i✦; the support of N𝖳N^{\mathsf T} is the bipartite graph with sides ZZ and π’ž\mathcal C in which (i,j)(i, j) is joined to (i,s)(i, s) whenever sβ†’js \to j✦.

For a point pp of XX, the fiber of β„›\mathcal R over pp is the set of points jj with (p,j)βˆˆβ„›(p, j) \in \mathcal R; the fiber of π’ž\mathcal C over a point ii is the set of points ss with (i,s)βˆˆπ’ž(i, s) \in \mathcal C.✦ For points pp and ii of XX, the local matrix Dp,iD^{p,i} of coefficients bb is the real matrix with rows indexed by the fiber of π’ž\mathcal C over ii and columns by the fiber of β„›\mathcal R over pp whose entries are Dsjp,i=bsj.D^{p,i}_{sj} = b_{sj}.(5)✦ The local support of Dp,iD^{p,i} is the set of its positions (s,j)(s, j) with sβ†’js \to j.✦

A real function bb on XΓ—XX \times X gives locally maximal ranks when, for every arc pβ†’ip \to i, every real matrix Dβ€²D' with the rows and columns of Dp,iD^{p,i} that is supported on the local support of Dp,iD^{p,i} satisfies rank⁡D′≀rank⁡Dp,i.\operatorname{rank} D' \le \operatorname{rank} D^{p,i}.(6)✦

The Claim

Theorem 1. Let DD be a matrix over a field, with rows indexed by a finite set II and columns by a finite set JJ. If SβŠ†IS \subseteq I and TβŠ†JT \subseteq J are such that every nonzero entry of DD lies in a row of SS or in a column of TT, then rank⁡D≀|S|+|T|.\operatorname{rank} D \le |S| + |T|.(7)✦ If DD is supported on a bipartite graph GG with sides II and JJ and MM is a maximum matching of GG, then rank⁡D≀|M|,\operatorname{rank} D \le |M|,(8)✦ and if moreover the minor det⁡DM\det D_M of DD on MM is nonzero, then rank⁡D=|M|.\operatorname{rank} D = |M|.(9)✦

Theorem 2. Let KK be an infinite field and qq a nonzero polynomial with coefficients in KK in variables tΞ»t_\lambda indexed by a set Ξ›\Lambda. Then there is a point c∈KΞ›c \in K^\Lambda with q(c)β‰ 0.q(c) \neq 0.(10)✦

Theorem 3. Let β†’\to be a relation on a finite set XX and let β„›\mathcal R and π’ž\mathcal C be families of pairs in XΓ—XX \times X. Let Ξ±\alpha be a maximum matching of the support of LL and Ξ²\beta a maximum matching of the support of N𝖳N^{\mathsf T}. Then there are real values of the variables axya_{xy} and bxyb_{xy} for which aa and bb vanish off the arcs, bb gives locally maximal ranks (6), and det⁡LΞ±β‰ 0,det⁡(N𝖳)Ξ²β‰ 0,rank⁡L=|Ξ±|,rank⁡N𝖳=|Ξ²|.\det L_\alpha \neq 0, \qquad \det\, (N^{\mathsf T})_\beta \neq 0, \qquad \operatorname{rank} L = |\alpha|, \qquad \operatorname{rank} N^{\mathsf T} = |\beta|.(11)✦

What Is Checked

The claim (11) is stated over a relation on a finite set XX, two families β„›\mathcal R and π’ž\mathcal C of pairs with the set ZZ of the points of their conflicts, the coefficient variables, the matrices LL, NN and Dp,iD^{p,i}, maximum matchings of the supports of LL and N𝖳N^{\mathsf T}, 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.