# Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices

Can you prove the following using techniques from convex analysis or linear algebra? I was originally seeking an elementary proof, but I think it is better to broaden the scope for this bounty question.

A psd matrix of the form $\left(\begin{smallmatrix} a & b & c\\ b & c & d \\ c & d & e \end{smallmatrix}\right)$ can be written as the sum of finitely many rank 1 matrices of the form $\left(\begin{smallmatrix} x^4 & x^3 y & x^2 y^2\\ x^3 y & x^2 y^2 & x y^3 \\ x^2 y^2 & x y^3 & y^4 \end{smallmatrix}\right)$?

Edit Thank you Greg for your answer. In our comments, we observe that every psd matrix of the form $\left(\begin{smallmatrix} a & b & c & d\\ b & c & d & e\\ c & d & e & f\\ d & e & f & g \end{smallmatrix}\right)$ is a finite sum of rank 1 and rank 2 matrices. Can one prove the following in a convex analytic manner?

A psd matrix of the form $\left(\begin{smallmatrix} a & b & c & d\\ b & c & d & e\\ c & d & e & f\\ d & e & f & g \end{smallmatrix}\right)$ can be written as the sum of finitely many rank 1 matrices of the form $\left(\begin{smallmatrix} x^6 & x^5 y & x^4 y^2 & x^3 y^3\\ x^5 y & x^4 y^2 & x^3 y^3 & x^2 y^4\\ x^4 y^2 & x^3 y^3 & x^2y^4 & x y^5 \\ x^3y^3 & x^2y^4 & x y^5 & y^6 \end{smallmatrix}\right)$?

Motivation The first question is a convex analytic proof to the (known fact) that $P_{2,4}=\Sigma_{2,4}$, while the second question is to prove $P_{2,6}=\Sigma_{2,6}$. Below, I describe the origin of the problem for the former.

I came upon this problem as a convex analytic approach to the (known fact) that $P_{2,4}=\Sigma_{2,4}$. Here $P_{2,4}$ is the cone of nonnegative-valued binary quartics. $\Sigma_{2,4}$ is the cone of binary quartics that are sums of squares. (A binary quartic is a homogeneous polynomial in 2 variables of degree 4). Obviously $P_{2,4}\subseteq \Sigma_{2,4}$. The standard proof that equality holds is by dehomonogizing and applying the Fundamental theorem of algebra.

Since the cone $\Sigma_{2,4}$ is closed in the vector space ${\mathbb{R}}[x,y]_4$ of homogeneous polynomials in 2 variables of degree 4, a separation theorem in convex geometry provides a necessary and sufficient condition for a binary quartic $f$ to lie in $\Sigma_{2,4}$. This condition is that, for any linear functional $T$ which spans an extremal ray of the dual cone $\Sigma_{2,4}^{\vee}$, we have $T(f)\ge 0$.

The cone of positive semidefinite matrices of the form $\left(\begin{smallmatrix} a & b & c\\ b & c & d \\ c & d & e \end{smallmatrix}\right)$ is isomorphic to $\Sigma_{2,4}^{\vee}$. Under this isomorphism, point evaluations correspond to rank 1 matrices of the form $\left(\begin{smallmatrix} x^4 & x^3 y & x^2 y^2\\ x^3 y & x^2 y^2 & x y^3 \\ x^2 y^2 & x y^3 & y^4 \end{smallmatrix}\right)$. The above proof of which I'm seeking a convex analytic proof is equivalent to the assertion $P_{2,4}=\Sigma_{2,4}$.

-
Unfortunately, your formatting is totally hosed, maybe you can fix... –  Igor Rivin Oct 4 '11 at 13:52
Yup. I've redone the formatting. –  Colin Tan Oct 4 '11 at 13:55
If $A$ is your symmetric matrix, then it is orthogonally diagonalizable, $A=PDP^T=\sum \lambda_i u_i u_i^T$, where $\lambda_i$ are the non-negative eigenvalues and $u_i$ are columns of $P$. So $A=\sum v_iv_i^T$ where $v_i=\sqrt{\lambda_i}u_i$. Can't see how to get $v_i$ to the form $(x^2,xy,y^2)^T$ you require but this holds for all n. –  user1894 Oct 4 '11 at 16:29
hello unknown (google), I'm asking to show that my symmetric matrix $A$ is a sum of matrices of the special form. "Sum" is the keyword here. –  Colin Tan Oct 5 '11 at 12:53

$\newcommand{\R}{\mathbb{R}}$ Let $K$ be a compact convex body in $\R^n$, or some other $n$-dimensional vector space or affine space. Then every point $p \in K$ has an extremality rank, which is the largest dimension of a flat open ball $B$ such that $p \in B \subset K$. The 0-extremal points are thus the usual extremal points, while the $n$-extremal points are the interior points. Also, the finite-dimensional Krein-Milman theorem says that $K$ is the convex hull of its extremal points. Also, if we intersect $K$ with a hyperplane $H \subset \R^n$, then the extremality rank of a point $p \in H \cap K$ is either the same or one less than its extremality rank in $K$. In particular, the extremality rank of $p$ cannot decrease by more than 1. If $K$ has no 1-extremal points, then the extremal points of $K \cap H$ are all extremal points of $K$ as well.
Let $K_n \subset S^2(\R^n)$ be the convex body of positive, semidefinite symmetric matrices with trace 1. Since you can canonicalize $p \in K_n$ as a symmetric form, its extremality rank can only depend on its rank as a matrix. (Well, an arbitrary change of basis won't preserve the trace, but that doesn't matter since it still yields a projective transformation on the trace 1 affine space. It may have been better to do this without the trace 1 condition, with closed cones instead, but the compact version is easier to see.) If it has matrix rank $r$, then it lives in the interior of an extremal copy of $K_r$, so its extremality rank is $\binom{r}{2}-1$. In particular, $K_n$ has no 1-extremal points. The extremal points are those of the form $v \otimes v$. After that are the 2-extremal points, which are rank 2 matrices $v \otimes v + w \otimes w$. Actually, you can see things most clearly by recognizing $K_2$ as a round 2-dimensional disk, which is a convex set that have "vertices" and interior points but no edges. Anyway, it means that if you impose any linear condition on PSD matrices represented by a hyperplane $H$, the extremal points in $K_n \cap H$ are still rank 1 matrices (that satisfy the same condition).
Your question is a special case of this general result. You are looking at $K_3 \cap H$, where $H$ is the condition that the middle entry of the matrix equals the northeast or southwest entry. The extremal points are all of the form $v \otimes v \in H$, which forces $v$ to have the form $(x^2,xy,y^2)$.
(Note that the complex version of $K_n$ is an important object in quantum information theory; it's convex body of mixed states on an $n$-state qudit. That is how I learned about this.)
Let me attempt to use your argument to prove $\Sigma_{2,6}=P_{2,6}$. In this case, we are dealing with $4\times 4$ matrices and there are 7 independent entries. So the plane $H$ now is of codimension 3. Thus $K_4 \cap H$ can possibly have rank 1 or rank 2 matrices. Do you know of a way to sharpen your argument to dealing with this case? –  Colin Tan Oct 9 '11 at 6:52
My feeling is that the result is no longer true for the same reason. I.e., as far as I know, if $H$ is a general subspace of codimension 3, then $K_n \cap H$ does have extreme points that are rank 2 matrices. For your choice of $H$, something special-looking happens: $H$ does not meet one of the circular 2-dimensional flats of $\partial K_4$ without meeting it in an entire interval. –  Greg Kuperberg Oct 10 '11 at 7:43