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?



Common lower bounds for positive semidefinite matrices
We have $n+1$ [linear matrix inequalities](https://en.wikipedia.org/wiki/Linear_matrix_inequality) (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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Sylvester%27s_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.




---


* Cynthia Vinzant, [What is a... Spectrahedron?](http://dx.doi.org/10.1090/noti1116), Notices of the AMS, Vol. 61, No. 5, May 2014.


