Can extremal matrices of subcones of psd matrices have low rank? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:49:36Z http://mathoverflow.net/feeds/question/74671 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/74671/can-extremal-matrices-of-subcones-of-psd-matrices-have-low-rank Can extremal matrices of subcones of psd matrices have low rank? Colin Tan 2011-09-06T17:09:00Z 2011-09-07T16:25:56Z <p>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. </p> <p>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 &lt; t &lt; 1$ .</p> <p>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?</p> http://mathoverflow.net/questions/74671/can-extremal-matrices-of-subcones-of-psd-matrices-have-low-rank/74769#74769 Answer by Robert Israel for Can extremal matrices of subcones of psd matrices have low rank? Robert Israel 2011-09-07T16:25:56Z 2011-09-07T16:25:56Z <p>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$. </p>