{'fraction_non_alphanumeric': 0.05091134650252887, 'fraction_numerical': 0.011387855075229825, 'mean_word_length': 4.024774234795812, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 43, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dimension reduction for semidefinite programs via Jordan algebras

We propose a new method for simplifying semidefinite programs (SDP) inspired by symmetry reduction. Specifically, we show if an orthogonal projection map satisfies certain invariance conditions, restricting to its range yields an equivalent primal-dual pair over a lower-dimensional symmetric cone---namely, the cone-of-squares of a Jordan subalgebra of symmetric matrices. We present a simple algorithm for minimizing the rank of this projection and hence the dimension of this subalgebra. We also show that minimizing rank optimizes the direct-sum decomposition of the algebra into simple ideals, yielding an optimal"block-diagonalization"of the SDP. Finally, we give combinatorial versions of our algorithm that execute at reduced computational cost and illustrate effectiveness of an implementation on examples. Through the theory of Jordan algebras, the proposed method easily extends to linear and second-order-cone programming and, more generally, symmetric cone optimization.


Introduction
Many problems in engineering can be posed as semidefinite programs (SDPs)-convex optimization problems over the cone of positive semidefinite (psd) matrices. While SDPs are efficiently-solvable in theory, solving many SDPs of practical interest is computationally-infeasible unless problem specific structure is exploited. Methods for exploiting structure include facial reduction and symmetry reduction, which both find a low-dimensional subset of psd matrices provably containing solutions. Specifically, facial reduction finds a proper face of the psd cone containing the solution set [7] by exploiting a failure of Slater's condition, where this face is isomorphic to a psd cone of lower order [3]. On the other hand, symmetry reduction finds a subspace intersecting the solution set by exploiting problem symmetry, where the intersection of this subspace with the psd cone is isomorphic to a product of simpler cones [20,45,9]. In this paper, we present a generalization of symmetry reduction (and related *-algebra-methods [9], [39]) with some of the appealing properties of facial reduction. In analogy with the minimal face of facial reduction, an optimal reduction within our framework is well-defined. Like facial reduction, a simple algorithm finds this optimal reduction for any SDP instance. Finally, like facial reduction, our method extends to any cone optimization problem and has an implementable solution algorithm for the special case of symmetric cones.
To explain our reduction method, we first recall the essential idea in symmetry reduction: finding an orthogonal projection map whose range intersects the solution set. This projection map, the so-called the Reynolds operator of a group action-satisfies certain invariance conditions that imply its range contains solutions. Though the Reynolds operator has a group-theoretic interpretation, the satisfied conditions are purely geometric and can be imposed on arbitrary maps. This leads to a simple statement of our method: minimize rank-or, equivalently, the dimension of the range-over the set of orthogonal projections satisfying these conditions.
As we show, there is a unique projection of minimum rank and it can be found efficiently. Moreover, the range of the rank minimizing projection is a Jordan subalgebra of symmetric matrices and hence has a canonical direct-sum decomposition. Precisely, it is isomorphic to a direct-sum of simple Jordan algebras and its intersection with the psd cone-the cone-of-squares of the subalgebrais isomorphic to a product of symmetric cones [27] [16]. Hence, by reformulating an SDP over the range of this projection, we not only reduce the dimension of the feasible set but replace the semidefinite constraint with a collection of simpler conic constraints. Finally, our algorithm for finding this projection extends 'word-by-word' to any symmetric cone optimization problem (e.g., linear programs and second-order-cone programs), mirroring similar extensions of interior-point methods [2].
We now summarize key contributions of this paper, making comparisons with related work in the literature. Theoretical and practical limitations of the method are also given as caveats.

Contributions and caveats
Our proposed method restricts an SDP instance to the range of an orthogonal projection satisfying certain invariance conditions. We call the range of such a projection an admissible subspace and the range of the minimum rank projection the optimal admissible subspace. In presenting this method, we make the following contributions.
• A generalization of symmetry reduction and *-algebra methods. Both symmetry reduction and *-algebra-methods find admissible subspaces but not necessarily optimal admissible subspaces. These subspaces also satisfy non-essential restrictions: they equal the range of a Reynolds operator or they equal the symmetric part of a *-algebra. Hence, we generalize these methods by removing these restrictions and introducing a notion of optimality.
• A fully algorithmic methodology. The optimal admissible subspace is found efficiently (in polynomial time) for arbitrary SDP instances using a simple algorithm. In contrast, symmetry reduction methods are tailored to particular family of SDPs and may, for instance, find the automorphism group of a related graph as a first step. While the (symmetric part) of the *-algebra generated by the SDP data matrices is an admissible subspace-and is found in a fully algorithmic way-generating this subspace requires working over the vector space R n×n (instead of S n ). It can also be much bigger than the optimal admissible subspace, as examples of Section 6 will illustrate.
• Extensions to linear, second-order cone, and symmetric cone optimization. Interiorpoint algorithms from linear programming can be translated word-by-word to symmetric cone optimization [2]. That is, each step can be expressed using operations well-defined for any formally-real Jordan algebra. The same is true of the presented algorithm for finding the optimal admissible subspace; indeed, versions of this algorithm are easily stated for linear and second-order cone programming.
• Subspaces with optimal decompositions. All admissible subspaces have a canonical direct-sum decomposition into minimal ideals. We prove the optimal admissible subspaceobtained by minimizing dimension-also has an optimal decomposition. Specifically, the ranks (in the Jordan algebra sense) of its minimal ideals are majorized by the ranks of any other admissible subspace. Roughly speaking, this direct-sum decomposition is a 'blockdiagonalization' of the subspace, where each direct-summand is a block with rank equal to its size. Our majorization result therefore implies the size of the largest block is minimized as is the sum of the block sizes.
• Trade-offs of dimension and sparsity. We present three refined versions of our method that optimize over subspaces with additional sparsity constraints. Each version requires the subspace to have a particular type of 0/1 orthogonal basis. A basis of the first type is the set of 0/1 characteristic matrices of a partition. A basis of the second type spans a coordinate subspace of S n -that is, it spans a subspace specified only by a sparsity pattern. (Indeed, the sparsity pattern of any admissible subspace will always be block-diagonal upto permutation.) A basis of the third type is a simply any set of 0/1 matrices that are pairwise orthogonal. Note this first type closely relates to coherent configurations [8], the second type was the topic of our conference paper [37], and the third type simultaneously generalizes the first two.
There are of course practical and theoretical limitations to the proposed method: • Formulation of the original SDP. Finding the optimal admissible subspace with the proposed algorithm requires the original SDP data matrices. Hence, to find this subspace for extremely large SDPs (where construction of these matrices is infeasible), one needs to use an analytic approach tailored to the specific SDP family-finding perhaps a 'closed-form' expression for the subspace. Though we do not pursue such an approach here, we note similar analytic descriptions are frequently available for related methods. For instance, there is a family of SDPs that bound the size of certain k-bit codes whose data matrices are of order 2 k . For these SDPs, equivalent LPs in order k variables have analytic descriptions [39] (see also [9]).
• Projection onto linear subspaces. The proposed algorithm requires the orthogonal projection map onto the linear subspace L defining the SDP feasible set. For SDPs with a single For many examples, this projection is easily obtained-at least in our experience. Indeed, it is easily constructed for many SDPs arising in sum-of-squares optimization, where {A i } m i=1 is a sparse orthogonal basis for its span (see, e.g., Lemma 1 of [4]). Nevertheless, finding this projection map may be impractical for SDPs of interest.
• Lack of affine invariance. The optimal admissible subspace is not affine invariant. Consider the following SDPs, where the data matrices of the second SDP are a congruence transformation of those of the first: If S 1 and S 2 are the optimal subspaces of the first and second SDP, respectively, affine invariance implies S 1 = {T T XT : X ∈ S 2 }. This relationship does not in general hold. Note symmetry reduction is not affine invariant either, and finding a practical affine invariant generalization is something we view as an important open problem.
• A proper subset of possible simplifications. While our method can convert an SDP to a simpler conic problem, it doesn't necessarily succeed when such a conversion is possible. For instance, if each matrix in {C, A 1 , . . . , A m } (as defined in the previous paragraph) is diagonal, our method will convert the SDP into a linear program. If they are only diagonal after congruence transformation by T ∈ R n×n , conversion to an LP is still possible; nevertheless, our method may fail unless T is special (e.g., orthogonal) or b is non-generic.

Outline
This paper is organized as follows. An optimization problem over orthogonal projections is introduced in Section 2 and its solution described in Section 3. Section 4 adds combinatorial constraints that ensure the range of the solution has a sparse basis with low storage complexity. Methods for representing the cone-of-squares are surveyed in Section 5, including its decomposition into primitive symmetric cones; we also show minimizing dimension minimizes a complexity measure of this decomposition. Finally, Section 6 gives examples and computational results.

Acknowledgments
We thank Etienne de Klerk for several useful conversations. Part of this work was completed while the first author was hosted at Tilburg University in February 2016.

Equivalent SDPs
To simplify notation, we consider a primal-dual pair of semidefinite programs (SDPs) expressed in conic form (Chapter 4, [33]): Here, X ∈ S n and S ∈ S n are decision variables in the vector space S n of real symmetric matrices equipped with trace inner-product X · Y := Tr XY , matrices C ∈ S n and Y ∈ S n are fixed, S n + ⊆ S n denotes the convex cone of positive semidefinite matrices, L ⊆ S n is a linear subspace with orthogonal complement L ⊥ ⊆ S n , and Y + L and C + L ⊥ are affine sets.
Since an inner-product is fixed, we'll view the sets of primal and dual optimal solutions as subsets of the same vector space S n . Our goal is find a subspace S ⊆ S n that intersects both these sets. A sufficient condition for intersection follows and is expressed in terms of the orthogonal projection P S : S n → S n onto S, the unique self-adjoint and idempotent linear map with range equal to S: Condition 2.1 (Constraint Set Invariance). For the primal-dual SDP pair (1), an orthogonal projection P S : S n → S n leaves the constraint sets invariant if (a) P S (S n + ) ⊆ S n + , i.e., P S is a positive map;

Remark 1. Note in symmetry reduction, the Reynolds operator satisfies constraints (a-b) and
(typically) P S (C) = C. It turns out these constraints imply (a-c); that is, the constraints of Condition 2.1 are weaker.
Condition 2.1 implies P S : S n → S n maps primal/dual feasible points to primal/dual feasible points; hence, its clear S intersects the primal and dual feasible sets. It turns out optimal solutions are also mapped to optimal solutions. To see this, first consider a primal feasible point X and the cost matrix C. The sub-conditions (b) and (c) state both X and P S (X) are in Y + L and both C and P S (C) are in C + L ⊥ ; hence, (b) and (c) imply that is, they imply the S ⊥ -components of X and C are contained in orthogonal subspaces. It follows C · X = P S (C) · P S (X) and, using the fact P S is self-adjoint and idempotent, that P S (C) · P S (X) = C · P S P S (X) = C · P S (X).
Hence, P S maps a primal feasible point X to a primal feasible point with equal cost. By similar arguments, P S also maps a dual feasible point S to a dual feasible point P S (S) with equal cost. Hence, optimal solutions are mapped to optimal solutions for both primal and dual problems. We conclude S intersects the sets of primal and dual optimal solutions, as desired. Evidently one can restrict the primal and the dual problems to S when Condition 2.1 holds without changing their optimal values. That is, one can replace the psd cone S n + with S n + ∩ S and the affine sets Y + L and C + L ⊥ with where the equations (2) is a primal-dual pair, i.e.,
Note variants of this proposition of various strength have appeared; see, e.g., Proposition 2 of [13] or Theorem 2 of [9]. We point out the most significant difference: the assumptions made elsewhere are not primal-dual symmetric like Condition 2.1; for instance, this symmetry is broken in [13] by assuming P S (C) = C.
The subspace S will have more useful structure if we impose the additional constraint of unitality: Condition 2.2 (Unitality). An orthogonal projection P S : S n → S n is unital if its range S contains a matrix E ∈ S satisfying where I r is the identity matrix of order r < n.
As we'll see in the next section, unitality and positivity (Condition 2.1-a) both hold iff S is a Jordan subalgebra of S n when S n is equipped with standard product (X, Y ) → 1 2 (XY + Y X). Hence, unitality and positivity imply S n + ∩ S-the so-called cone-of-squares of the subalgebra-is isomorphic to a symmetric cone. As we review in Section 5, this in turn implies existence of a linear map Φ and self-dual cone K := K 1 × · · · × K N for which Φ(K) = S n + ∩ S, where each K i is a Lorentz cone or a cone of Hermitian psd matrices with real, complex, or quaternion entries. This allows explicit reformulation of the SDP (1) over K as the following proposition illustrates: Proposition 2.2. Suppose P S : S n → S n satisfies the condition of Constraint Set Invariance (Condition 2.1). Let V be an inner-product space and Φ : V → S n an injective linear map with adjoint Φ * : S n → V. Finally, suppose the range of Φ equals S and that Φ(K) = S n + ∩ S for a self-dual cone K ⊆ V. Then, ifX andŜ solve the primal-dual pair Φ(X) and Φ(Φ * Φ) −1 (Ŝ) solve the pair (3)-and hence the pair (1).

Remark 3. Note analogues of Propositions 2.1-2.2 hold if
S n + is replaced with any self-dual cone. We conclude by illustrating the primal-dual pair (1), its restriction (3), and the existence of Φ and K with the following example. Example 2.1. Consider the following primal-dual pair of semidefinite programs: For the subspace S spanned by the set , Condition 2.1 holds for P S : S 4 → S 4 . Hence, primal and dual optimal solutions are obtained by solving the following restrictions to S: Moreover, Condition 2.2 also holds, implying S 4 + ∩ S is isomorphic to a product of symmetric cones; indeed, there exists a linear map Φ for which Φ(S 2 + × S 1 + ) = S 4 + ∩ S.

The optimal admissible subspace
We now state our reduction method: given an instance of the SDP (1), find a minimum rank projection P S satisfying the conditions of Constraint Set Invariance and Unitality. As we'll show, there is actually a unique minimum rank projection and it can be found efficiently. Uniqueness of this projection, and an algorithm for finding it, will be immediate from a characterization of admissible subspaces: Proof. This is an immediate consequence of Theorems 3.3-3.4 of the next subsections.
Note the set of admissible subspaces is closed under intersection. Hence, there is a unique admissible subspace of minimum dimension: Definition 3.2. The optimal admissible subspace S opt is the admissible subspace of minimum dimension, i.e., it is the unique solution of the following optimization problem: The subspace S opt also has the following useful properties: As we'll see in Section 5.2, this corollary implies S opt is not only optimal with respect to dimension but also with respect to complexity parameters of a canonical direct-sum decomposition.

Solution algorithm
Note an algorithm for finding S opt is immediate from Theorem 3.1. First, initialize S to the subspace spanned by C L and Y L ⊥ . Next, iteratively grow the subspace S by adding P L (S) and the span of {X 2 : X ∈ S}, terminating when the resulting ascending chain of subspaces stabilizes. Formally: Theorem 3.2. The optimal admissible subspace S opt is the output of the following algorithm: Stabilization clearly implies S is admissible. Further, each subspace in the chain is contained in S opt by a simple induction argument; hence, at stabilization the subspace is optimal. Finally, stabilization occurs in finitely-many steps, i.e., the algorithm terminates, since the dimension of the subspace increases monotonically. (Indeed, at most dim S n iterations are executed.) Lattice interpretation As mentioned, the set of admissible subspaces is closed under intersection. The whole space S n is also admissible. Hence, the set of admissible subspaces equals the set of fixed points of a closure operator-an idempotent, extensive, and increasing operator into the subspace lattice of S n . Indeed, one can interpret the Theorem 3.2 algorithm as evaluation of this closure operator at the subspace spanned by C L and Y L ⊥ .

Jordan algebra interpretation and extensions
Note we can modify the Theorem 3.2 algorithm to re-execute the step 'S ← S + span{X 2 : X ∈ S}' multiple times without changing the final output of the algorithm. If we repeatedly re-execute until S contains {X 2 : X ∈ S}, the subspace S has an algebraic interpretation. Specifically, it is closed under the Jordan product and is hence a Jordan subalgebra of S n , viewing S n as an algebra with this product. This leads to an alternative algorithm for finding S opt : This algorithm extends word-by-word in the sense of [2] if the original SDP of interest (1) is replaced with another symmetric cone optimization problem. Specifically, one simply replaces S n with the appropriate Jordan algebra. For instance, if (1) is a second-order-cone program (SOCP), one replaces S n with a spin-factor algebra; the output of the resulting algorithm is then a subspace containing optimal solutions of the SOCP.

Combinatorial extensions
In practice, one may want S to have additional structure-for instance, a sparse basis. In Section 4, we give alternative methods that impose this structure. Specifically, we give alternative definitions of S opt each constraining S opt to have a sparse basis with different combinatorial descriptions. As we'll see, the Theorem 3.2 algorithm is easily modified to accommodate these new constraints.

Characterization of invariance conditions
For the interested reader, we state and prove Theorem 3.3 and Theorem 3.4, which were just used to show Theorem 3.1. Together, they characterize projections satisfying Constraint Set Invariance and Unitality (Conditions 2.1-2.2) in terms of their ranges. Theorem 3.3 characterizes positive and unital projections-i.e., projections satisfying both Conditions 2.1-(a) and Condition 2.2. Theorem 3.4 characterizes projections leaving invariant an affine subspace and hence projections satisfying Condition 2.1-(b) and Condition 2.1-(c).

Positive projections and invariance under squaring
Recall Condition 2.1-(a) requires positivity of P S : S n → S n and Condition 2.2 requires unitality. It turns out these conditions hold iff the range S is invariant under squaring, i.e., iff S contains {X 2 : X ∈ S}. Analogues of this statement-using the language of Jordan algebras-are wellknown. See [42] [43] for results in the complex setting and also the thesis [24]. Positivity of projections onto Jordan subalgebras is also shown in [32].
If S is invariant under squaring, positivity and unitality of P S : S n → S n follow from the basic properties of symmetric matrices. The converse direction is shown in part by translating an argument of [42] from the complex to real case. Since they are relatively-short and self-contained, we now give these arguments. We'll use the following lemma relating invariance under squaring to eigenvalue decompositions.
For a subspace S ⊆ S n , the following are equivalent.
1. S contains the set E X for all non-zero X ∈ S.

S is invariant under squaring, i.e., S ⊇ {X
Proof. That statement one implies two is immediate given that X 2 = E∈E X λ 2 E E. Conversely, suppose X has non-zero eigenvalue λ of maximum magnitude. Then, if statement two holds, the idempotentÊ = lim n→∞ (|λ| −1 X) 2n is contained in S and has range equal to an eigenspace or, if ±|λ| are both eigenvalues, the sum of two eigenspaces. Replacing X with X − λÊ and iterating yields a set of idempotents whose span contains E X ; moreover, this set is contained in S.
Note if we had assumed S contained I, the non-trivial direction of this lemma reduces to the fact the subspace spanned by {I, X, X 2 , . . . , X q } for sufficiently large q contains a set of idempotents whose ranges equal the eigenspaces of X (including the kernel); see, e.g., Section 11.4.1 of [1] for a proof using properties of Vandermonde matrices. We now use this lemma and the mentioned argument of [42] to show the following: Proof. To prove (2 ⇒ 1), consider X 0 and suppose P S (X) is non-zero. For a non-zero eigenvalue λ E of P S (X), let E ∈ S n denote the idempotent with range equal to the associated eigenspace. If (2) holds, then Lemma 3.1 implies P S (E) = E. Hence, We conclude the eigenvalues of P S (X) are non-negative, i.e., that P S (X) 0. To show the unitality condition, let Z be a matrix in S of maximum rank and let For all X ∈ S, it holds that tÊ X 2 for some t > 0. This shows the range ofÊ contains the range of X 2 and hence the range of X. It followsÊX = X.
To prove (1 ⇒ 2), we first apply the orthogonal matrix Q to S via QSQ T . That is, assuming the unit element of S has rank r, we pick the subspaceŜ ⊆ S r for which Letting Q r denote the first r columns of Q, it easily follows where PŜ : S r → S r is the orthogonal projection ontoŜ (with respect to the trace-inner product on S r ). Moreover, ifŜ is invariant under squaring, so is S, and if P S is positive, so is PŜ . Hence, statement 2 follows by showingŜ is invariant under squaring. We show this applying the argument from Theorem 2.2.2 of [42] and using the factŜ contains the identity matrix of order r. Dropping the subscriptŜ from PŜ , we first note since P is positive and P (I) = I, it satisfies the Kadison inequality, which states P (X 2 ) − P (X)P (X) 0 for all X ∈ S r (e.g., Theorem 2.3.4 of [5]). Hence, for X in the range of P P (X 2 ) − X 2 0.
Letting Z = P (X 2 ) − X 2 and taking the trace shows Since Z 0, we conclude Z = 0, i.e., that P (X 2 ) = X 2 . Therefore X 2 is in the range of P .
Note a theorem of Jordan, von Neumann, and Wigner [27] fully classifies subspaces invariant under squaring, as we review in Section 5.

Invariant affine subspaces of projections
Recall Condition 2.1-(b) and Condition 2.1-(c) require invariance of the affine sets Y + L and C + L ⊥ under the projection P S . We now characterize these conditions in terms of S. The first of two lemmas yielding this characterization follows: Lemma 3.2. For affine sets Y + L and C + L ⊥ , let Y L ⊥ ∈ S n and C L ∈ S n denote the projections of Y ∈ S n and C ∈ S n onto the subspaces L ⊥ and L, respectively. Let P S : S n → S n denote the orthogonal projection onto a subspace S of S n . Then, Proof. We show only the first statement, noting the second has identical proof. To begin, first note P S -being an orthogonal projection-is a contraction with respect to the Frobenius norm X F (recalling our use of the trace inner-product); further, Y L ⊥ is the unique minimizer of this norm We now characterize invariance of L and L ⊥ under P S . It turns out for an orthogonal projection P S (or more generally, a self-adjoint linear map), the conditions P S (L) ⊆ L and P S (L ⊥ ) ⊆ L ⊥ are equivalent. Indeed, for projections, even more is true: L is an invariant subspace of P S if and only if S is an invariant subspace of P L . We capture these remarks in the following lemma, which follows from, e.g., Proposition 3.8 of [17]. Lemma 3.3. Let P L : S n → S n and P S : S n → S n denote the orthogonal projections onto subspaces L and S of S n . The following four 1 statements are equivalent.
Combining one of these conditions with the previous lemma gives the desired conditions on S: Theorem 3.4. For affine sets Y + L and C + L ⊥ , let Y L ⊥ ∈ S n and C L ∈ S n denote the projections of Y ∈ S n and C ∈ S n onto the subspaces L ⊥ and L, respectively. The following are equivalent.
• Y + L and C + L ⊥ are invariant under the orthogonal projection P S : S n → S n , i.e., Condition 2.1-(b) and Condition 2.1-(c) hold.
• The subspace S contains C L and Y L ⊥ and is invariant under the orthogonal projection P L : S n → S n , i.e., S contains Y L ⊥ , C L and P L (S).
In summary, Y + L and C + L ⊥ are invariant under P S iff S is an invariant subspaces of P L and contains the distinguished points C L and Y L ⊥ . Note these points are precisely the minimum-Frobenius-norm points of the affine sets Y +L and C +L ⊥ due to our use of the trace inner-product.

Combinatorial variations
In the previous section, we called a subspace S admissible if the orthogonal projection P S : S n → S n satisfied the conditions of Constraint Set Invariance and Unitality (Conditions 2.1-2.2). We then characterized admissible subspaces and gave an algorithm for finding the optimal admissible subspace S opt -the unique admissible subspace of minimum dimension. In this section we address the following drawback: S opt may not have a sparse basis, hence finding it can be expensive, and restricting to it may destroy problem sparsity. To address this issue, we show how to optimize only over subsets of admissible subspaces with certain types of sparse bases. We then give alternative versions of our solution algorithm for minimizing dimension over these subsets. We present three versions based on three types of bases, each representable by a simple 'data structure.' The first is  ; and the third is represented by a partition of a relation. The three subspaces found by these algorithms-defined explicitly in the next subsections-are denoted S part , S coord , and S 0/1 . Figure 1 summarizes basic properties of these subspaces and their relationship with S opt , the optimal admissible subspace.
Images of subspaces as polynomial matrices We first introduce notation that enables concise statements of our solution algorithms, defining polynomial matrices that represent the sets P L (S) and {X 2 : X ∈ S}. We'll also show how to randomize these algorithms using point evaluations of these matrices. Given a basis B for S, we construct polynomial matrices as follows: where t B is a vector of scalar indeterminates indexed by B. Note the set of point evaluations of f X 2 (t B ; B) equals {X 2 : X ∈ S}, i.e., and similarly for f L (t B ; B) and P L (S). The following example illustrates this notation.
Expanding then shows To ease notation going forward, we will simply write f X 2 (B) to mean f X 2 (t B ; B), and similarly for f L (B). We note polynomial matrices (in non-commuting indeterminates) are similarly used in the partition refinement algorithm of [47]; we elaborate on this connection in the Appendix (Section 8.1).

Partition subspaces
We now find an optimal partition subspace-a subspace defined by a partition P of [n] × [n]. More precisely, a partition subspace equals the span of B P := {B P } P ∈P , where B P ∈ R n×n denotes the zero-one valued characteristic matrix of the subset P , i.e., for P ∈ P, we have (

Remark 4.
Partition subspaces are defined as subspaces of R n×n as opposed to S n to simplify notation and to enable comparison with special partitions (called coherent configurations) whose characteristic matrices aren't necessarily symmetric. See Section 8 for this comparison.
We define the optimal partition subspace as follows: Note partition subspaces are closed under intersection, where the partition of the intersection S 1 ∩S 2 is the coarsest partition refining the partitions of S 1 and S 2 ; hence, the feasible set of (6) is closed under intersection, implying uniqueness of solutions. Also note S ⊆ S n is a partition subspace iff its orthogonal projection P S : S n → S n satisfies P S (11 T ) = 11 T , P S (X) ≥ 0 when X ≥ 0, where 11 T is the all-ones-matrix and the inequality is elementwise. (One direction is obvious; the other is straightforward to show from properties of idempotent doubly-stochastic matrices; see, e.g., Theorem 1 of [40].) Hence, the optimal partition subspace equals the range of the minimum rank projection P S satisfying the conditions of Constraint Set Invariance and Unitality (Condition 2.1-2.2), and in, in addition, the constraints (7). Finally, while partition subspaces seem quite special, they arise naturally in symmetry reduction of semidefinite programs. In particular, the set of square matrices commuting with a group of permutation matrices is a partition subspace of R n×n defined by an orbit partition of [n] × [n]; see, e.g., [9].

Solution algorithm
To state an algorithm for finding S part , we first introduce new notation. For a matrix T ∈ S n , we let Part T denote the partition of [n] × [n] induced by the unique entries of T , i.e., (i, j) and (k, l) are in the same class of Part T if and only if T ij = T kl . We similarly define Part f (B P ) by its unique polynomial entries for f ∈ {f L , f X 2 }. We illustrate this notation below: Example 4.1 (continued). For B defined previously, the polynomial matrix f X 2 (B) is given by The partition Part f X 2 (B) has five classes induced by the unique polynomial entries of f X 2 (B). The characteristic matrices of these classes and the corresponding polynomials are: An algorithm for finding S part leverages the following simple observation: The span of B P contains T ∈ S n iff P refines Part T . Moreover, the span of B P is invariant under P L : S n → S n and the squaring map Lemma 4.1 suggests finding S part by iteratively refining a partition P using the polynomial matrices f X 2 (B P ) and f L (B P ). Such an algorithm takes the following form; its correctness follows from Lemma 4.1 and a simple induction argument: and P R denotes the coarsest partition of [n] × [n] that refines both P and R.
Randomization via sampling Note this algorithm need not explicitly construct symbolic representations of f L (B P ) and f X 2 (B P ); instead, one can evaluate these matrices at a generic point. Consider, for instance, a point evaluation of f X 2 (B P ) at t * ∈ R |B P | , i.e., consider Clearly, Part f X 2 (B P ) = Part f X 2 (B P ) |t=t * except for t * in a measure-zero subset of R |B P | . Indeed, this subset equals the union of solutions to finitely-many systems of polynomial equations. Similar remarks apply to f L (B P ). We see this point evaluation induces the same partition as f X 2 (B), i.e., the partitions Part f X 2 (B P ) and Part f X 2 (B) |t=t * B are the same.

Admissible partition subspaces
It turns out admissible partition subspaces connect with partitions arising in graph theory, namely, equitable partitions and coherent configurations. We study these connections in detail in the appendix (Section 8.1).

Coordinate subspaces
We now optimize over coordinate subspaces-subspaces defined only by a sparsity pattern. Mathematically, we define such a subspace by a symmetric relation R ⊆ [n] × [n] that identifies a subset of standard basis matrices {E ij } n i,j=1 of R n×n . The symmetrizations of these basis matrices then form a basis for the subspace. Precisely: . The optimal coordinate subspace S coord is the unique solution of Note uniqueness of S coord follows from the fact the feasible set of (8) is closed under intersection. Also note the orthogonal projection onto the span of B R is a Schur map-a map of the form X → M • X where • denotes the Schur (i.e., entry-wise) product and M ∈ S n is fixed. Indeed, M is just the characteristic matrix of the symmetric relation R. Since the images of Schur projections are conversely coordinate subspaces, S coord equals the range of the minimum rank Schur projection satisfying the conditions of Constraint Set Invariance and Unitality (Conditions 2.1-2.2).

Solution algorithm
We can find S coord using the same basic approach that finds the optimal partition subspace S part . Instead of iteratively refining a partition, we'll now iteratively grow a relation. To state an algorithm, we let Supp T denote the relation induced by non-zero entries of T ∈ S n , i.e., (i, j) ∈ Supp T iff T ij = 0; for f ∈ {f L , f X 2 }, we similarly define Supp f (B R ) by its non-zero polynomial entries.
The following example illustrates this notation: Based on Lemma 4.2, we modify our solution algorithm for finding S opt to iteratively grow a relation R using the polynomial matrices f X 2 (B R ) and f L (B R ). This modification takes the following form, and its correctness follows from Lemma 4.2 and a simple induction argument: Theorem 4.2. The optimal coordinate subspace S coord equals the span of B R , where R is the relation returned by: Randomization via sampling Note to find the support of the polynomial matrices f L (B R ) and f X 2 (B R ), one can evaluate each at generic t * ∈ R |B R | -as done in Section 4.1.1.

Combinatorial description of supports
In addition, these supports have combinatorial descriptions. Recalling B R := {E ij + E ji : (i, j) ∈ R}, it easily follows Hence, the support of f L (B R ) is determined by the sparsity of a matrix representation for P L . On the other hand, letting S ij = E ij + E ji , it holds that From this equation, it follows the support of f X 2 (B R ) contains (i, k) when R contains (i, j) and (j, k). Hence, if R contains the support of f X 2 (B R )-as it will at convergence-it is necessarily transitive.
Indeed, if R is symmetric and transitive, the coordinate subspace spanned by B R is blockdiagonal upto permutation. The corresponding sparsity pattern is defined by the partition of {i : (i, i) ∈ R} induced by R. Sparsity patterns of two such coordinate subspaces and the mentioned partitions are given below, where the (i, j) entry is marked * iff (i, j) ∈ R:

Admissible coordinate subspaces
Like admissible partition subspaces, admissible coordinate subspaces have connections with canonical combinatorial objects. We've just seen a connection with transitive relations. We elaborate on this connection and others in the appendix (Section 8.2).

Subspaces with 0/1 orthogonal bases
Finally, we consider a simultaneous generalization of the optimal partition subspace and optimal coordinate subspace: Clearly both coordinate subspaces and partition subspaces have such a basis; hence, S coord and S part both contain S 0/1 . One can show a subspace S equals S 0/1 if and only if 2 P S minimizes rank subject to Conditions 2.1-2.2 and the additional constraints given by (Recall P S satisfies the stronger constraint P S (11 T ) = 11 T when S is a partition subspace.) An algorithm for finding S 0/1 combines features of the algorithms presented in the previous two subsections. Specifically it maintains a relation R-capturing the indices (i, j) for which X ij is not identically zero for all X ∈ S-and, in combination, a partition P of R, whose characteristic matrices B P are the actual 0/1 basis. To state this algorithm, we let Part R T denote the partition of R ⊆ [n] × [n] induced by the unique entries of a matrix T with support contained in R. The algorithm follows: Add class R \ (∪ P ∈P P ) to P Replace P with refinement P Part R f (B P ) end until converged; As indicated, it alternates between growing the relation R, adding a single class R \ (∪ P ∈P P ) to P (such that it partitions R) and refining P.

Decomposing the cone-of-squares
Recall that S n , if equipped with product (X, Y ) → 1 2 (XY + Y X), is a formally real Jordan algebra. A subspace closed under this product is called a subalgebra. As also noted, since a subspace S is a subalgebra iff it is invariant under squaring, i.e., if S ⊇ {X 2 : X ∈ S}. Hence, any admissible subspace S is a subalgebra of S n . As a consequence, S n + ∩S-the so-called cone-of-squares of S-can be represented using powerful theorems from Jordan algebra theory.
In this section, we overview one such representation, decomposing S n + ∩ S into a product of cones. Here, each cone is isomorphic to the cone-of-squares of a simple algebra that in turn is isomorphic to a minimal ideal of S (viewing S as an algebra). That is, the decomposition of S n + ∩ S corresponds with a decomposition of S into minimal ideals. Note the decomposition of S is analogous to the Wedderburn decomposition of a semisimple associative algebra [46], which can be found using algorithms of [12] [29] [14]. Indeed, the basic mechanics of decomposing S are the same. After discussing the basics of this decomposition, we show S opt has an optimal decomposition with respect to a certain complexity measure.

Jordan algebras
Viewed as an algebra, any subalgebra S of S n is formally-real. Further, all formally-real Jordan algebras are isomorphic to a direct-sum of so-called simple algebras, which have been fully classified by a theorem of Jordan, von Neumann, and Wigner [27]. See also Chapter V of [16]. In particular, there exists a special linear map Φ-a Jordan isomorphism-and simple Jordan algebras J i for which where J i is a spin-factor algebra, or a full algebra of Hermitian matrices with real, complex, or quaternion entries of some fixed order. (The Albert algebra is excluded, since it, being exceptional, isn't isomorphic to any subalgebra of S n . See, e.g., Chapter 1, [25].) From (10), it follows the cone-of-squares S n + ∩ S has the decomposition S n + ∩ S = Φ(K 1 × · · · × K s ) where K i is the cone-of-squares of the simple algebra J i and hence equal to a Lorentz cone or the cone of Hermitian psd matrices (of some order) with real, complex, or quaternion entries.

Remark 5.
Note since K := K 1 × · · · × K s is self-dual and Φ injective, Proposition 2.2 tells us how to explicitly reformulate the primal-dual pair (1) over K when P S : S n → S n satisfies the condition of Constraint Set Invariance (Condition 2.1).
Given S, the question then is finding the isomorphism Φ and the simple algebras J i . We sketch the basic procedure here, pointing out it is extremely similar to [12] [29] [14]. (We will pursue a novel way of finding this decomposition in a followup paper that exploits the iterative nature of our solution algorithms. See Remark 6 in Section 5.3.) We first observe each minimal ideal S i of S is isomorphic to one of the simple algebras J i if viewed as an algebra (Theorem 11, [28]). Hence, a first step towards finding Φ and J i is to identify the minimal ideals of S (which form an orthogonal direct-sum decomposition of S.) The next step is to identify the isomorphism class of each ideal-i.e., the type of simple algebra isomorphic to each ideal. Finally, the last is to find the isomorphism-that is, to construct the linear map Φ. To reiterate, there are three key steps: 1. Find the orthogonal direct-sum decomposition of S into minimal ideals S i .

Identify the isomorphism class of each ideal.
3. Find isomorphism from simple algebra J i to each ideal S i .
Finding the direct-sum decomposition can be done by sampling a generic element X * from the center of S, viewed as an algebra; the set of minimal ideals is the set of orthogonal projections onto the eigenspaces of X * (Chapter 3, [28]). Letting for all A, B ∈ S. The isomorphism class is determined by the dimension of S i and the rank of S i (defined formally in the next section); that is, dimension and rank uniquely determine J i upto isomorphism. (See, e.g., page 97, [16].) Finally, isomorphisms between ideals and canonical matrix representations of simple algebras are studied in [26].

Structure of admissible subspaces
Recall if a subspace W is admissible, it contains S opt (Corollary 3.1). Further, W is a Jordan subalgebra of S n and hence decomposes into a direct-sum of minimal ideals. In this section, we show S opt has an optimal decomposition (Corollary 5.1). Specifically, we show if W is admissible, then the ranks of the minimal ideals of W majorize those of S opt , a consequence of the inclusion W ⊇ S opt . We begin formally defining rank. If J is a simple formally-real Jordan algebra with unit e, then the degree of x ∈ J , denoted deg(x), is the largest m for which {e, x, x 2 , . . . , x m } is a linearly independent set. The rank of J is the maximum of deg(x) over x ∈ J . If a subalgebra U of S n is isomorphic to a simple algebra J , we let rank U := rank J .
Note if U and J are isomorphic, the rank of J equals the number of distinct eigenvalues of a regular element of U (viewed as an algebra); see, e.g., Theorem III.1.2 and Chapter III of [16].
If a subalgebra S = ⊕ s i=1 S i is contained in another W = ⊕ w k=1 W k , it is natural to ask how the ranks of the minimal ideals S i relate to those of W i . It turns out some expected inequalities hold. For instance, the sums of the ranks satisfy and the maximum ranks satisfy More in fact is true: the ranks of W weakly majorize those of S: where x ↓ and y ↓ denote x and y with entries sorted in descending order.
Consider the following theorem, which we prove using a statement (Lemma 8.6) given in the appendix (Section 8).

Proof. First note S i contains a set
of non-zero matrices that are pairwise orthogonal and idempotent. Further, if i ∈ I k , then Φ k (E) = 0 for a non-zero idempotent matrix E in S i . We conclude all matrices in {Φ k (E) : E ∈ ∪ i∈I k E i } are non-zero (Lemma 8.6-3); moreover, they are idempotent (Lemma 8.6-1) and pairwise orthogonal (Lemma 8.6-2). It follows W k contains at least i∈I k rank S i non-zero matrices that are pairwise orthogonal and idempotent. Hence, rank W k ≥ i∈I k rank S i .
For the second statement, we note the first implies the following: for each l ∈ max{s, w}, there is a subset T ⊆ [w] with |T | ≤ min {l, w} for which Also of note are the subalgebras U 3 and U 4 ; despite having three non-zero blocks, U 3 is isomorphic to a product of two simple algebras since its second two-by-two block is a copy of the first-similar remarks apply to U 4 .
Optimality of the decomposition of S opt now follows as a corollary: Specifically, Corollary 3.1 implies W ⊇ S opt ; using this, Corollary 5.1 follows from Theorem 5.1.

Additional remarks
Remark 6 (Iteratively updating decompositions). In Section 3, we suggested the following alternative algorithm for finding S opt : To implement, one can iteratively update the isomorphism Φ and simple algebras J i for which S = Φ(J 1 × · · · × J s ). This can be more efficient than storing an arbitrary basis for S. We will pursue this in a follow-up paper.

Remark 7 (Representation via multiplication operators).
Another representation of S n + ∩ Sanalogous to the regular *-representation used in [11]-is in terms of multiplication operators. For fixed X ∈ S, the multiplication operator L(X) : S → S is the linear map satisfying The map L(X) : S → S is self-adjoint and has non-negative eigenvalues iff X ∈ S n + ∩ S (e.g., Lemma 12 of [38]). It follows S n + ∩ S is the pre-image of S dim S + under a particular linear map. Note the cone-of-squares of any formally-real Jordan algebra has such a representation, e.g., the algebra obtained by equipping R × R m with product (x, y) → L(x)y, where L(x) is the arrow matrix

Examples
We now find admissible subspaces for several example SDPs, exploring trade-offs in dimension, complexity of the cone constraint, and sparsity. To simplify presentation, we will use a common format for original instances and reduced instances. We now overview these formats and their complexity parameters.

Format of original SDPs
Each primal-dual pair is originally expressed in either SeDuMi [44] or SDPA [19] format and may have a mix of free and conic variables, where the cones are either orthants or cones of psd matrices. 3 From these formats, we eliminate free variables, reformatting the primal problem as where C, A i ∈ S n 1 × · · · × S nr are fixed, and ·, · denotes the inner-product obtained by equipping each product term S n i with the trace inner-product. Note once free variables are eliminated, reformatting amounts to relabeling linear inequalities as semidefinite constraints of order one. We will in some cases report the number of non-zero (nnz) entries in a description of (12); this equals the number of non-zero floating-point numbers needed to store C and {A i } m i=1 . We also report a tuple of ranks for (12), which is simply the tuple (n 1 , . . . , n r ).

Formats of reduced SDPs
Using techniques sketched in Section 5, we formulate reduced SDPs by finding a Jordan isomorphism Φ satisfying for simple Jordan algebras J i . Precisely, using Proposition 2.2, we construct where K i is the cone-of-squares of J i . We will in some cases report the number of non-zero (nnz) entries in a description of (13); this equals the number of non-zero floating-point numbers needed to store Φ * (C) and {Φ * (A i )} i∈T . We also report a tuple (r 1 , . . . , r q ) of ranks for (13). Here, each cone K i is the cone-of-squares of a simple algebra; the reported tuple consists of the ranks of these simple algebras.

Remark 8.
For most examples, K 1 × · · · × K q is a product of psd cones S r 1 + × · · · × S rq + and the tuple (r 1 , . . . , r q ) indicates their orders-in other words, all minimal ideals of S are isomorphic to algebras of real symmetric matrices. The only exception is discussed in Section 6.1.3. We also note S 2 is isomorphic to a spin-factor algebra-hence, S 2 + is isomorphic to a Lorentz cone.

Reference subspaces and inclusions
For convenience, we will let S f ull := S n 1 × · · · × S nr denote the full ambient space of the original instance (12). As discussed in [9], an SDP can be restricted to the *-algebra generated by its data matrices. To compare with this restriction, we let where C data is the *-algebra generated by the problem data C and {A i } m i=1 (using matrix multiplication as a product and transposition as the *-involution). Recall that As examples indicate, different inclusions can hold strictly for different examples. We also have As examples show, it often holds that S data = S f ull even when S opt is (much) smaller than S f ull .

Libraries of problem instances
The first set of SDPs are selected from three publicly-available sources: the parser SOSTOOLS [35], the DIMACS library [36] and a library of structured SDP instances from [10]. Table 6.1.1 reports the dimensions of the subspaces S opt , S 0/1 , S coord , S data and S f ull . Note the inclusions S opt ⊆ S 0/1 ⊆ S coord ⊆ S f ull hold as expected, and, as Table 6.1.1 indicates, different ones hold strictly for different instances. For a large fraction of instances, S f ull equals S data , implying generating a *-subalgebra from the problem data [9] does not provide reductions for these instances.

Remark 9.
We note the libraries [36,10] have additional instances on which our method was not effective (S opt = S f ull ); we do not report results for these instances. The library [10] also has other instances with group symmetry that were too large or too poorly conditioned for a simple MATLAB implementation of our algorithm. We omit these instances.

The Lovász number of Hamming graphs
We give special attention to the Table 6.1.2 instances denoted hamming_q_x and hamming_q_x_y, taken from [36]. The optimal values of these SDPs equal the Lovász number of a particular graph. For a graph G with vertices {1, . . . , n} and edge set E, the Lovász number is the optimal value of maximize Tr 11 T X subject to Tr X = 1 Tr where 11 T ∈ S n is the all-ones-matrix and E ij is a standard basis matrix of R n×n . The graphs for these instances are closely-related to Hamming graphs, which, for parameters q and d, have 2 q vertices labeled uniquely by q-bit Boolean vectors. For these graphs, vertices are adjacent iff their labels have Hamming distance at least d.   Here, s t× means s repeated t times, i.e., 3 2× := (3,3).
are Hamming graphs with certain edges removed; precisely, vertices are adjacent iff the Hamming distance of their labels equals x or equals x or y. When G is a Hamming graph, it is well known the SDP (14) can be converted into a linear program using the theory of association schemes [39]. Here, we find similar simplifications for the instances of [36]; precisely, S n + ∩ S opt is isomorphic to a non-negative orthant of order equal to the dimension of S opt , i.e., Note the other automated approach-generating a * -algebra from the cost matrix 11 T and constraint matrices I, {E ij + E ji } (i,j)∈E fails completely for these instances; that is, S data (the symmetric part of this * -algebra) equals S n .

Decompositions and majorization
In Given these strict inclusions, Theorem 5.1 implies the ranks of S 0/1 and S coord weakly majorize those of S opt in the sense of Definition 5.1. Similarly, it implies the ranks of S coord weakly majorize those of S 0/1 . This is confirmed in Table 6.1.2. The first row, for instance, reports the following tuples r 1 ∈ Z l 1 and r 2 ∈ Z l 2 for S opt and S 0/1 , respectively: ).
It easily follows r 2 weakly majorizes r 1 , i.e., for all positive integers q ∈ Z, This illustrates the major result of Section 5: S opt is not only optimal with respect to dimension but also its decomposition.

An algebra with a complex direct-summand
The example sosdemo5 is an SDP that bounds a quantity from robust control theory-the structured singular value µ(M, ∆) [34]: Here, M is a complex matrix and ∆ is a set of complex matrices. Though the parameters of µ(M, ∆) are complex, one can formulate an SDP with real data matrices to bound µ(M, ∆). This is done in sosdemo5 for particular M and ∆. Nevertheless, upon decomposing S opt into a direct-sum of minimal ideals, we find one of the direct-summands is isomorphic to an algebra of complex Hermitian matrices. Precisely, S opt = ⊕ 11 i=1 S i for minimal ideals S i . Letting r := (rank S 1 , . . . , rank S 11 ) and d := (dim S 1 , . . . , dim S 11 ), we have Orig.
Note with the exception of the entries marked * , the relation d i = r i +1 2 holds, showing S i is isomorphic to the algebra of real symmetric matrices of order r i . The exception satisfies d i = r 2 i , showing the corresponding ideal S i is isomorphic to the algebra of complex Hermitian matrices of order r i . We remark this is the only example considered where the direct-summands are not all isomorphic to S n for some n.

Coordinate subspaces and sparse decompositions
We next consider SDPs constructed by demonstration scripts packaged with the control system analysis tools available at http : //www.aem.umn.edu/˜AerospaceControl/, which build upon the parser SOSOPT [41]. For these SDPs, S opt equals the optimal coordinate subspace S coord . These SDPs illustrate we can always restrict to S coord without increasing the number of non-zero entries in the problem description. Though these examples are of small size, they illustrate S coord is a proper subspace of S f ull for surprisingly many examples arising in sumsof-squares optimization.

Comparison with LP method of Grohe, Kersting, Mladenov, and Selman
In [22], Grohe et al. describe a reduction method for linear programming (LP) and show it outperforms a symmetry reduction method of [6] on a collection of LPs; indeed, they show their method theoretically subsumes [6]. The linear programs used for comparison are relaxations of integer programs studied in [30]. By treating each linear inequality as a semidefinite constraint of order one, we applied our method to the same LP relaxations. Of the 57 relaxations, we find the same reductions on 56. For the remaining instance (cov1054sb), we significantly outperform [22]. For space reasons, Table 6.3.1 reports results for just a small subset of these LP relaxations. To match [22], we give the number of dual variables and inequality constraints. In terms of SDP (12) and the SDP (13), the number of dual variables and constraints equals the number of linear equations and the sum of the ranks, respectively. That the method of [22] and ours exhibits similar performance is not surprising. Indeed, the method of [22] is based on equitable partitions, which, as we discuss in the Appendix (Section 8.1), define invariant subspaces of linear maps. This and the empirical evidence of Table 6.3.1 suggest a projection satisfying the conditions of Constraint Set Invariance and Unitality (Condition 2.1-2.2) is explicitly constructed in the method of [22]; the instance cov1054sb shows this projection isn't always minimum rank.

Completely-positive rank, the subspace S 0/1 , and decomposition trade-offs
Our last example illustrates restrictions to S 0/1 , the optimal subspace with an orthogonal basis of 0/1 matrices. The considered SDP family yields lower-bounds of completely-positive rank, or cprank for short. The cp-rank of W ∈ S n + measures the size of the smallest non-negative factorization of W . Precisely, it is the smallest r for which V ∈ R n×r + exists satisfying W = V V T . Note cp-rank need not be finite-that is, a non-negative factorization of W need not exist for any r. As shown in [18], the cp-rank of W ∈ S n is lower bounded by the optimal value of the following SDP: Here, W ⊗ W denotes the Kronecker product and vect W denotes the n 2 × 1 vector obtained by stacking the columns of W . The double subscript ij indexes the n 2 rows (or columns) of X and the inequalities on (i, j) hold iff they hold element-wise (see [18] for further clarification on this notation).
In this example, we solve three instances of this SDP taking W equal to the matrices Z, Z ⊗ Z,

Alternative reformulation
For these examples, we compare (13) against the following alternative reformulation: where T ⊆ [m] indexes a maximal subset of linearly-independent equations. The dual of (16) is We can interpret this dual SDP as the dual of (12) restricted to the subspace S 0/1 , recalling by Proposition 2.1 that S 0/1 contains both primal and dual solutions. Table 6.4.1 shows solving (16) achieves computational savings and, indeed, can be preferred to solving (13). As indicated, for the largest instance, we cannot even find the Jordan isomorphism needed to construct (13) due to memory constraints. The formulation (16) also preserves sparsity.

Conclusion
We have proposed a new method for reducing the cost of solving semidefinite programs that restricts a given SDP to an optimal Jordan subalgebra. As illustrated with examples, this can significantly outperform the method of restricting to the *-algebra generated by the data matrices. We proposed practical variations of our method that restrict to subspaces with combinatorial bases-allowing one preserve sparsity and trade-off preprocessing effort with the size of the obtained reductions.   Table 6.4.1: The first row corresponds to the original SDP (12) and the others reformulations over S 0/1 . Here, t pre is time spent (in seconds) finding S 0/1 and constructing the reformulation. Solve time t solve is also in seconds.

Equitable partitions and invariant subspaces
To describe the invariant partition subspaces of P L , we first consider the analogous invariant subspaces of a symmetric matrix-recalling their connection with equitable partitions. To begin, an equitable partition of a symmetric matrix A ∈ S n is a partition of [n] that defines sub-matrices with constant row and column sums. For instance, the following partitions are equitable: which is in the span of the characteristic vectors of {1, 2} and {3, 4} and {5}. Equitable partitions-generalized to linear maps on S n -will characterize the invariant partition subspaces of the projection P L . To define these partitions, we first make the following observation: if a partition of [n] is an equitable partition of A ∈ S n , then for any characteristic vectors x, y ∈ {0, 1} n of the partition, y • (Ax) ∈ span y, where y • (Ax) denotes elementwise product. This suggests the following definition.
The following is then essentially immediate: Lemma 8.1. Let P be a partition of [n] × [n] with symmetric characteristic matrices B P ⊂ S n . Let S : S n → S n be a self-adjoint linear map. The following are equivalent: • The span of B P is an invariant subspace of S.
• P is a matrix equitable partition of S.
Proof. Suppose the first statement holds. Then, for all X ∈ B P , it holds that S(X) ∈ span B P . Hence, for all Y ∈ B P , it holds that Y • S(X) ∈ {0, Y } since matrices in B P have disjoint support. For the other direction, assume S(X) • Y ∈ span Y for all X, Y ∈ B P . Then, clearly, Since P partitions [n] × [n], the sum Y ∈B P Y equals the all-ones-matrix. Hence, S(X) ∈ span B P . The claim then follows by linearity of S.
Note equitable partitions-and matrix equitable partitions-form a lattice, reflecting the fact invariant subspaces of a linear map form a lattice. As a subset of the partition lattice, equitable partitions are also closed under join (Lemma 5.3 of [31]), reflecting the fact invariant subspaces are closed under intersection.

Jordan configurations, coherent configurations, and an open question of Cameron
We now discuss how partition subspaces invariant under squaring relate to so-called coherent configurations [8] and a refinement algorithm of [47]. To begin, recall a coherent configuration is a partition of [n] × [n] whose characteristic matrices span a subspace of R n×n , containing the identity matrix I, that is closed under matrix multiplication and transposition. Equivalently: Definition 8.2 (e.g., [8] • X T ∈ B P for all X ∈ B P ; • XY ∈ span B P for all X, Y ∈ B P ; • I ∈ span B P . Based on this, we define a Jordan configuration as a partition of [n] × [n] whose characteristic matrices span a subspace of S n closed under the squaring map X → X 2 , or, equivalently, the Jordan product (X, Y ) → 1 2 (XY + Y X):

Definition 8.3. A partition P of [n] × [n] is a Jordan configuration if its characteristic matrices B P satisfy
• X = X T for all X ∈ B P ; • XY + Y X ∈ span B P for all X, Y ∈ B P ; • I ∈ span B P .
Note a Jordan configuration P is a Jordan scheme, as defined in [8], if B P contains the identity matrix. Further, symmetrizing the characteristic matrices B C of a coherent configuration C yields a Jordan configuration; that is, B + B T : B ∈ B C is the set of characteristic matrices of a Jordan configuration.
It is an open question if all Jordan configurations are of this form. Cameron [8] posed an analogous question for Jordan schemes. Given a partition P with symmetric characteristic matrices, it is natural to ask what is the coarsest Jordan configuration refining P. An algorithm for this is easily stated: where we recall f X 2 (B P ) = ( B∈B P t B B) 2 -a polynomial matrix in the set {t B } B∈B P of commuting indeterminates. Note if non-commuting indeterminates are used instead (to determine the unique entries of f X 2 (B P )), this procedure is precisely the algorithm of [47] for finding the coarsest coherent configuration refining P.

Admissible coordinate subspaces
We now study coordinate subspaces (Section 4.2) invariant under squaring and the orthogonal projection P L : S n → S n in more detail, where we recall a coordinate subspace is the span of B R := {E ij + E ji : (i, j) ∈ R} for a symmetric relation R ⊆ [n] × [n]. Connections are made with symmetric, transitive relations and the connected components of a graph encoding the sparsity of P L , or, rather, the sparsity of a matrix representation for P L . • The relation R is transitive.
• The subspace S spanned by B R is invariant under squaring, i.e., S ⊇ {X 2 : X ∈ S}.
Proof. For all x, y ∈ C, T * T (x), y = T (x), T (y) ≥ 0 by self-duality of K. By self-duality of C, we conclude T * T (x) ∈ C. On the other hand, since T * is surjective, we have for any x ∈ C existence of w for which x = T * w. Further, for all y ∈ C, 0 ≤ T * w, y = w, T y which, since K = T (C), shows w ∈ K. Hence, w = T z for z ∈ C, showing x = T * T z.

Projections onto ideals
Finally, we state results used to prove Theorem 5.1. The first is a collection of technical results. The second describes projections onto minimal ideals. • If W = ⊕ w k=1 W k where W k is a minimal ideal of W, then the orthogonal projection map from W onto W k is a Jordan homomorphism.
Proof. Statement 1 and 2 follow from identity 2.20 of [23]. Statement 3 follows from Lemma 2.5.6, [23]. Lemma 8.6. Let W be a Jordan algebra of symmetric matrices with product (X, Y ) → 1 2 (XY + Y X). Let V ⊆ W be a subalgebra that is simple (viewed as an algebra). Let W = ⊕ w k=1 W k denote the orthogonal direct-sum decomposition of W into minimal ideals. Finally, let Φ k : W → W denote the orthogonal projection onto W k . The following statements hold for all k ∈ [w].
Proof. Since W k is a minimal ideal, the projection map Φ k from W onto W k is a Jordan homomorphism by Lemma 8.5; hence Φ k (E)Φ k (E) = Φ k (EE) = Φ k (E), showing the first statement.
For the second statement, recall W = ⊕ w k=1 W k is an orthogonal direct-sum decomposition of W. We conclude It follows if E · F = 0 then Φ i (E) · Φ j (F ) = 0 since each summand is positive semidefinite. For the third statement, view V as a simple algebra and let E = i E i and F = j F j denote the decompositions of E and F into primitive idempotents of V. Then, there exists T ∈ V such that E i = T F j T (Corollary IV.2.4, [16]). By Lemma 8.5, and Φ k (E i ) and Φ k (F j ) are idempotent (statement 1) and hence positive semidefinite, it follows Φ(F ) = 0 if Φ(E) = 0.