Matching Matrices Have Exponential PSD Rank Below the Unit Shift

The matching matrix has one row for each odd vertex set U and one column for each perfect matching M. Its entry is the number of matching edges crossing the cut defined by U, minus one, plus a shift rho:

A_n(rho)_(U,M) = |M ∩ delta(U)| - 1 + rho.

For every fixed rho strictly between zero and one, the manuscript proves that the real positive semidefinite rank of this matrix is at least 2^(cn) for sufficiently large even n. The constant c is positive and independent of rho, though the threshold for n may depend on rho. Every entry is at least rho, so the shifted matrix has no zero entries. ^†

The parity behind the unshifted entries is simple. A perfect matching pairs every vertex exactly once. For an odd set U, each matching edge internal to U accounts for two vertices, while each edge crossing out of U accounts for one. If I is the number of internal matching edges and C the number of crossing edges, then |U| = 2I + C. Since |U| is odd, C is odd and therefore at least one. When C equals one, the unshifted entry is zero; adding rho makes it positive.

This is a lower bound on the size of an exact semidefinite description, not on the running time of an algorithm for finding a matching. Positive semidefinite rank is the smallest matrix order r for which each row and column can be assigned a real positive semidefinite matrix of order r, with the trace of each row–column product reproducing the corresponding entry. The factors may be arbitrary: the proof does not assume they are diagonal, symmetric under vertex permutations, or low precision.

The exponential lower bound applies to every fixed shift strictly below one, but rho = 1 admits a polynomial-size construction. Index diagonal coordinates by graph edges. For a row U, put a one on edges crossing its cut; for a column M, put a one on edges in the matching. The trace of the product counts crossing matching edges, exactly the matrix entry at this shift. The construction uses n choose 2 coordinates.

The endpoint changes the answer in kind: below one, the manuscript proves an exponential lower bound for exact PSD rank; at one, a diagonal representation of polynomial size exists. The conclusion concerns exact representation. Approximation is a separate question.

The proof recasts the odd-crossing condition as a parity problem. Take another graph and assign a bit to each endpoint of each edge. At every vertex, prescribe the parity of its incident bits, choosing prescriptions whose total is odd. Summing all incidence bits modulo two cancels equal endpoint bits on each edge. An edge contributes one precisely when its endpoint bits disagree. The number of disagreements is therefore odd, and at least one.

Subtract 1 - rho from that disagreement count to define f. Since there is at least one disagreement, f(y) is at least rho for every bit assignment y. Yet the proof constructs a signed linear functional D for which D(f) = -(1 - rho). This is not a contradiction: D is not an ordinary probability average and need not be nonnegative on every positive function. Its narrower useful property is that it is nonnegative on squares of functions of sufficiently low block degree.

The parity graph is embedded into the matching problem. Replace each parity-graph vertex by a cell of matching vertices, give each incident edge a terminal in that cell, and pair the remaining vertices internally. Match terminals across cells according to the parity graph. In the restricted cuts used by the proof, both ends of an internal pair receive the same cut bit, so internal pairs do not cross. A terminal edge crosses exactly when the corresponding incidence bits disagree. The shifted matching entry therefore equals f(y) exactly. The small-cycle example illustrates the parity identity; the proof uses large expanding graphs, with fixed-size cells as the number of matching vertices grows.

Assume a small PSD factorization exists. Averaging its row factors over the restricted cuts still gives the required pairing with each matching factor. But averaging squares is not the same as squaring averages: (0² + 2²) / 2 = 2, while ((0 + 2) / 2)² = 1. The proof must preserve the exact sum-of-squares structure rather than replace it with a square of an averaged factor.

The technical argument combines averaging within large cells, an orthogonal-splitting inequality, and a product theorem that concentrates Fourier coefficients near a separate center for each branch. The local variance and splitting bounds do not depend on matrix dimension; the final Fourier estimate does track factor size. Together, these steps apply to arbitrary PSD factors.

A Boolean Fourier character takes values +1 and -1, so multiplying a matrix branch by a character leaves its Gram square unchanged. Character indices add modulo two. Translating frequencies near a branch’s center therefore turns them into low-block-degree terms, while the concentration estimate controls the discarded terms. The resulting function f* is a sum of squares of low-block-degree functions, so D(f*) is nonnegative.

The error between f and f* can be made smaller than 1 - rho, even after applying D. But D(f) is -(1 - rho), whereas D(f*) is nonnegative. That gap cannot be bridged, yielding the exponential lower bound on factor size.

Finally, an unshifted factorization gives one for the shifted matrix by appending a scalar coordinate: rho on each row factor and one on each column factor. Thus the unshifted PSD rank is at most one less than the shifted rank. The manuscript uses the standard slack-matrix correspondence to carry the lower bound over to exact semidefinite lifts of the perfect matching polytope.

The finite examples illustrate the mechanics, not the general theorem. The linked Lean scope records weaker superpolynomial statements rather than a formal reproduction of the exponential bound.