OctoInformBeta

OpenAI preprint, October 2026 · §6. From matching factors to low-degree squares

Lemma 6.1 [Normalization of PSD factors]: Normalization at fixed order for finite pairings and the matching slack matrix

Positive semidefinite factors admit uniform trace bounds.

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

Normalization of a real positive semidefinite (PSD) trace factorization concerns the individual traces of its row and column factors. The question is to bound these traces while preserving the trace pairings and the common matrix order.

Let nn be a nonnegative integer, and let [n]={0,…,n−1}[n]=\{0,\ldots,n-1\} be the labeled vertex set of the complete graph KnK_n. An edge e=(u,v)e=(u,v) of KnK_n is a pair of vertices with u<vu<v; write EnE_n for the edge set.✦ A perfect matching MM on [n][n] is a finite subset of EnE_n in which every vertex is incident with exactly one edge.✦ The set ℳn\mathcal M_n consists of the perfect matchings on [n][n]. An odd cut is specified by a subset U⊆[n]U\subseteq[n] of odd cardinality.✦

For a vertex subset U⊆[n]U\subseteq[n], an edge ee of KnK_n crosses the cut δ(U)\delta(U) precisely when one endpoint belongs to UU and the other does not; δ(U)\delta(U) is the set of such edges. For a perfect matching MM on [n][n] and a vertex subset U⊆[n]U\subseteq[n], the crossing count cU(M)=|M∩δ(U)|c_U(M)=|M\cap\delta(U)| is the number of edges of MM crossing δ(U)\delta(U).✦ The matching slack matrix Tn(0)T_n(0) has columns indexed by ℳn\mathcal M_n and rows indexed by the disjoint union ℛn\mathcal R_n of EnE_n and the odd cuts, with entries (1). Tn(0)i,M={𝟏{e∈M},i=e∈En,cU(M)−1,i=U an odd cut.T_n(0)_{i,M}= \begin{cases} \mathbf{1}_{\{e\in M\}}, & i=e\in E_n,\\ c_U(M)-1, & i=U\text{ an odd cut}. \end{cases}(1)✦

For a nonnegative integer rr, let 𝕊+r\mathbb S_+^r denote the cone of real PSD r×rr\times r matrices. A real PSD factorization of order rr of Tn(0)T_n(0) is a pair of families Ai,BM∈𝕊+rA_i,B_M\in\mathbb S_+^r, indexed by i∈ℛni\in\mathcal R_n and M∈ℳnM\in\mathcal M_n, satisfying (2). Tn(0)i,M=tr⁡(AiBM)(i∈ℛn,M∈ℳn).T_n(0)_{i,M}=\operatorname{tr}(A_iB_M) \qquad(i\in\mathcal R_n,\ M\in\mathcal M_n).(2)✦

The Claim

Theorem 1 (Normalization of PSD factors). Let JJ and II be finite sets, with II nonempty. Let Aa,Bb∈𝕊+rA_a,B_b\in\mathbb S_+^r for a∈Ja\in J and b∈Ib\in I, and let m∈ℝm\in\mathbb R satisfy tr⁡(AaBb)≤m\operatorname{tr}(A_aB_b)\le m for every a,ba,b. There are families Aa′,Bb′∈𝕊+rA'_a,B'_b\in\mathbb S_+^r such that tr⁡(Aa′Bb′)=tr⁡(AaBb)(a∈J,b∈I),tr⁡(Aa′)≤m+1(a∈J),tr⁡(Bb′)≤r(b∈I).\begin{aligned} \operatorname{tr}(A'_aB'_b)&=\operatorname{tr}(A_aB_b) && (a\in J,\ b\in I),\\ \operatorname{tr}(A'_a)&\le m+1 && (a\in J),\\ \operatorname{tr}(B'_b)&\le r && (b\in I). \end{aligned}(3)✦

Let nn be even and positive, and suppose that Tn(0)T_n(0) has a real PSD factorization of order rr. There are families Fi,GM∈𝕊+rF_i,G_M\in\mathbb S_+^r such that tr⁡(FiGM)=Tn(0)i,M(i∈ℛn,M∈ℳn),tr⁡(Fi)≤n+1(i∈ℛn),tr⁡(GM)≤r(M∈ℳn).\begin{aligned} \operatorname{tr}(F_iG_M)&=T_n(0)_{i,M} && (i\in\mathcal R_n,\ M\in\mathcal M_n),\\ \operatorname{tr}(F_i)&\le n+1 && (i\in\mathcal R_n),\\ \operatorname{tr}(G_M)&\le r && (M\in\mathcal M_n). \end{aligned}(4)✦

In the paper, the result reads: a finite nonzero nonnegative matrix SS with entries at most bb and a real PSD factorization of order r0r_0 has a real PSD factorization of an order r≤r0r\le r_0 whose row factors FaF_a and column factors GjG_j satisfy tr⁡(Fa)≤b\operatorname{tr}(F_a)\le b and tr⁡(Gj)≤r\operatorname{tr}(G_j)\le r.

What Is Checked

The normalization in (3) is stated over finite families of real PSD matrices with a nonempty column index set and a common upper bound on their trace pairings; (4) concerns factorizations of the edge and odd-cut slack matrix on an even positive number of vertices.