OctoInformBeta

OpenAI preprint, October 2026 · §1. Introduction

§1 (setting): matching matrices and real PSD rank: The unshifted slack matrix Tn(0)T_n(0) with edge and odd-cut rows and its least positive factor order

Real positive semidefinite rank of matching matrices.

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

Matching slack matrices pair the edge constraints and odd-cut constraints of a complete graph with its perfect matchings. The parameter of interest in semidefinite extension complexity is the order of real matrix factors.

The Definition

Definition 1. Let nn be a nonnegative integer and let Vn={0,…,n−1}V_n=\{0,\ldots,n-1\} be the vertex set. An edge e=(u,v)e=(u,v) of the complete graph on VnV_n is a pair of distinct vertices with u<vu<v, as in (1). En={(u,v)∈Vn×Vn:u<v}.E_n=\{(u,v)\in V_n\times V_n:u<v\}.(1)✦

The perfect matching condition 𝖯𝖬n(M)\mathsf{PM}_n(M) for an edge set M⊆EnM\subseteq E_n is the condition that exactly one edge of MM is incident with each vertex of VnV_n, as in (2). 𝖯𝖬n(M)⇔|{(u,w)∈M:u=v or w=v}|=1for every v∈Vn.\mathsf{PM}_n(M) \quad\Longleftrightarrow\quad \bigl|\{(u,w)\in M:u=v\text{ or }w=v\}\bigr|=1 \quad\text{for every }v\in V_n.(2)✦

The family ℳn\mathcal M_n of perfect matchings of the complete graph on VnV_n consists of the edge sets M⊆EnM\subseteq E_n satisfying 𝖯𝖬n(M)\mathsf{PM}_n(M), as specified in (3). ℳn={M⊆En:𝖯𝖬n(M)}.\mathcal M_n=\{M\subseteq E_n:\mathsf{PM}_n(M)\}.(3)✦

An odd-cut index is a vertex subset U⊆VnU\subseteq V_n of odd cardinality; these indices form the family 𝒪n\mathcal O_n in (4). 𝒪n={U⊆Vn:|U| is odd}.\mathcal O_n=\{U\subseteq V_n:|U|\text{ is odd}\}.(4)✦

The row set RnR_n is the disjoint union of the edge indices and odd-cut indices in (5). Rn=En⊔𝒪n.R_n=E_n\sqcup\mathcal O_n.(5)✦

An edge e=(u,v)∈Ene=(u,v)\in E_n crosses a vertex subset U⊆VnU\subseteq V_n when exactly one endpoint lies in UU; the cut δ(U)\delta(U) consists of these edges, according to (6). e∈δ(U)⇔(u∈U and v∉U) or (u∉U and v∈U).e\in\delta(U) \quad\Longleftrightarrow\quad (u\in U\text{ and }v\notin U) \text{ or }(u\notin U\text{ and }v\in U).(6)✦

The crossing count cU(M)c_U(M) of a perfect matching M∈ℳnM\in\mathcal M_n across U⊆VnU\subseteq V_n is the number of its edges in δ(U)\delta(U), given by (7). cU(M)=|M∩δ(U)|.c_U(M)=|M\cap\delta(U)|.(7)✦

The unshifted matching slack matrix Tn(0)∈ℝRn×ℳnT_n(0)\in\mathbb R^{R_n\times\mathcal M_n} is the matrix whose entries are defined in (8), where 𝟏{e∈M}\mathbf 1_{\{e\in M\}} is the indicator of membership of ee in MM. Tn(0)i,M={𝟏{e∈M},i=e∈En,cU(M)−1,i=U∈𝒪n.T_n(0)_{i,M}= \begin{cases} \mathbf 1_{\{e\in M\}},&i=e\in E_n,\\ c_U(M)-1,&i=U\in\mathcal O_n. \end{cases}(8)✦

For r∈ℕr\in\mathbb N, let 𝕊+r\mathbb S_+^r be the cone of real symmetric positive semidefinite (PSD) matrices of order rr. A real PSD trace factorization of Tn(0)T_n(0) of order rr consists of families (Ai)i∈Rn(A_i)_{i\in R_n} and (BM)M∈ℳn(B_M)_{M\in\mathcal M_n} in 𝕊+r\mathbb S_+^r satisfying the trace identities in (9); write 𝖥n(r)\mathsf F_n(r) for the existence of such a factorization. 𝖥n(r)⇔∃(Ai)i∈Rn,(BM)M∈ℳn⊆𝕊+r,Tn(0)i,M=tr⁡(AiBM)for every i∈Rn,M∈ℳn.\mathsf F_n(r)\quad\Longleftrightarrow\quad \exists\,(A_i)_{i\in R_n},(B_M)_{M\in\mathcal M_n}\subseteq\mathbb S_+^r, \qquad T_n(0)_{i,M}=\operatorname{tr}(A_iB_M) \quad\text{for every }i\in R_n,\ M\in\mathcal M_n.(9)✦

The real PSD rank rank⁡psdTn(0)\operatorname{rank}_{\mathrm{psd}}T_n(0) of Tn(0)T_n(0) is the least positive integer rr for which Tn(0)T_n(0) admits a real PSD trace factorization of order rr, as in (10). rank⁡psdTn(0)=min⁡{r∈ℕ:r≥1 and 𝖥n(r)}.\operatorname{rank}_{\mathrm{psd}}T_n(0) =\min\{r\in\mathbb N:r\geq1\text{ and }\mathsf F_n(r)\}.(10)✦

In the paper, the result reads: for even n≥4n\geq4 and 0≤ρ≤10\leq\rho\leq1, the matrix An(ρ)A_n(\rho) has columns indexed by perfect matchings MM of the complete graph KnK_n on VnV_n and rows indexed by odd vertex subsets UU, with entries An(ρ)U,M=|M∩δ(U)|−1+ρA_n(\rho)_{U,M}=|M\cap\delta(U)|-1+\rho; Tn(ρ)T_n(\rho) additionally has one row for each edge ee, with entry 11 when e∈Me\in M and 00 otherwise; and real PSD rank is the least integer r≥1r\geq1 admitting an exact trace factorization by real symmetric PSD matrices of order rr, with no equivariance or rank restrictions.

What Is Checked

The rank in (10) is defined for every nonnegative integer nn using the row and matching sets in (5) and (3) and the real trace factorizations in (9).