OctoInformBeta

OpenAI preprint, September 2026 ยท ยง3. Pruning two families of pairs

Lemma 3.2: If DD has the largest rank among real matrices supported on TT, then xjys=0x_j y_s = 0 whenever Dx=0Dx = 0, D๐–ณy=0D^{\mathsf{T}} y = 0 and (s,j)โˆˆT(s, j) \in T

Kernel products vanish where a maximum-rank matrix may be nonzero.

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 II and JJ be finite sets and TโІIร—JT \subseteq I \times J the edge set of a bipartite graph with sides II and JJ. A real Iร—JI \times J matrix DD, with rows indexed by II and columns by JJ, is supported on TT if its entries off the edges are zero: Dsj=0for every (s,j)โˆˆ(Iร—J)\T.D_{sj} = 0 \qquad \text{for every } (s, j) \in (I \times J) \setminus T.(1)โœฆ

Choose the entries on the edges so that DD has the largest rank among the real Iร—JI \times J matrices supported on TT, and take xโˆˆโ„Jx \in \mathbb{R}^J with Dx=0Dx = 0 and yโˆˆโ„Iy \in \mathbb{R}^I with D๐–ณy=0D^{\mathsf{T}} y = 0. The coordinates where xx is nonzero form a set of vertices on the side JJ, those where yy is nonzero a set on the side II. The question is whether an edge (s,j)(s, j) of TT can join the two sets, with ysโ‰ 0y_s \neq 0 and xjโ‰ 0x_j \neq 0.

The Claim

Theorem 1. Let II and JJ be finite sets, let TโІIร—JT \subseteq I \times J, and let DD be a real Iร—JI \times J matrix supported on TT whose rank is at least the rank of every real Iร—JI \times J matrix supported on TT. Then, for every (s,j)โˆˆT(s, j) \in T, xjys=0for all xโˆˆker⁡D and yโˆˆker⁡D๐–ณ.x_j\, y_s = 0 \qquad \text{for all } x \in \ker D \text{ and } y \in \ker D^{\mathsf{T}}.(2)โœฆ Equivalently, if xโˆˆโ„Jx \in \mathbb{R}^J and yโˆˆโ„Iy \in \mathbb{R}^I satisfy Dx=0Dx = 0 and D๐–ณy=0D^{\mathsf{T}} y = 0, and (s,j)โˆˆT(s, j) \in T, then xjys=0.x_j\, y_s = 0.(3)โœฆ

In the paper, the result reads: for TโІIร—JT \subseteq I \times J with II and JJ finite, if D:โ„Jโ†’โ„ID \colon \mathbb{R}^J \to \mathbb{R}^I has maximum rank among all real matrices supported on TT, then xjys=0x_j y_s = 0 for every xโˆˆker⁡Dx \in \ker D, yโˆˆker⁡D๐–ณy \in \ker D^{\mathsf{T}} and (s,j)โˆˆT(s, j) \in T.

What Is Checked

The claim is stated over the real matrices supported on a set TโІIร—JT \subseteq I \times J, as in (1), and over their rank.