# On Polynomial Characterization of Projection area of semidefinite matrices

Suppose $m,n$ are positive integers.

$D$ denotes the set of $n\times n$ complex semidefinite positive matrices with unit trace.

$A_1,\cdots,A_m$ are $n\times n$ Hermitians.

We are interested in the projection of $D$ onto $A_1,\cdots,A_m$ in the following way,

$$S=\{(tr(A_1N),\cdots,tr(A_m N)):N\in D\}$$

It is clear $S$ is convex compact set. How to characterize its boundary. Can it be characterized by polynomial inequalities of $\mathbb{R}^m$. What is the minimal degree of those polynomials? Is $m$ enough? How many polynomials are needed?

In particular, for the case $m=4$, what do we know? Can we compute the boundary efficiently?

• As you may already know, your $S$ is the convex hull of the joint numerical range of the $A_i$'s. The paper arxiv.org/pdf/0812.1624 may help, which is essentially concerned with the case $m=2$ (take $A=A_1 + iA_2$). – Tobias Fritz Jul 19 '17 at 1:47
• It should be easy to prove that $S$ is a semi-algebraic set in $\mathbb{R}^m$ (notice that your map, defining $S$ as the image of $D$, is linear), and the boundary of semialgebraic set is semialgebraic: en.wikipedia.org/wiki/Semialgebraic_set How exactly it can be described is a much harder question. – Dima Pasechnik Jul 19 '17 at 7:45
• @Dima Pasechnik Thank you! I am particularly interested in the case that $m=4$. Is there a clear characterization of this case? – gondolf Jul 20 '17 at 0:16
• @gondolf I posted an answer describing the "dual" to $S$ set, for which indeed a lot is known---at least it is known whether the algebraic equation comes from. – Dima Pasechnik Jul 20 '17 at 12:07

One can construct a "dual" $S^*$ to $S$, for which a lot is known.

Indeed, this is related to "convex algebraic geometry", namely, an approach to describe convex semialgebraic sets as sets $S^*$ of solutions of the linear matrix inequality in $y:=(y_1,\dots, y_m)$: $$y_1A_1+\dots+y_mA_m\succeq A_0,\quad A_k=A_k^\top\in \mathbb{R}^{n\times n}, \tag{*}$$ where $T\succeq U$ means $T-U$ is positive semidefinite. There is a wealth of material on this, see e.g. Victor Vinnikov's survey. In loc.cit. you can find footnote on p.1, explaining that there is not much generality added by considering Hermitian $A_k$ rather than real symmetric $A_k$.

On (*) one can consider a semindefinite optimisation problem (SDP): $$\max b^\top y, \quad y \text{ satisfies (*)}, \quad b:=(b_1,\dots,b_m)\in\mathbb{R}^m.\tag{P}$$ It has a naturally defined dual: $$\min_{N\succeq 0}\ tr(A_0 N), \quad tr(A_kN)=b_k,\quad 1\leq k\leq m.\tag{D}$$ This is related to your set $S$ by setting $A_0=0$ and $A_1=I$. That is, a point $b$ is in $S$ if and only if (D) has a solution. The duality of (P) and (D) comes from the computation $$tr(A_0N)=tr((-T+\sum_k y_k A_k)N)=\sum_k y_k tr(A_k N)- tr(TN)=b^\top y-tr(TN), \quad T\succeq 0.$$ Save some pathological cases, at the optimum of (D) one has $TN=0$, and the optima of (D) and (P) are equal.

Building upon this, one can relate $S$ and $S^*$: for each $b\in S$ there exists unique $y\in S^*$ such that $b^\top y=0$.

A lot is understood about the boundary of $S^*$, see Theorem 2.1. Basically, it is a component in an algebraic set defined by $\det(-A_0+\sum_k y_kA_k)=0$. An interesting nontrivial example comes from determinantal representations of certain cubic curves, for which one has one compact convex component---this is the boundary of $S^*$, and one unbounded branch.

• Thanks! I am particular interested in the polynomial characterization of $S$ with $m=4$. Is there good way to understand it? – gondolf Jul 21 '17 at 0:07
• I suppose that it's not really known. It will be instructive to start with the first non-trivial case, $m=2$. – Dima Pasechnik Jul 21 '17 at 15:15
• That is usually called nemerical range for $m=2$. – gondolf Jul 22 '17 at 22:00
• Right, indeed, in arxiv.org/pdf/0812.1624.pdf the duality I outlined is developed for $m=2$. (My description is incomplete, as at some point one has to take the convex closure of the dual variety). I do not know how much of it can be carried over to the case $m>2$, but I presume at least the general setup can. – Dima Pasechnik Jul 23 '17 at 8:25