1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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$). $\endgroup$ – Tobias Fritz Jul 19 '17 at 1:47
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Jul 19 '17 at 7:45
  • $\begingroup$ @Dima Pasechnik Thank you! I am particularly interested in the case that $m=4$. Is there a clear characterization of this case? $\endgroup$ – gondolf Jul 20 '17 at 0:16
  • $\begingroup$ @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. $\endgroup$ – Dima Pasechnik Jul 20 '17 at 12:07
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I am particular interested in the polynomial characterization of $S$ with $m=4$. Is there good way to understand it? $\endgroup$ – gondolf Jul 21 '17 at 0:07
  • $\begingroup$ I suppose that it's not really known. It will be instructive to start with the first non-trivial case, $m=2$. $\endgroup$ – Dima Pasechnik Jul 21 '17 at 15:15
  • $\begingroup$ That is usually called nemerical range for $m=2$. $\endgroup$ – gondolf Jul 22 '17 at 22:00
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Jul 23 '17 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.