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 be a nonnegative integer, and let be the labeled vertex set of the complete graph . An edge of is a pair of vertices with ; write for the edge set.✦ A perfect matching on is a finite subset of in which every vertex is incident with exactly one edge.✦ The set consists of the perfect matchings on . An odd cut is specified by a subset of odd cardinality.✦
For a vertex subset , an edge of crosses the cut precisely when one endpoint belongs to and the other does not; is the set of such edges. For a perfect matching on and a vertex subset , the crossing count is the number of edges of crossing .✦ The matching slack matrix has columns indexed by and rows indexed by the disjoint union of and the odd cuts, with entries (1). (1)✦
For a nonnegative integer , let denote the cone of real PSD matrices. A real PSD factorization of order of is a pair of families , indexed by and , satisfying (2). (2)✦
The Claim
Theorem 1 (Normalization of PSD factors). Let and be finite sets, with nonempty. Let for and , and let satisfy for every . There are families such that (3)✦
Let be even and positive, and suppose that has a real PSD factorization of order . There are families such that (4)✦
In the paper, the result reads: a finite nonzero nonnegative matrix with entries at most and a real PSD factorization of order has a real PSD factorization of an order whose row factors and column factors satisfy and .
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.