Perfect matching: why exact semidefinite descriptions must be large

← All digests

Family 126 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Some optimization problems are easy to solve but difficult to describe compactly in a particular mathematical language. Perfect matching is a striking example. A perfect matching pairs every vertex of a graph with exactly one other vertex, using permitted edges. Efficient algorithms can optimize edge weights over such pairings.

One might therefore hope to express all perfect matchings through a small system of convex constraints, then use a general optimization solver. Linear descriptions are already known to require exponential size, even when auxiliary variables are allowed. Semidefinite constraints are more expressive: they require a symmetric matrix to have no negative eigenvalues and can compress some structures that linear inequalities describe poorly.

Does that extra expressive power make a compact exact description of perfect matching possible? This manuscript claims an exponential lower bound even for unrestricted real semidefinite formulations. It strengthens the statement by treating a family of positively shifted matching matrices, where the entries that were originally zero become positive.

The distinction between solving and representing is central. The claim does not make matching computationally intractable. It limits one general-purpose way of encoding its entire feasible region.

2. Background and essential definitions

Let $K_n$ be the complete graph on an even number $n$ of vertices. A perfect matching $M$ contains $n/2$ disjoint edges. Its incidence vector $\mathbf1_M$ has one coordinate per edge, equal to one when that edge belongs to $M$, and zero otherwise.

The perfect matching polytope is

$$P_n=\operatorname{conv}\{\mathbf1_M:M\text{ is a perfect matching of }K_n\}.$$

Here $\operatorname{conv}$ means all convex combinations. Points in the polytope can be interpreted as averages of perfect matchings, and optimizing a linear edge-weight objective over it gives the same optimum as optimizing over individual matchings.

For a vertex set $U$, let $\delta(U)$ be the edges with exactly one endpoint in $U$. If $|U|$ is odd, any perfect matching crosses this cut an odd positive number of times. Thus

$$|M\cap\delta(U)|\ge1.$$

The difference $|M\cap\delta(U)|-1$ is the slack of this inequality at $M$: the amount by which the inequality exceeds equality.

A real symmetric matrix $A$ is positive semidefinite, abbreviated PSD, if $v^{\mathsf T}Av\ge0$ for every real vector $v$. A semidefinite lift represents a polytope as an affine image of an affine slice of the cone of PSD matrices. Auxiliary coordinates are allowed; the lift’s size is the matrix dimension.

For a nonnegative matrix $S$, its PSD rank is the least $r$ for which PSD matrices $F_u,G_v$ of size $r$ satisfy

$$S_{u,v}=\operatorname{tr}(F_uG_v)$$

for every row and column. The trace is the sum of diagonal entries. A general factorization theorem connects PSD rank of slack matrices to the smallest semidefinite lift.

3. Development history and previous partial results

Edmonds’s 1965 description established the role of degree equations, nonnegative edge coordinates, and odd-cut inequalities in the matching polytope. There are exponentially many odd vertex sets, but that alone does not prove that every possible formulation must be large: extra variables can sometimes replace many inequalities by a much smaller system.

Yannakakis developed the factorization approach to this question and proved strong lower bounds for symmetric linear formulations. Symmetry restrictions require the representation to respect relabeling of the original problem in a specified way. Rothvoß later removed that restriction and proved exponential linear extension complexity for matching.

Semidefinite lifts remained a separate issue. Gouveia, Parrilo, and Thomas established the cone-factorization framework, while Lee, Raghavendra, and Steurer developed general lower-bound methods connecting semidefinite formulations to sums of squares and low-degree obstructions.

For matching specifically, Braun and collaborators proved that there is no small coordinate-symmetric semidefinite formulation. That is not the same as excluding arbitrary formulations: a small representation might encode vertices in an asymmetric way. Braun and Pokutta also proved exponential nonnegative rank for the positively shifted matching matrices considered here, a result about scalar nonnegative factorizations rather than PSD factors.

A further boundary comes from approximation. Kaniewski, Lee, and de Wolf constructed matrices of subexponential PSD rank that approximate unshifted matching slacks with extremely small entrywise error. Their query-complexity paper therefore makes exactness especially important. An exact lower bound cannot simply be described as an equally strong barrier to every numerical approximation.

4. What the new manuscripts claim

For every fixed real $\rho\in(0,1)$, form the matrix indexed by odd vertex sets $U$ and perfect matchings $M$:

$$A_n(\rho)_{U,M}=|M\cap\delta(U)|-1+\rho.$$

The manuscript states that there is an absolute $c>0$ such that, for all sufficiently large even $n$,

$$\operatorname{rank}_{\mathrm{psd}}A_n(\rho)\ge2^{cn}.$$

The threshold for “sufficiently large” may depend on $\rho$, but the exponential rate $c$ does not. The factors are arbitrary real PSD matrices: there is no imposed symmetry, sparsity, coordinate action, or bound on numerical precision. They must reproduce every entry exactly.

The statement implies an exponential lower bound for the unshifted matrix $A_n(0)$. Indeed, adding one scalar block to an unshifted factorization can supply the constant $\rho$, increasing its size by at most one. If the shifted matrix requires exponential size, the original does too.

Adding the nonnegativity rows gives a slack matrix for the full matching polytope. The manuscript consequently claims that every exact real semidefinite lift of $P_n$ has exponential size.

The endpoint $\rho=1$ is deliberately excluded. At that value, the entries are simply $|M\cap\delta(U)|$, which have a diagonal PSD factorization indexed by the $\binom n2$ edges. Thus the transition at the endpoint is substantial: every fixed shift below one is claimed to require exponential size, while one itself permits polynomial size.

5. Why the advance matters

Provisional importance: 4/5. The claim would establish a strong limitation on unrestricted semidefinite representations of a central combinatorial polytope. It extends the separation between efficient optimization and concise convex formulation from linear programming to a more expressive framework.

The absence of symmetry assumptions is important. A representation lower bound is stronger when it allows all possible ways of choosing auxiliary coordinates, including ones with no visible relationship to the graph’s labels. The positive-shift theorem also shows that the proposed obstruction is not merely a count of exact zeros in the ordinary slack matrix.

The result would inform the limits of generic optimization formulations, rather than invalidate specialized matching algorithms. It also adds to the broader study of when positivity can be certified with low-complexity algebraic expressions. The methods may be useful elsewhere, but such extensions require separate arguments.

The score reflects the generality of the representation barrier. It does not imply a matching lower bound for every approximate relaxation or every algorithm that happens to use semidefinite programming as one component.

6. The main idea

Start with a globally inconsistent parity pattern

The proof strategy begins on an auxiliary expanding graph. Each incidence between a vertex and an edge receives a bit. At each vertex, the bits must have a prescribed parity, meaning a specified sum modulo two. Choose these parity requirements so that their total is odd.

If the two incidence bits on every edge agreed, summing the vertex constraints would count each edge bit twice, producing an even total. Therefore at least one edge must disagree. Subtracting $1-\rho$ from the number of disagreements gives a function that is positive on every legitimate assignment.

Local information can nevertheless fail to detect this global contradiction. The manuscript constructs a linear functional that behaves nonnegatively on squares of sufficiently low-complexity functions, yet assigns a negative value to this particular positive function. Such a functional is a certificate that the function cannot have the required low-degree sum-of-squares representation.

Encode the obstruction inside matching

Each auxiliary vertex is replaced by a cell containing a fixed number of matching vertices. Designated terminals represent incidences; the remaining vertices are paired internally. Restrictions on cuts make the internal pairs contribute no crossing edges. The crossing count then records precisely the disagreements in the parity construction.

This places the algebraic obstruction inside the shifted matching matrix. The remaining challenge is to show that a small PSD factorization would yield a low-complexity sum-of-squares representation of the obstructed function.

Average without discarding matrix information

PSD matrices admit square-root factorizations, suggesting a connection with sums of squares. But averaging squares is not the same as squaring averages. Replacing one by the other would lose essential information.

The manuscript instead builds an exact decomposition into several matrix-valued branches. Fourier characters on the incidence bits organize each branch by the vertex blocks it involves. Local averaging within cells makes high-complexity contributions small, with bounds that do not grow with the PSD matrix dimension.

A product-averaging theorem then concentrates each branch near a suitable Fourier character. Multiplying by that character shifts its retained terms to low degree while preserving their squares. After controlling the discarded contribution, the purported small factorization would contradict the separating functional.

The conceptual chain is therefore: a small exact PSD representation would force a low-complexity positivity certificate; a parity obstruction rules out that certificate; and a matching construction transfers the obstruction to the desired matrix. This is a description of the manuscript’s route, not an independent verification of its estimates.

7. Scope, limitations, and open questions

The lower bound concerns exact factorizations over the reals and exact semidefinite lifts. It does not impose a finite-precision restriction, which strengthens that exact statement. At the same time, it does not automatically prohibit approximate matrices with small entrywise error or relaxations whose optimization values are only approximately correct.

The shift $\rho$ is fixed before $n$ tends to infinity. The allowed threshold depends on it, so the theorem should not be used without further analysis for a sequence $\rho_n$ approaching one rapidly. The explicit polynomial-size factorization at one explains why this quantifier matters.

The underlying graph for the stated family is the complete graph of even order. Restricted graph classes can have much simpler matching polytopes. The theorem does not say that every individual matching instance requires an exponential formulation.

Natural further questions concern which approximations evade the obstruction, how the transition near $\rho=1$ behaves quantitatively, and whether the averaging tools yield lower bounds for other polytopes. Specialized polynomial-time matching remains entirely compatible with the claim.

8. Sources and further reading

Edmonds provides the polyhedral starting point; Rothvoß gives the unrestricted linear lower bound; Gouveia–Parrilo–Thomas explain the factorization correspondence. The linked symmetric-SDP and approximate-slack papers clarify the two principal distinctions in the new claim. The source manuscript below states the shifted-matrix theorem and its exact-lift consequence.

Source manuscripts

• M1. OpenAI, Exponential PSD rank of positively shifted matching matrices (October 5, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.