Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.