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 be a nonnegative integer and let be the vertex set. An edge of the complete graph on is a pair of distinct vertices with , as in (1). (1)✦
The perfect matching condition for an edge set is the condition that exactly one edge of is incident with each vertex of , as in (2). (2)✦
The family of perfect matchings of the complete graph on consists of the edge sets satisfying , as specified in (3). (3)✦
An odd-cut index is a vertex subset of odd cardinality; these indices form the family in (4). (4)✦
The row set is the disjoint union of the edge indices and odd-cut indices in (5). (5)✦
An edge crosses a vertex subset when exactly one endpoint lies in ; the cut consists of these edges, according to (6). (6)✦
The crossing count of a perfect matching across is the number of its edges in , given by (7). (7)✦
The unshifted matching slack matrix is the matrix whose entries are defined in (8), where is the indicator of membership of in . (8)✦
For , let be the cone of real symmetric positive semidefinite (PSD) matrices of order . A real PSD trace factorization of of order consists of families and in satisfying the trace identities in (9); write for the existence of such a factorization. (9)✦
The real PSD rank of is the least positive integer for which admits a real PSD trace factorization of order , as in (10). (10)✦
In the paper, the result reads: for even and , the matrix has columns indexed by perfect matchings of the complete graph on and rows indexed by odd vertex subsets , with entries ; additionally has one row for each edge , with entry when and otherwise; and real PSD rank is the least integer admitting an exact trace factorization by real symmetric PSD matrices of order , with no equivariance or rank restrictions.
What Is Checked
The rank in (10) is defined for every nonnegative integer using the row and matching sets in (5) and (3) and the real trace factorizations in (9).