4
$\begingroup$

Suppose we are given positive semidefinite matrices $P_1, P_2, \dots, P_n \in \mathbb{C}^{m \times m}$.

  • How to characterize the set $S$ of their common lower bounds $$S = \{Q \mid 0 \leq Q\leq P_i, \forall i\}$$ where $A \leq B$ means $B-A$ is positive semidefinite?

  • The set is convex. How to describe all the extreme points?

$\endgroup$
1
$\begingroup$

We have $n+1$ linear matrix inequalities (LMIs) in $\mathrm X$, namely,

$$\mathrm X \succeq \mathrm O_m, \qquad \mathrm P_1 - \mathrm X \succeq \mathrm O_m, \qquad \mathrm P_2 - \mathrm X \succeq \mathrm O_m, \qquad \cdots \qquad \mathrm P_n - \mathrm X \succeq \mathrm O_m$$

The conjunction of these $n+1$ LMIs can be written as a single LMI

$$\begin{bmatrix} \mathrm X & & & & \\ & \mathrm P_1 - \mathrm X & & & \\ & & \mathrm P_2 - \mathrm X & & \\ & & & \ddots & \\ & & & & \mathrm P_n - \mathrm X\end{bmatrix} \succeq \mathrm O_{m (n+1)}$$

which defines a (convex) spectrahedron in $\mathbb R^{\binom{m+1}{2}}$. In the interior of this spectrahedron, the block matrix above is positive definite. At the boundary, the block matrix is merely positive semidefinite, i.e., its rank is lower at the boundary.

From Sylvester's criterion for positive semidefiniteness, saying that $\mathrm P_i - \mathrm X \succeq \mathrm O_m$ is equivalent to saying that all $2^m - 1$ principal minors of matrix $\mathrm P_i -\mathrm X$ are nonnegative. In other words, each LMI of the form $\mathrm P_i - \mathrm X \succeq \mathrm O_m$ encapsulates at most $2^m - 1$ polynomial inequalities in the $\binom{m+1}{2}$ entries of symmetric $\rm X$. Thus, in total, we have at most $(2^m - 1) (n+1)$ polynomial inequalities.


$\endgroup$

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.