Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:45:41Z http://mathoverflow.net/feeds/question/77131 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77131/convex-analytic-or-linear-algebraic-proof-that-a-certain-psd-matrix-is-a-sum-of-r Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices Colin Tan 2011-10-04T13:43:12Z 2011-10-11T03:36:21Z <p>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. </p> <blockquote> <p>A psd matrix of the form <code>$\left(\begin{smallmatrix} a &amp; b &amp; c\\ b &amp; c &amp; d \\ c &amp; d &amp; e \end{smallmatrix}\right)$</code> can be written as the sum of finitely many rank 1 matrices of the form <code>$\left(\begin{smallmatrix} x^4 &amp; x^3 y &amp; x^2 y^2\\ x^3 y &amp; x^2 y^2 &amp; x y^3 \\ x^2 y^2 &amp; x y^3 &amp; y^4 \end{smallmatrix}\right)$</code>?</p> </blockquote> <p><b>Edit</b> Thank you Greg for your answer. In our comments, we observe that every psd matrix of the form <code>$\left(\begin{smallmatrix} a &amp; b &amp; c &amp; d\\ b &amp; c &amp; d &amp; e\\ c &amp; d &amp; e &amp; f\\ d &amp; e &amp; f &amp; g \end{smallmatrix}\right)$</code> is a finite sum of rank 1 and rank 2 matrices. Can one prove the following in a convex analytic manner?</p> <blockquote> <p>A psd matrix of the form <code>$\left(\begin{smallmatrix} a &amp; b &amp; c &amp; d\\ b &amp; c &amp; d &amp; e\\ c &amp; d &amp; e &amp; f\\ d &amp; e &amp; f &amp; g \end{smallmatrix}\right)$</code> can be written as the sum of finitely many rank 1 matrices of the form <code>$\left(\begin{smallmatrix} x^6 &amp; x^5 y &amp; x^4 y^2 &amp; x^3 y^3\\ x^5 y &amp; x^4 y^2 &amp; x^3 y^3 &amp; x^2 y^4\\ x^4 y^2 &amp; x^3 y^3 &amp; x^2y^4 &amp; x y^5 \\ x^3y^3 &amp; x^2y^4 &amp; x y^5 &amp; y^6 \end{smallmatrix}\right)$</code>?</p> </blockquote> <hr> <p><b> Motivation </b> 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.</p> <p>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.</p> <p>Since <a href="http://mathoverflow.net/questions/49622/is-the-set-of-polynomial-sum-of-squares-closed-under-limits/49629#49629" rel="nofollow">the cone $\Sigma_{2,4}$ is closed in the vector space <code>${\mathbb{R}}[x,y]_4$</code></a> 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$. </p> <p>The cone of positive semidefinite matrices of the form <code>$\left(\begin{smallmatrix} a &amp; b &amp; c\\ b &amp; c &amp; d \\ c &amp; d &amp; e \end{smallmatrix}\right)$</code> is isomorphic to $\Sigma_{2,4}^{\vee}$. Under this isomorphism, point evaluations correspond to rank 1 matrices of the form <code>$\left(\begin{smallmatrix} x^4 &amp; x^3 y &amp; x^2 y^2\\ x^3 y &amp; x^2 y^2 &amp; x y^3 \\ x^2 y^2 &amp; x y^3 &amp; y^4 \end{smallmatrix}\right)$</code>. The above proof of which I'm seeking a convex analytic proof is equivalent to the assertion $P_{2,4}=\Sigma_{2,4}$.</p> http://mathoverflow.net/questions/77131/convex-analytic-or-linear-algebraic-proof-that-a-certain-psd-matrix-is-a-sum-of-r/77544#77544 Answer by Greg Kuperberg for Convex Analytic or linear algebraic proof that a certain psd matrix is a sum of rank 1 psd matrices Greg Kuperberg 2011-10-08T16:16:39Z 2011-10-08T16:16:39Z <p>$\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.</p> <p>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 <em>any</em> 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).</p> <p>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)$.</p> <p>(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.)</p>