Positive semidefinite cone is generated by all rank-$1$ matrices.

The positive semidefinite cone is generated by all rank-$1$ matrices $xx^T$, which form the extreme rays of the cone. Positive definite matrices lie in the interior of the cone. Positive semidefinite matrices with at least one zero eigenvalue are on the boundary.

I am unable to justify why the statements above are true. Please give some hints.

• What definition of "cone" are you using? – Jeff Snider Feb 17 '14 at 17:20
• if $x \in S$ then c.x is in S c>=0 – thetatheta Feb 18 '14 at 13:44

$C=\{xx^\top:x\in\mathbb{R}^n\}$ is a cone, because for any $c\in\mathbb{R}^+$ we have $$cxx^\top=(\sqrt{c}x)(\sqrt{c}x)^\top\in C.$$ Also observe that $-cxx^\top\not\in C$, since $\sqrt{-c}\not\in\mathbb{R}$. And $C$ is a pointed cone since $x=0\Rightarrow 0\in C$. (These aren't necessary, only facts about the cone.)

$xx^\top$ is rank one because each row is a scalar multiple of any other (nonzero) row. (Similarly for columns.)

$xx^\top$ is positive semi-definite for any $x\in\mathbb{R}^n$ because for any $y\in\mathbb{R}^n$ you have $$y^\top xx^\top y=(y^\top x)(y^\top x)^\top=\left(\sum_{k=1}^n y_k x_k\right)^2 \ge 0.$$

For some $xx^\top$ pick any nonzero $y$ such that $y^\top xx^\top y=0$, and any small positive definite matrix $M$. Then $$y^\top(xx^\top+M)y=y^\top xx^\top y+y^\top My=y^\top My>0.$$ Hence also $y^\top (xx^\top-M) y<0$, and $xx^\top-M$ is not positive semidefinite. This shows that $xx^\top$ is on the boundary.

Use the same argument for PSD matrices with one zero eigenvector. (When $M$ has a zero eigenvalue there is always a nonzero $y$ such that $y^\top M y=0$.)

We have that the space is convex: for any two $x_0,x_1\in\mathbb{R}^n$ and $0\le \lambda\le 1$ we know $$y^\top \big(\lambda x_0x_0^\top + (1-\lambda)x_1x_1^\top\big) y = \lambda y^\top x_0x_0^\top y + (1-\lambda) y^\top x_1x_1^\top y \ge 0.$$

Now you need to show how you can create an affine combination of matrices in the form $xx^\top$ to create any positive definite matrix: this will show they are all in the interior.