2 Spectral convex sets

Denote by $D : \mathrm {S}_2\mathbb {R}^d \to \mathbb {R}^d$ the projection onto the diagonal and by $\delta : \mathbb {R}^d \to \mathrm {S}_2\mathbb {R}^d$ the embedding into diagonal matrices. Many remarkable properties of spectral convex sets arise because the projection onto the diagonal, and the diagonal section, coincide.

Lemma 2.1. If K is a symmetric convex set, then

$$\begin{align*}D(\Lambda(K)) \ = \ K \ = \ D( \Lambda(K) \cap \delta(\mathbb{R}^d) ). \end{align*}$$

Before giving a proof, we introduce some notation and terminology. For a point $p \in \mathbb {R}^d$ , we write $s_k(p)$ for the sum of its k largest coordinates. Recall that a point $q \in \mathbb {R}^d$ is majorized by p, denoted $q \trianglelefteq p$ , if

(2.1) $$ \begin{align} \sum_{i=1}^d q_i \ = \ \sum_{i=1}^d p_i \qquad \text{ and } \qquad s_k(q) \ \le \ s_k(p) \quad \text{ for all } k=1,\dots,d-1. \end{align} $$

Majorization relates to permutahedra in that

$$\begin{align*}\Pi(p) \ = \ \{q\in \mathbb{R}^d\;:\; q \trianglelefteq p\}. \end{align*}$$

In other words, the majorization inequalities give an inequality description of the permutahedron [Reference Billera and Sarangarajan8].

Lemma 2.1 yields that spectral convex sets are, in fact, convex.

We identify the dual space $(\mathrm {S}_2\mathbb {R}^d)^*$ with $\mathrm {S}_2\mathbb {R}^d$ via the Frobenius inner product . The support function of a closed convex set K is defined by

Proposition 2.3, like many of the convex analytic facts in this section, can be deduced from results of Lewis on extended real-valued spectral functions [Reference Lewis20]. If $f:\mathbb {R}^d\rightarrow \mathbb {R} \cup \{+\infty \}$ is an extended real-valued symmetric function, then $f_{\mathcal {H}}(A) := f(\lambda (A))$ is the associated spectral function. The Fenchel conjugate of a function g is . Observe that the support function $h_{K}(\cdot )$ of a closed convex set is the Fenchel conjugate of the indicator function $\iota _K(\cdot )$ that takes value $0$ for points in K and value $+\infty $ for points not in K. For a symmetric function f, the fundamental relation $f_{\mathcal {H}}^* = (f^*)_{\mathcal {H}}$ holds [Reference Lewis20, Theorem 2.3]. Applying this to the indicator function of a symmetric closed convex set yields Proposition 2.3.

An exposed face of a convex set K is a subset of the form $\{p\in K\;:\; \langle {c,p} \rangle = h_{K}(c)\}$ for some c. Geometrically, a (proper) exposed face is a subset of K that arises as the intersection of K and a hyperplane that supports K. Exposed faces of $\Lambda (K)$ and K come in $O(d)$ - and $\mathfrak {S}_d$ -orbits, respectively. The collection of exposed faces up to symmetry is a partially ordered set with respect to inclusion that we denote by $\overline {\mathcal {F}}(\Lambda (K))$ and $\overline {\mathcal {F}}(K)$ , respectively. Proposition 2.3 allows us to deduce the following relationship between $\overline {\mathcal {F}}(\Lambda (K))$ and $\overline {\mathcal {F}}(K)$ .

The polar of a convex set $K \subset \mathbb {R}^d$ is defined as

It is easy to see that the polar of a symmetric convex set is symmetric. In combination with Proposition 2.3, we can deduce that the class of spectral convex sets is closed under polarity.

Furthermore, since polyhedra are also closed under polarity, it follows that the class of spectral polyhedra is closed under polarity.

Proposition 2.3 can also be used to show that spectral convex bodies interact nicely with Minkowski sums.

Proof. We compute

$$ \begin{align*} h_{\Lambda(K)+\Lambda(L)}(B) & \ = \ h_{\Lambda(K)}(B) + h_{\Lambda(L)}(B) \ = \ h_{K}(\lambda(B)) + h_{L}(\lambda(B))\\ & \ = \ h_{K+L}(\lambda(B)) \ = \ h_{\Lambda(K+L)}(B).\\[-37pt] \end{align*} $$

We can use this property to simplify the computation of basic convex-geometric invariants; cf. the book by Schneider [Reference Schneider26]. Let $B(\mathbb {R}^d)$ denote the Euclidean unit ball in $\mathbb {R}^d$ . The Steiner polynomial of a convex body $K \subset \mathbb {R}^d$ is

$$\begin{align*}\operatorname{\mathrm{vol}}(K + t B(\mathbb{R}^d)) \ = \ W_d(K) + d W_{d-1}(K) t + \cdots + \tbinom{d}{d} W_0(K) t^d. \end{align*}$$

The coefficients $W_i(K)$ are called quermaßintegrals. The following reduces the computation of Steiner polynomials of $\Lambda (K)$ to the computation of an integral over K.

Theorem 2.7. Let $K \subset \mathbb {R}^d$ be a symmetric convex body. Then

$$\begin{align*}\operatorname{\mathrm{vol}}(\Lambda(K) + t B(\mathrm{S}_2\mathbb{R}^d)) \ = \ 2^{\frac{1}{2}d(d+3)}\prod_{r=1}^d\frac{\pi^{\frac{r}{2}}}{\Gamma(\frac r 2)} \int_{K + t B_d} \prod_{i < j} |p_j - p_i| \, dp. \end{align*}$$

Proof. Recall from the introduction that the unit ball in $\mathrm {S}_2\mathbb {R}^d$ satisfies $B(\mathrm {S}_2\mathbb {R}^d) = \Lambda (B(\mathbb {R}^d))$ . In particular, using Corollary 2.6, we need to determine the volume of $\Lambda (K + t B(\mathbb {R}^d))$ .

Let $\varphi : O(d) \times \mathbb {R}^d \to \mathrm {S}_2\mathbb {R}^d$ with $\varphi (g,p) := g \delta (p) g^t$ . Then by Corollary 2.2, we need to compute $\int _{\varphi (O(d) \times K')} d\mu $ , where $K' := K + t B(\mathbb {R}^d)$ .

The differential at $(g,p) \in O(d) \times \mathbb {R}^d$ is the linear map $D_{g,p} : T_g O(d) \times T_p \mathbb {R}^d \to T_{\varphi (g,p)} \mathrm {S}_2\mathbb {R}^d$ with

$$\begin{align*}D_{g,p}\varphi (Bg, u) \ = \ [g\delta(p)g^t,B] + g D(u) g^t, \end{align*}$$

where [,] is the Lie bracket. Now, the linear spaces $T_g O(d) \times T_p \mathbb {R}^d$ and $T_{\varphi (g,p)} \mathrm {S}_2\mathbb {R}^d$ have the same dimension. If $g = (g_1,g_2,\dots ,g_d) \in O(d)$ , then we choose as a basis for the former $g_i \wedge g_j := g_i g_j^t - g_j g_i^t \in T_gO(d)$ for $1 \le i < j \le d$ and the standard basis $e_1,\dots ,e_d \in T_p\mathbb {R}^d = \mathbb {R}^d$ . For the latter, we choose $g_i \bullet g_j = \frac {1}{2}(g_ig_j^t + g_jg_i^t)$ for $1 \le i < j \le d$ and $g_i \bullet g_i $ for $i=1,\dots ,d$ . We then compute

$$\begin{align*}D_{g,p}(g_i \wedge g_j) \ = \ (p_j - p_i) \, g_i \bullet g_j \quad \text{and} \quad D_{g,p}(e_i) \ = \ g_i \bullet g_i . \end{align*}$$

Hence, under the identification $g_i \wedge g_j \mapsto g_i \bullet g_j$ and $e_i \mapsto g_i \bullet g_i$ , $D_{g,p}\varphi $ has eigenvalues $p_j - p_i$ for $i < j$ as well as $1$ with multiplicity d. This yields

$$\begin{align*}\int_{\varphi(O(d) \times K')} \, d\mu \ = \ \int_{O(d) \times K'} |\det D_{g,p}\varphi| \, dg dp \ = \ \int_{O(d)}dg \, \int_{K'} \prod_{i < j} |p_j - p_i| \, dp . \end{align*}$$

Together with Hurwitz formula for the volume of $O(d)$ , this yields the claim.

The algebraic boundary $\partial _{\mathrm {alg}} K$ of a full-dimensional closed convex set $K \subset \mathbb {R}^d$ is, up to scaling, the unique polynomial $f_K \in \mathbb {R}[x_1,\dots ,x_d]$ of minimal degree that vanishes on all points $q \in \partial K$ ; see [Reference Sinn27] for more information. Throughout, we assume K is semialgebraic. If K is symmetric, then $f_K$ is a symmetric polynomial – that is, $f_K(x_{\sigma ^{-1}(1)},\dots ,x_{\sigma ^{-1}(d)}) = f_K(x_1,\dots ,x_d)$ for all $\sigma \in \mathfrak {S}_d$ . By the fundamental theorem of symmetric polynomials, there is a polynomial $F_K(y_1,\dots ,y_d) \in \mathbb {R}[y_1,\dots ,y_d]$ such that $f_K(x_1,\dots ,x_d) = F_K(e_1,\dots ,e_d)$ , where $e_i$ is the i-th elementary symmetric polynomial.

For $A \in \mathrm {S}_2\mathbb {R}^d$ , let $\det (A + tI) = t^d + \eta _1(A) t^{d-1} + \cdots + \eta _d(A)$ be its characteristic polynomial. The coefficients $\eta _i(A)$ are polynomials in the entries of A, and it is easy to see that $\eta _i(g A g^t) = \eta _i(A)$ . In fact, every polynomial h such that $h(gAg^t) = h(A)$ for all $g \in O(d)$ and $A \in \mathrm {S}_2\mathbb {R}^d$ can be written as a polynomial in $\eta _1,\dots ,\eta _d$ ; see [Reference Goodman and Wallach14, Ch. 12.5.3].

3 Spectrahedra

In this section, we show that spectral polyhedra are spectrahedra. For $P = \Pi (p)$ a permutahedron and $\mathcal {SH}(p) = \Lambda (P)$ , a Schur-Horn orbitope, this was shown in [Reference Sanyal, Sottile and Sturmfels23]. We briefly recall the construction, which will then be suitably generalized.

A point $q \in \mathbb {R}^d$ is contained in $\Pi (p)$ if and only if $q \trianglelefteq p$ . This condition can be rewritten in terms of linear inequalities. For $I \subseteq [d]$ , we write $q(I) = \sum _{i \in I} q_i$ . Recall that for a point $p \in \mathbb {R}^d$ , we write $s_k(p)$ for the sum of its k largest coordinates. Then $q \trianglelefteq p$ if and only if

$$\begin{align*}s_d(p) \ = \ q([d]) \quad \text{ and } \quad s_{|I|}(p) \ \ge \ q(I) \quad \text{ for all } \varnothing \neq I \subsetneq [d]. \end{align*}$$

If p is generic – that is, $p_i \neq p_j$ for $i \neq j$ – then it is easy to show that the system of $2^d - 2$ linear inequalities is irredundant.

For $1 \le k \le d$ , the k -th linearized Schur functor $\mathcal {L}_k$ is a linear map from $\mathrm {S}_2\mathbb {R}^d$ to $\mathrm {S}_2\bigwedge ^k \mathbb {R}^d$ such that the eigenvalues of $\mathcal {L}_k(A)$ are precisely $\lambda (A)(I) = \sum _{i \in I} \lambda (A)_i$ for $I \subseteq [d]$ and $|I| = k$ . Therefore, $\mathcal {SH}(p)$ is precisely the set of points $A \in \mathrm {S}_2\mathbb {R}^d$ such that

(3.1) $$ \begin{align} s_d(p) \ = \ \mathop{tr}(A) \quad \text{ and } \quad s_k(p) \, I_{\binom{d}{k}} \ \succeq \ \mathcal{L}_k(A) \quad \text{ for all } 1 \le k < d . \end{align} $$

The simplest symmetric polyhedron has the form

$$\begin{align*}P_{a,b} \ = \ \{x\in \mathbb{R}^d : \langle { \sigma a, x} \rangle \le b \text{ for } \sigma \in \mathfrak{S}_d\}, \end{align*}$$

where $a\in \mathbb {R}^d$ and $b\in \mathbb {R}$ . In general, a symmetric polyhedron has the form

$$\begin{align*}P \ = \ \{ x \in \mathbb{R}^d : \langle { \sigma a_i, x } \rangle \le b_i \text{ for } \sigma \in \mathfrak{S}_d \text{ and } i = 1,\dots,M \} \ = \ \bigcap_{i=1}^M P_{a_i,b_i} . \end{align*}$$

Since $\Lambda (K \cap L) \ = \ \Lambda (K) \cap \Lambda (L)$ , it suffices to focus on the case $P_{a,b}$ .

To extend the representation (3.1) directly, for each general $a\in \mathbb {R}^d$ , we would need a linear map $\mathcal {L}_a$ from $\mathrm {S}_2\mathbb {R}^d$ to $\mathrm {S}_2 V$ with $\dim V = d!$ such that the eigenvalues of $\mathcal {L}_a(A)$ are precisely $\langle {\sigma a, \lambda (A)} \rangle $ for all $\sigma \in \mathfrak {S}_d$ . For $a = (1,\dots ,1,0,\dots ,0)$ with k ones, this is realized by the linearized Schur functors.

Proposition 3.1. For $d = 2$ , set

$$\begin{align*}\mathcal{L}_a(A) \ := \ a_1 A + a_2 \mathop{adj}(A) \, , \end{align*}$$

where $\mathop {adj}(A)$ is the adjugate (or cofactor) matrix. Then $A \mapsto \mathcal {L}_a(A)$ is a linear map satisfying the above requirements.

The construction above only works for $d=2$ , and we have not been able to construct such a map for $d \ge 3$ .

We pursue a different approach toward a spectrahedral representation by considering a redundant set of linear inequalities for $P_{a,b}$ . An ordered collection $\mathcal {I} = (I_1,\dots ,I_d)$ of subsets $I_j \subseteq [d]$ is called a numerical chain if $|I_j| = j$ for all j. A numerical chain is a chain if additionally $I_1 \subset I_2 \subset \cdots \subset I_d$ . Chains are in bijection to permutations $\sigma \in \mathfrak {S}_d$ via $I_j = \{ \sigma (1),\dots ,\sigma (j) \}$ . For $I \subseteq [d]$ , we write $\mathbf {1}_I \in \{0,1\}^d$ for its characteristic vector.

Let us assume that $a = (a_1 \ge a_2 \ge \cdots \ge a_d)$ , and set $a_{d+1} := 0$ . For a numerical chain $\mathcal {I}$ , we define

(3.2) $$ \begin{align} a^{\mathcal{I}} \ := \ (a_1 - a_2)\mathbf{1}_{I_1} + (a_2 - a_3)\mathbf{1}_{I_2} + \cdots + (a_{d-1} - a_d)\mathbf{1}_{I_{d-1}} + a_d \mathbf{1}_{I_d} . \end{align} $$

Proposition 3.2. Let $a = (a_1 \ge a_2 \ge \cdots \ge a_d)$ and $b\in \mathbb {R}$ . Then

$$\begin{align*}P_{a,b}\ = \ \{ x \in \mathbb{R}^d : \langle {a^{\mathcal{I}},x} \rangle \le b \text{ for all numerical chains } \mathcal{I} \} . \end{align*}$$

Proof. Let Q denote the right-hand side. To see that $Q \subseteq P_{a,b}$ , we note that if $\mathcal {I}$ is a chain corresponding to a permutation $\sigma $ , then $a^{\mathcal {I}} = \sigma a$ .

For the reverse inclusion, it suffices to show that $a^{\mathcal {I}} \trianglelefteq a$ , which implies that $\langle {a^{\mathcal {I}},x} \rangle \le b$ is a valid inequality for $P_{a,b}$ . Using the fact that $s_k(p+q) \le s_k(p) + s_k(q)$ , we compute

$$\begin{align*}s_k(a^{\mathcal{I}}) \le \sum_{j=1}^d (a_j - a_{j+1}) s_k(\mathbf{1}_{I_j}) = \sum_{j=1}^{k-1} j (a_j - a_{j+1}) + k \sum_{j=k}^d (a_j - a_{j+1}) = a_1 + \cdots + a_k = s_k(a). \end{align*}$$

Similarly, $s_d(a^{\mathcal {I}}) = a_1 + \cdots + a_d$ , which completes the proof.

Recall that for matrices $A \in \mathrm {S}_2\mathbb {R}^d$ and $B \in \mathrm {S}_2\mathbb {R}^e$ , the tensor product $A \otimes B$ is a symmetric matrix of order $de$ with eigenvalues $\lambda _i(A) \cdot \lambda _j(B)$ for $i=1,\dots ,d$ and $j=1,\dots ,e$ . For $a = (a_1 \ge \cdots \ge a_d)$ , let

$$\begin{align*}\widehat{\mathcal{L}}_a : \textstyle{\bigwedge^1\mathbb{R}^d} \otimes \bigwedge^2\mathbb{R}^d \otimes \cdots \otimes \bigwedge^d\mathbb{R}^d \ \to \ \bigwedge^1\mathbb{R}^d \otimes \bigwedge^2\mathbb{R}^d \otimes \cdots \otimes \bigwedge^d\mathbb{R}^d \end{align*}$$

be the linear map given by

Theorem 3.3. Let $P = P_{a_1,b_1} \cap \cdots \cap P_{a_M,b_M}$ be a symmetric polyhedron. Then $A \in \Lambda (P)$ if and only if

$$\begin{align*}b_i\, I \succeq \widehat{\mathcal{L}}_{a_i}(A)\,\text{ for }\, i=1,2,\ldots,M.\end{align*}$$

Proof. Since $\Lambda (P) = \bigcap _{i=1}^{M}\Lambda (P_{a_i,b_i})$ , it is enough to show that $A\in \Lambda (P_{a,b})$ if and only if $bI \succeq \widehat {\mathcal {L}}_{a}(A)$ .

Let $a = (a_{1} \ge a_{2} \ge \cdots \ge a_{d})$ and $A \in \mathrm {S}_2\mathbb {R}^d$ with $v_1,\dots ,v_d$ an orthonormal basis of eigenvectors. For $I = \{i_1 < i_2 < \cdots < i_k \}$ a subset of $[d]$ , we write $v_I := v_{i_1} \wedge v_{i_2} \wedge \cdots \wedge v_{i_k} \in \bigwedge ^k \mathbb {R}^d$ . Then a basis of eigenvectors for $\widehat {\mathcal {L}}_a(A)$ is given by

$$\begin{align*}v_{\mathcal{I}} \ := \ v_{I_1} \otimes v_{I_2} \otimes \cdots \otimes v_{I_d} \, , \end{align*}$$

where $\mathcal {I}$ ranges of all numerical chains. The eigenvalue of $\widehat {\mathcal {L}}_a(A)$ corresponding to $v_{\mathcal {I}}$ is precisely $\langle {a^{\mathcal {I}},\lambda (A)} \rangle $ . Hence, A satisfies the given linear matrix inequalities for a if and only if $\sum _i \lambda _i(A) = \sum _i a_i$ and $\langle {a^{\mathcal {I}},\lambda (A)} \rangle \le b$ for all $\mathcal {I}$ . By Proposition 3.2, this is the case if and only if $\lambda (A) \in P_{a,b}$ or, equivalently, $A \in \Lambda (P_{a,b})$ .

The spectrahedral representation given in Theorem 3.3 for $\Lambda (P)$ , where P is a symmetric polyhedron in $\mathbb {R}^d$ with M orbits of facets, is of size

$$\begin{align*}M \cdot \prod_{i=1}^d \binom{d}{i}. \end{align*}$$

So the spectrahedral representation is of order $M 2^{d^2}$ ; see [Reference Lagarias and Mehta19].

If

$$\begin{align*}K \ = \ \{x\in \mathbb{R}^d : A_0 + x_1 A_1 + \cdots + x_d A_d \succeq 0\} \end{align*}$$

is a spectrahedral representation of a convex set K with $A_0,\dots ,A_d \in \mathrm {S}_2 \mathbb {R}^m$ and $A_0$ positive definite, then $h(x) = \det (A_0 + x_1 A_1 + \cdots + x_d A_d)$ vanishes on $\partial K$ . Hence, the size of a spectrahedral representation is bounded from below by the degree of $\partial _{\mathrm {alg}} K$ . If P is a symmetric polytope with M full orbits of facets, then its algebraic boundary has degree $M\cdot d{!}$ . From the discussion following Proposition 2.8, we can deduce that the degree of $\partial _{\mathrm {alg}} \Lambda (P)$ is also $M\cdot d{!}$ , and so that any spectrahedral representation of $\Lambda (P)$ has size at least $M\cdot d{!}$ . While interesting from an algebraic point of view, spectrahedral representations of symmetric polytopes are clearly impractical for computational use. In the next section, we discuss substantially smaller representations as projections of spectrahedra.

4 Spectrahedral shadows

In this section, we give a representation of $\Lambda (K)$ as a spectrahedral shadow (i.e., a linear projection of a spectrahedron) when K is, itself, a symmetric spectrahedral shadow, by a direct application of results from [Reference Ben-Tal and Nemirovski4]. The aim of this section is to illustrate the significant reductions in size possible by using projected spectrahedral representations.

It is convenient to use slightly different notation in this section, to emphasize that we do not need to construct an explicit representation of the symmetric convex set K, to get a representation of $\Lambda (K)$ . To this end, let $\mathbb {R}^d_{\downarrow } = \{p\in \mathbb {R}^d\;:\; p_1 \geq p_2 \geq \cdots \geq p_d\}$ . For $L\subseteq \mathbb {R}^d_{\downarrow }$ , define

$$\begin{align*}\Pi(L) = \operatorname{\mathrm{conv}}\,\left(\mathfrak{S}_d \cdot L\right),\end{align*}$$

the convex hull of the orbit of L under $\mathfrak {S}_d$ . This is the inclusion-wise minimal symmetric convex set containing L. We recover the usual permutahedron of a point $p\in \mathbb {R}^d_{\downarrow }$ by $\Pi (p)$ .

In Theorem 4.2, we give a representation of $\Lambda (\Pi (L))$ as a spectrahedral shadow whenever $L\subseteq \mathbb {R}_{\downarrow }^d$ is a spectrahedral shadow. We use the following result of Ben-Tal and Nemirovski [Reference Ben-Tal and Nemirovski4, Section 4.2, 18c].

Lemma 4.1. Let $1 < k < d$ and $t \in \mathbb {R}$ . Then a matrix $A \in \mathrm {S}_2\mathbb {R}^d$ satisfies $s_k(\lambda (A)) \le t$ if and only if there are $Z \in \mathrm {S}_2\mathbb {R}^d$ and $s \in \mathbb {R}$ such that

$$\begin{align*}Z \ \succeq \ 0, \quad Z - A + s I_d \ \succeq \ 0, \quad \text{ and } \quad t - ks - \mathop{tr}(Z) \ \ge \ 0 . \end{align*}$$

For the case $k = 1$ , we obtain the simpler representation $s_1(\lambda (A)) = \max \lambda (A) \le t$ if and only if $t I - A \succeq 0$ .

Theorem 4.2. If $L\subseteq \mathbb {R}^d_{\downarrow }$ is convex, then

(4.1) $$ \begin{align} \Lambda(\Pi(L)) = \{A\in \mathrm{S}_2\mathbb{R}^d\;:\; \exists p\in L\;\text{such that}\;\lambda(A) \trianglelefteq p\}. \end{align} $$

If $L\subseteq \mathbb {R}^d_{\downarrow }$ is the projection of a spectrahedron of size r, then $\Lambda (\Pi (L))$ is the projection of a spectrahedron of size $r + 2 d^2 - 2d - 2$ .

We now specialize to the case of $\Lambda (P)$ where P is a symmetric polyhedron with the origin in its interior.

Proof. We will argue that $\Lambda ({P}^\circ ) = {\Lambda (P)}^\circ $ is the projection of a spectrahedron of size $M+2d^2-2d-2$ and then appeal to the fact that if C has a projected spectrahedral representation, then ${C}^\circ $ has a representation as a projection of a spectrahedron of the same size [Reference Gouveia, Parrilo and Thomas15, Proposition 1]. By our assumptions on P, we have that ${({\Lambda (P)}^\circ )}^\circ = \Lambda (P)$ .

Since the origin is in the interior of P, we know that ${P}^\circ $ is a symmetric polytope with M orbits of vertices. Each orbit of vertices meets $\mathbb {R}^d_{\downarrow }$ , and thus, $\Lambda (P) = \Lambda (\Pi (\{v_1,\ldots ,v_M\}))$ for some $v_1,\ldots , v_M\in \mathbb {R}^d_{\downarrow }$ . Let $L = \operatorname {\mathrm {conv}}\,\{v_1,\ldots ,v_M\}\subseteq \mathbb {R}^d_{\downarrow }$ , and note that

$$\begin{align*}L = \{ \mu_1v_1 + \cdots + \mu_M v_M\;:\; \mu_1,\dots,\mu_M \ge 0,\;\mu_1 + \cdots + \mu_M= 1\} \end{align*}$$

gives a representation of L as the projection of a polyhedron with M facets, and so a representation as the projection of a spectrahedron of size M. Finally, since $\Pi (L) = \Pi (\{v_1,\ldots ,v_M\})$ , it follows from Theorem 4.2 applied to $\Lambda (\Pi (L))$ that ${\Lambda (P)}^\circ = \Lambda ({P}^\circ )$ is the projection of a spectrahedron of size $M+2d^2-2d-2$ .

5 Remarks, questions and future directions

Hyperbolicity cones and the generalized Lax conjecture

A multivariate polynomial $f \in \mathbb {R}[x_1,\dots , x_d]$ , homogeneous of degree m, is hyperbolic with respect to $e\in \mathbb {R}^d$ if $f(e) \neq 0$ and for each $x\in \mathbb {R}^d$ , the univariate polynomial $t\mapsto f_x(t) := f(x-te)$ has only real roots. Associated with $(f,e)$ is a closed convex cone $C_{f,e} \subseteq \mathbb {R}^d$ , defined as the set of points $x \in \mathbb {R}^d$ for which all roots of $f_x$ are nonnegative. A major question in convex algebraic geometry, known as the generalized (set-theoretic) Lax conjecture (see [Reference Vinnikov29]), asks whether every hyperbolicity cone is a spectrahedron.

If $C = \{x\in \mathbb {R}^d: \langle {\sigma a_i,x} \rangle \geq 0,\;\mathrm {for\ all}\; \sigma \in \mathfrak {S}_d\; \text{and}\; i=1,2,\ldots , M\}$ is a symmetric polyhedral cone containing $e=(1,1,\ldots ,1)$ in its interior, then it is the hyperbolicity cone associated with the degree $M\cdot d{!}$ symmetric polynomial

$$\begin{align*}f(x) = \prod_{i=1}^{M}\prod_{\sigma\in \mathfrak{S}_d}\langle {\sigma a_i,x} \rangle. \end{align*}$$

The spectral polyhedral cone $\Lambda (C)$ is the hyperbolicity cone associated with the polynomial $F(X) = f(\lambda (X))$ and $e = I \in \mathrm {S}_2\mathbb {R}^d$ . This follows from Proposition 2.8 and is a special case of an observation of Bauschke, Güler, Lewis and Sendov [Reference Bauschke, Güler, Lewis and Sendov2, Theorem 3.1]. One can view Theorem 3.3 as providing further evidence for the generalized Lax conjecture since it shows that every member of this family of hyperbolicity cones is, in fact, a spectrahedron.

Given a symmetric hyperbolic polynomial f, one natural way to produce a new symmetric hyperbolic polynomial, and an associated symmetric hyperbolicity cone, is to take the directional derivative $D_ef$ in the direction $e=(1,1,\ldots ,1)$ , an example of a Renegar derivative. This operation commutes with passing to the associated spectral objects. Indeed, taking the Renegar derivative $D_ef$ and then constructing the spectral convex cone $\Lambda (C_{D_ef,e})$ gives the same result as constructing the spectral hyperbolic polynomial $F(X) = f(\lambda (X))$ and then taking the hyperbolicity cone of $D_IF$ , the Renegar derivative in the direction $I\in \mathrm {S}_2\mathbb {R}^d$ . For example, the hyperbolicity cones associated with the elementary symmetric polynomials are symmetric convex cones that arise by repeatedly taking Renegar derivatives starting with $f(x) = x_1 x_2 \cdots x_d$ in the direction $e=(1,1,\ldots ,1)$ . Brändén [Reference Brändén10] established that these cones are all spectrahedral; see also [Reference Sanyal22, Reference Saunderson and Parrilo24]. Building on this result, Kummer [Reference Kummer18] has shown that the associated spectral hyperbolicity cones are also spectrahedral.

Categories and Adjointness

For a group G acting on a real vector space V, let us write $\mathcal {K}(V)^G$ for the class of G-invariant convex bodies $K \subset V$ . We can interpret the construction of spectral bodies as a map

$$\begin{align*}\Lambda : \mathcal{K}^{\mathfrak{S}_d}(\mathbb{R}^d) \ \to \ \mathcal{K}^{O(d)}(\mathrm{S}_2\mathbb{R}^d) . \end{align*}$$

It follows from Lemma 2.1 that the map that takes $A \in \mathrm {S}_2\mathbb {R}^d$ to $\{ \sigma \lambda (A) : \sigma \in \mathfrak {S}_d \}$ extends to a map

(5.1) $$ \begin{align} \lambda : \mathcal{K}^{O(d)}(\mathrm{S}_2\mathbb{R}^d) \ \to \ \mathcal{K}^{\mathfrak{S}_d}(\mathbb{R}^d) \end{align} $$

such that $\lambda \circ \Lambda $ and $\Lambda \circ \lambda $ are the identity maps. It would be very interesting to see if this can be phrased in categorical terms that would explain the reminiscence of adjointness of functors in Proposition 2.3.

Spectral zonotopes

For $z \in \mathbb {R}^d$ , we denote the segment with endpoints $-z$ and z by $[-z,z]$ . A zonotope is a polytope of the form

(5.2) $$\begin{align}Z \ = \ [-z_1, z_1] + [-z_2, z_2] + \cdots + [-z_m, z_m] \, , \end{align}$$

where $z_1,\dots ,z_m \in \mathbb {R}^d$ and addition is Minkowski sum. Zonotopes are important in convex geometry as well as in combinatorics; see, for example, [Reference Beck and Sanyal3, Reference Bolker9, Reference De Concini and Procesi12]. For $z \in \mathbb {R}^d$ , we obtain a symmetric zonotope

$$ \begin{align*} Z(z) \ := \ \sum_{\sigma \in \mathfrak{S}_d} \sigma [-z,z] \end{align*} $$

and for $z = e_1 - e_2 = (1,-1,0,\dots ,0)$ , the resulting symmetric zonotope is $2 (d-2)! \Pi (d-1, d-3,\dots ,-(d-3),-(d-1))$ and thus homothetic to the standard permutahedron $\Pi (1,2,\dots ,d)$ . For $z = e_1$ , we obtain a dilate of the unit cube $[0,1]^d$ .

We define spectral zonotopes as convex bodies of the form

$$\begin{align*}\Lambda(Z(z_1)) + \cdots + \Lambda(Z(z_m)) \, , \end{align*}$$

where $Z(z_i)$ are symmetric zonotopes. This class of convex bodies includes the Schur-Horn orbitope $\mathcal {SH}((d-1,d-3,\dots ,-(d-1)))$ as well as symmetric matrices with spectral norm at most one. It follows from Corollary 2.6 that spectral zonotopes are spectral convex bodies, and, in particular, spectral zonotopes form a sub-semigroup (with respect to Minkowski sum) among spectral convex bodies. It would be very interesting to explore the combinatorial, geometric and algebraic properties of spectral zonotopes.

There are a number of remarkable characterizations of zonotopes; cf. [Reference Bolker9]. In particular, zonotopes have a simple characterization in terms of their support functions: The support function of a zonotope Z as in (5.2) is given by $ h_{Z}(c) = \sum _{i=1}^m |\langle {z_i,c} \rangle |$ . We obtain the following characterization for spectral zonotopes.

Corollary 5.1. A convex body $\Omega \subset \mathrm {S}_2\mathbb {R}^d$ is a spectral zonotope if and only if its support function is of the form

$$\begin{align*}h_{\Omega}(B) \ = \ \sum_{i=1}^m \sum_{\sigma \in \mathfrak{S}_d} |\langle {\sigma z_i, \lambda(B)} \rangle| \, , \end{align*}$$

for some $z_1,\dots , z_m \in \mathbb {R}^d$ .

The support function for $Z(e_1-e_2)$ is

$$\begin{align*}h_{Z(e_1-e_2)}(c) \ = \ 2(d-2)! \sum_{i < j} |c_i - c_j| . \end{align*}$$

From Proposition 2.3, we infer that the support function of the (standard) Schur-Horn orbitope is

(5.3) $$ \begin{align} h_{\mathcal{SH}(d-1,\dots,-(d-1))}(B) \ = \ \sum_{i < j} |\lambda(B)_i - \lambda(B)_j | \ = \ \|\mathcal{M}_B\|_* . \end{align} $$

Here, $\|\cdot \|_*$ is the nuclear norm – that is, the sum of the singular values – and, for fixed $B\in \mathrm {S}_2\mathbb {R}^d$ , $\mathcal {M}_B$ is the linear map from $d\times d$ skew-symmetric matrices to traceless $d\times d$ symmetric matrices defined by $\mathcal {M}_B(X) = [B,X] = BX-XB$ , which has non-zero singular values $|\lambda (B)_i - \lambda (B)_j|$ for $1\leq i<j\leq d$ . The $m_1\times m_2$ nuclear norm ball has a spectrahedral representation of size $2^{\max \{m_1,m_2\}}$ [Reference Saunderson, Parrilo and Willsky25, Theorem 1.2], and a projected spectrahedral representation of size $m_1+m_2$ . These observations show that ${\mathcal {SH}(d-1,\dots ,-(d-1))}^\circ = \{B\;:\; \|\mathcal {M}_B\|_*\leq 1\}$ has a spectrahedral representation of size $2^{\binom {d+1}{2}-1}$ and a projected spectrahedral representation of size $d^2-1$ .

A convex body $K \subset \mathbb {R}^d$ is a (generalized) zonoid if it is the limit (in the Hausdorff metric) of zonotopes, or, equivalently, if its support function is of the form

(5.4) $$ \begin{align} h_{K}(c) \ = \ \int_{S^{d-1}} |\langle {c,u} \rangle| \, d\rho(u) \, , \end{align} $$

for some (signed) even measure $\rho $ ; see [Reference Schneider26, Ch. 3]. It was hoped that spectral zonotopes are zonoids, but this is not the case. Leif Nauendorf [Reference Naundorf21] showed that the Schur-Horn orbitopes $\mathcal {SH}(d-1,\dots ,-(d-1))$ are never zonoids for $d \ge 3$ .

A convex body $K\subset \mathbb {R}^d$ is a symmetric zonoid if and only if the measure $\rho $ in (5.4) is symmetric. We define spectral zonoids as those convex bodies with support functions of the form

$$\begin{align*}h_{\Omega}(B) \ = \ \int_{S^{d-1}}|\langle {\lambda(B),u} \rangle|\, d\rho(u)\, ,\end{align*}$$

where $\rho $ is a symmetric even measure. Examples of spectral zonoids include the Schatten p-norm balls in $\mathrm {S}_2\mathbb {R}^d$ when $p\geq 2$ . Further examples of spectral zonoids can be found in [Reference Aubrun and Lancien1, Section 5.1] (in the Hermitian setting) and [Reference Bürgisser and Lerario11, Section 5] (in the setting where the singular values of general matrices play the role of eigenvalues of symmetric matrices).