Let $S$ be the cone of positive semidefinite symmetric real matrices of size $n\times n$. The cone $S$ spans a $d:=n(n+1)/2$ dimensional vector space.

Let $C\subset S$ be a subcone formed by intersecting $S$ with a plane $\Pi$. Suppose that the plane $\Pi$ is of high codimension, say $\dim \Pi = t d$ where $1/2 < t < 1$ .

If a matrix $A\in C$ spans an extremal ray of $C$, then ${\mathrm{rank}}\, A\le n-1$. This is because $A$ cannot be an interior point of $S$. Can this bound be improved in general?

  • $\begingroup$ Improved how??? $\endgroup$ – Igor Rivin Sep 6 '11 at 20:00
  • $\begingroup$ Are you somehow excluding the cases where $\dim \Pi = 1$? In such cases $\text{rank} A$ could be $d$. $\endgroup$ – Robert Israel Sep 6 '11 at 20:01
  • $\begingroup$ Yes Robert. I'm assuming $\dim \Pi > d/2$. $\endgroup$ – user2529 Sep 7 '11 at 1:44
  • $\begingroup$ Hi Robert. I have an observation. If A spans an extremal ray, and $B\in C$ is distinct from A, then every matrix in the line segment (A, B) must have rank strictly larger than A. $\endgroup$ – user2529 Sep 13 '11 at 5:16

We may assume wlog that $A$ is diagonal, and that its first $r$ diagonal elements are nonzero and the others 0, where $r = \text{rank}(A)$. Suppose the symmetric matrix $B \in \Pi$. In order for $A + tB$ to be positive semidefinite for $t$ in some open interval containing $0$, it is necessary and sufficient that all nonzero entries of $B$ are in the upper left $r \times r$ block. So for $A$ to span an extremal ray in $\cal C$, it is necessary and sufficient that the only such members of $\Pi$ are multiples of $A$. Thus the maximal $\Pi$ such that $A$ spans an extremal ray of $\cal C$ consists of matrices whose upper left $r \times r$ block is a multiple of $A$, and this has dimension $\frac{n(n+1)}{2} - \frac{r(r+1)}{2} + 1$. So $td \le d - \frac{r(r+1)}{2} + 1$, or $r \le \left\lfloor \frac{\sqrt{8(1-t)d + 9} - 1}{2} \right\rfloor$.


Your Answer

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