Prove or disprove that the set of $n \times n$ positive semidefinite matrices $PSD_n$ is a polyhedral set.

Question

The question is the following:

Prove or disprove that the set of $n \times n$ positive semidefinite matrices $PSD_n$ is a polyhedral set.

A set is called polyhedral if it can written as an intersection of a finite number of halfspaces. I finished the first part of the problem which asks that the set $PSD_n$ is a convex closed cone, but I can't connect anything between the concepts. Any hint or help is appreciated.

Answer 1

I assume that in this context, PSD matrices are defined to be symmetric real matrices.

Here's a proof that avoids extremal points/rays. Let $\langle A,B \rangle$ denote the inner-product of symmetric matrices $A,B$ defined by $\langle A,B \rangle = \operatorname{tr}(AB)$. First, we note that every halfspace can be written in the form $\{A:\langle A,M \rangle \geq \alpha\}$ for some symmetric $M$ and $\alpha>0$.

Claim: $\{A:\langle A,M \rangle \geq \alpha\}$ contains $PSD_n$ if and only if $M \in PSD_n$ and $\alpha \leq 0$.

Now, suppose for the purpose of contradiction that $PSD_n$ is polyhedral. Then by the above claim, there exist PSD matrices $M_1,\dots,M_{N_0}$ such that $$ PSD_n = \bigcap_{k=1}^{N_0} \{A:\langle A,M_k \rangle \geq \alpha_k\}. $$ Applying the above claim, we can replace every $\alpha_k$ with zero to get a possibly "smaller" set containing $PSD_n$. So, we can take $$ PSD_n = \bigcap_{k=1}^{N_0} \{A:\langle A,M_k \rangle \geq 0\}. $$ If $M = \sum \lambda_j x_jx_j^T$ with unit-vectors $x_j$ is an eigendecomposition, then we note that $$ \{A:\langle A,M \rangle \geq 0\} \supseteq \bigcap_{j}\{A:\langle A,x_jx_j^T \rangle \geq 0\} = \bigcap_{k} \{A:x_j^TAx \geq 0\} \supseteq PSD_n. $$ So, by replacing each $\{A:\langle A,M_k \rangle \geq 0\}$ with an associated intersection $\bigcap_{j=1}^n \{A:x_j^TAx \geq 0\}$, we now have a set of unit-vectors $\{x_1,x_2,\dots,x_N\}$ such that $$ PSD_n = \bigcap_{k=1}^N \{A:x_k^TAx_k \geq 0\}. $$ Select a unit-vector $x$ that is not a multiple of $x_k$ for any $k = 1,\dots,N$. Let $\alpha$ be given by $$ \alpha = \max_{k=1,\dots,N} (x_k^Tx)^2. $$ Note that this maximum necessarily exists since it is the maximum of a finite set, and (by Cauchy-Schwarz) $\alpha < 1$. Let $X = \alpha I - xx^T$.

Claim: The matrix $X$ is a non-PSD element of $\bigcap_{k=1}^N \{A:x_k^TAx_k \geq 0\}$.

So, $\bigcap_{k=1}^{N_0} \{A:\langle A,M_k \rangle \geq \alpha_k\}$ contains a non-PSD element, which contradicts our premise. So, $PSD_n$ is not polyhedral.

---

We could avoid using the vectors $x_j$'s if we define $x$ to be any unit vector that does not maximize $x^TM_kx$ for any $M_k$.

Answer 2

HINT:

The extreme rays $PSD_n$ are the $\mathbb{R}_{+}\cdot \pi$, where $\pi$ is an orthogonal projection of rank $1$. If $n>1$ there are infinitely many subspaces of $\dim 1$, hence infinitely many extremal rays. We conclude that the cone is not polyhedral.

Note: to show that a projector of rank $1$ is extremal, show that for $A$, $B$ positive semidefinite we have $$\textrm{Image} A+B = \textrm{Image} A+ \textrm{Image} B$$

To show this, check that for $A$ positive semidefinite $$(\textrm{Image} A)^{\perp} = \{ v \ | \ \langle A v | v \rangle = 0\}$$

$\bf{Added}$ Since you are studying $PSD_n$ it is important to know that $PSD_n$ is self dual under the trace pairing $(A,B)\mapsto Tr(AB)$. Now, if $PSD_n$ were a finite intersection of hyperplanes then its dual would be the span of the normald of those hyperplanes ( this is Farkas theorem). But $PSD_n$ is not finitely generated