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

2011-10-04T13:43:12Z

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}$.

Answer by Greg Kuperberg for Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices

2011-10-08T16:16:39Z

$\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.)

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

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

Answer by Greg Kuperberg for Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices